methods for handling symmetries by dynamic lexicographic ordering reduction
This implements lexicographic reduction, which generalizes symresack propagation to work for non-binary variable domains, and is dynamified. Whereas static lexicographic reduction propagates that a vector \(x\) is lexicographically larger than its permuted counterpart (i.e., \(x \succeq \gamma(x)\) with \(\succeq\) being standard elementwise lexicographic comparison), the dynamic variant determines the variable vector ordering dynamically. Just as in orbital reduction (cf. symmetry_orbital.c), the variable order is chosen as the variables branched on from the root node to the focus node. Thus, in node \(\beta\), we propagate \(\sigma_\beta(x) \succeq \sigma_\beta(\gamma(x))\), where \(\sigma_\beta(\cdot)\) permutes and restricts the variable vector such that it corresponds to the branched variables in the order from the rooted path to \(\beta\).
See Section 4.1 and Example 11 in [vD,H]:
J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023, https://doi.org/10.48550/arXiv.2211.01295.
For dynamic lexicographic reduction, it is crucial that the vectors \(\sigma_\beta(x)\) are the branching variables up to node \(\beta\) in the given order. Since SCIP can change the tree structure during solving (re-writing history), we store the original branching decisions at the moment they are made. See event_shadowtree.c .
Definition in file symmetry_lexred.c.
#include "blockmemshell/memory.h"
#include "scip/symmetry_lexred.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_var.h"
#include "scip/struct_var.h"
#include "scip/type_var.h"
#include "scip/scip.h"
#include "scip/scip_branch.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_sol.h"
#include "scip/scip_var.h"
#include "scip/debug.h"
#include "scip/struct_scip.h"
#include "scip/struct_mem.h"
#include "scip/struct_tree.h"
#include "scip/symmetry.h"
#include "scip/event_shadowtree.h"
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | LexRedPermData |
struct | NodeDepthBranchIndex |
struct | VarArrayNodeDepthBranchIndex |
Functions | |
static SCIP_RETCODE | lexdataFree (SCIP *scip, LEXDATA **lexdata) |
static SCIP_RETCODE | lexdataCreate (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA **lexdata, SCIP_VAR *const *vars, int nvars, int *perm, SYM_SYMTYPE symtype, SCIP_Real *permvardomaincenter, SCIP_Bool usedynamicorder, SCIP_Bool *success) |
static | SCIP_DECL_SORTINDCOMP (sortbynodedepthbranchindices) |
static int | varOrderGetIndex (int *varorder, int pos) |
static SCIP_RETCODE | getVarOrder (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, int nvarstotal, SCIP_VAR **branchvars, int nbranchvars, int *varorder, int *nselvars, int maxnselvars) |
static SCIP_RETCODE | getVarBounds (SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset, SCIP_Real *lb1, SCIP_Real *ub1, SCIP_Real *lb2, SCIP_Real *ub2) |
static SCIP_Bool | alwaysLTshiftedVars (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real shift1, SCIP_Real shift2, SCIP_Bool isnegated, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset) |
static SCIP_Bool | canGTshiftedVars (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real shift1, SCIP_Real shift2, SCIP_Bool isnegated, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset) |
static SCIP_RETCODE | propagateLowerBoundVar (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real center1, SCIP_Real center2, SCIP_Bool isnegated, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset) |
static SCIP_RETCODE | propagateUpperBoundSymVar (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real center1, SCIP_Real center2, SCIP_Bool isnegated, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset) |
static SCIP_RETCODE | propagateSelfReflectionVar (SCIP *scip, SCIP_VAR *var, SCIP_Real center, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset) |
static SCIP_RETCODE | propagateVariablePair (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real center1, SCIP_Real center2, SCIP_Bool isnegated, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset) |
static SCIP_RETCODE | peekStaticLexredIsFeasible (SCIP *scip, LEXDATA *lexdata, int *varorder, int nselvars, int fixi, int fixj, int fixrow, SCIP_Real fixvaluei, SCIP_Real fixvaluej, SCIP_Bool *peekfeasible, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset) |
static SCIP_RETCODE | propagateStaticLexred (SCIP *scip, LEXDATA *lexdata, int *varorder, int nselvars, SCIP_Bool *infeasible, int *nreductions) |
static SCIP_RETCODE | propagateLexredDynamic (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, int nvarstotal, SCIP_VAR **branchvars, int nbranchvars, SCIP_Bool *infeasible, int *nreductions) |
static SCIP_RETCODE | propagateLexredStatic (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, SCIP_Bool *infeasible, int *nreductions) |
static SCIP_RETCODE | propagateLexicographicReductionPerm (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, int nvarstotal, SCIP_VAR **branchvars, int nbranchvars, SCIP_Bool *infeasible, int *nreductions) |
static SCIP_RETCODE | shadowtreeFillNodeDepthBranchIndices (SCIP *scip, SCIP_LEXREDDATA *masterdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, SCIP_VAR **branchvars, int *nbranchvars, SCIP_SHADOWTREE *shadowtree, SCIP_NODE *focusnode, SCIP_Bool *inforesolved) |
static SCIP_RETCODE | shadowtreeUndoNodeDepthBranchIndices (SCIP *scip, SCIP_LEXREDDATA *masterdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, SCIP_VAR **branchvars, int *nbranchvars, SCIP_SHADOWTREE *shadowtree, SCIP_NODE *focusnode) |
SCIP_RETCODE | SCIPlexicographicReductionGetStatistics (SCIP *scip, SCIP_LEXREDDATA *masterdata, int *nred, int *ncutoff) |
SCIP_RETCODE | SCIPlexicographicReductionPrintStatistics (SCIP *scip, SCIP_LEXREDDATA *masterdata) |
SCIP_RETCODE | SCIPlexicographicReductionPropagate (SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun) |
SCIP_RETCODE | SCIPlexicographicReductionAddPermutation (SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_VAR **permvars, int npermvars, int *perm, SYM_SYMTYPE symtype, SCIP_Real *permvardomaincenter, SCIP_Bool usedynamicorder, SCIP_Bool *success) |
SCIP_RETCODE | SCIPlexicographicReductionReset (SCIP *scip, SCIP_LEXREDDATA *masterdata) |
SCIP_RETCODE | SCIPlexicographicReductionFree (SCIP *scip, SCIP_LEXREDDATA **masterdata) |
SCIP_RETCODE | SCIPincludeLexicographicReduction (SCIP *scip, SCIP_LEXREDDATA **masterdata, SCIP_EVENTHDLR *shadowtreeeventhdlr) |
typedef struct LexRedPermData LEXDATA |
Definition at line 100 of file symmetry_lexred.c.
typedef struct NodeDepthBranchIndex NODEDEPTHBRANCHINDEX |
Definition at line 125 of file symmetry_lexred.c.
typedef struct VarArrayNodeDepthBranchIndex VARARRAYNODEDEPTHBRANCHINDEX |
Definition at line 135 of file symmetry_lexred.c.
|
static |
frees dynamic lexicographic reduction propagator data
scip | SCIP data structure |
lexdata | pointer to individual lexicographic reduction propagator datas |
Definition at line 144 of file symmetry_lexred.c.
References assert(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPhashmapFree(), SCIPreleaseVar(), SYM_SYMTYPE_SIGNPERM, and TRUE.
Referenced by SCIPlexicographicReductionReset().
|
static |
creates dynamic lexicographic reduction propagator data
Fixed points are removed.
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
lexdata | pointer to store data for permutation to be added |
vars | input variables of the lexicographic reduction propagator |
nvars | input number of variables of the lexicographic reduction propagator |
perm | input permutation of the lexicographic reduction propagator |
symtype | type of symmetries in perm |
permvardomaincenter | array containing center point for each variable domain |
usedynamicorder | whether a dynamic variable order shall be used |
success | to store whether the component is successfully added |
Definition at line 222 of file symmetry_lexred.c.
References assert(), FALSE, i, VarArrayNodeDepthBranchIndex::masterdata, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPactivateShadowTree(), SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPcaptureVar(), SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapInsertInt(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), SCIPvarIsTransformed(), SYM_SYMTYPE_PERM, TRUE, var, and vars.
Referenced by SCIPlexicographicReductionAddPermutation().
|
static |
comparator used in the getVarOrder() function, for sorting an array of NODEDEPTHBRANCHINDEX by depth, then by index
result: 0: the same index is compared, so the (depth, index)-informations are the same -1: the depth of ind1 is smaller than the depth of ind2, or it's equal and the index is smaller 1: the depth of ind2 is smaller than the depth of ind1, or it's equal and the index is smaller
Definition at line 422 of file symmetry_lexred.c.
References assert(), NodeDepthBranchIndex::index, VarArrayNodeDepthBranchIndex::masterdata, NodeDepthBranchIndex::nodedepth, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, SCIPhashmapGetImageInt(), VarArrayNodeDepthBranchIndex::vars, and vars.
|
static |
return the index of a variable at a specific position of a variable order
varorder | variable order (or NULL) |
pos | position for which index is returned |
Definition at line 466 of file symmetry_lexred.c.
References assert(), and NULL.
Referenced by peekStaticLexredIsFeasible(), and propagateStaticLexred().
|
static |
gets the variable ordering based on the branching decisions at the node
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
lexdata | pointer to data for this permutation |
nodedepthbranchindices | array with (depth, index)-information per variable in rooted path to focus node |
nvarstotal | length of that array |
branchvars | array populated with variables branched on in the symvarmap hashset |
nbranchvars | number of elements in branchvars array |
varorder | array to populate with variable order |
nselvars | pointer to number of variables in the ordering |
maxnselvars | maximal size of the number of selected variables |
Definition at line 481 of file symmetry_lexred.c.
References assert(), i, VarArrayNodeDepthBranchIndex::masterdata, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, LexRedPermData::nvars, nvars, SCIP_OKAY, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPsortInd(), var, LexRedPermData::varmap, LexRedPermData::vars, VarArrayNodeDepthBranchIndex::vars, and vars.
Referenced by propagateLexredDynamic().
|
static |
gerts local variable bounds or reads bound from peek data
var1 | first variable in comparison |
var2 | second variable in comparison |
peekmode | whether function is called in peek mode |
varidx1 | index of var1 (or NULL) |
varidx2 | index of var2 (or NULL) |
peeklbs | lower bounds of variables in peek mode (or NULL) |
peekubs | upper bounds of variables in peek mode (or NULL) |
peekbdset | whether peek bounds have been set (or NULL) |
lb1 | pointer to store lower bound of var1 |
ub1 | pointer to store upper bound of var1 |
lb2 | pointer to store lower bound of var2 |
ub2 | pointer to store upper bound of var2 |
Definition at line 590 of file symmetry_lexred.c.
References assert(), NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().
Referenced by alwaysLTshiftedVars(), canGTshiftedVars(), propagateLowerBoundVar(), propagateSelfReflectionVar(), propagateStaticLexred(), and propagateUpperBoundSymVar().
|
static |
returns whether a shifted variable is always smaller than another shifted variable
Shifts are always (var - shift).
scip | SCIP data structure |
var1 | first variable in comparison |
var2 | second variable in comparison |
shift1 | shift of var1 |
shift2 | shift of var2 |
isnegated | whether shift of var2 is negated |
peekmode | whether function is called in peek mode |
varidx1 | index of var1 (or NULL) |
varidx2 | index of var2 (or NULL) |
peeklbs | lower bounds of variables in peek mode (or NULL) |
peekubs | upper bounds of variables in peek mode (or NULL) |
peekbdset | whether peek bounds have been set (or NULL) |
Definition at line 644 of file symmetry_lexred.c.
References assert(), FALSE, getVarBounds(), NULL, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPisLT(), and TRUE.
Referenced by peekStaticLexredIsFeasible(), and propagateVariablePair().
|
static |
returns whether a shifted variable can be greater than another shifted variable
Shifts are always (var - shift).
scip | SCIP data structure |
var1 | first variable in comparison |
var2 | second variable in comparison |
shift1 | shift of var1 |
shift2 | shift of var2 |
isnegated | whether shift of var2 is negated |
peekmode | whether function is called in peek mode |
varidx1 | index of var1 (or NULL) |
varidx2 | index of var2 (or NULL) |
peeklbs | lower bounds of variables in peek mode (or NULL) |
peekubs | upper bounds of variables in peek mode (or NULL) |
peekbdset | whether peek bounds have been set (or NULL) |
Definition at line 691 of file symmetry_lexred.c.
References assert(), FALSE, getVarBounds(), NULL, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPisGT(), and TRUE.
Referenced by peekStaticLexredIsFeasible(), and propagateStaticLexred().
|
static |
propagates lower bound of first variable in relation x >= y for shifted variables
scip | SCIP data structure |
var1 | first variable in pair |
var2 | second variable in pair |
center1 | center of var1 (original var domain) |
center2 | center of var2 (original var domain) |
isnegated | whether var2 is negated by symmetry |
infeasible | pointer to store whether infeasibility is found |
nreductions | pointer to store number of reductions |
peekmode | whether function is called in peek mode |
varidx1 | index of var1 (or NULL) |
varidx2 | index of var2 (or NULL) |
peeklbs | lower bounds of variables in peek mode (or NULL) |
peekubs | upper bounds of variables in peek mode (or NULL) |
peekbdset | whether peek bounds have been set (or NULL) |
Definition at line 735 of file symmetry_lexred.c.
References assert(), FALSE, getVarBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), SCIPtightenVarLb(), SCIPvarGetName(), and TRUE.
Referenced by peekStaticLexredIsFeasible(), and propagateVariablePair().
|
static |
propagates upper bound of second variable in relation x >= y for shifted variables
scip | SCIP data structure |
var1 | first variable in pair |
var2 | second variable in pair |
center1 | center of var1 (original var domain) |
center2 | center of var2 (original var domain) |
isnegated | whether var2 is negated by symmetry |
infeasible | pointer to store whether infeasibility is found |
nreductions | pointer to store number of reductions |
peekmode | whether function is called in peek mode |
varidx1 | index of var1 (or NULL) |
varidx2 | index of var2 (or NULL) |
peeklbs | lower bounds of variables in peek mode (or NULL) |
peekubs | upper bounds of variables in peek mode (or NULL) |
peekbdset | whether peek bounds have been set (or NULL) |
Definition at line 822 of file symmetry_lexred.c.
References assert(), FALSE, getVarBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), and TRUE.
Referenced by peekStaticLexredIsFeasible(), and propagateVariablePair().
|
static |
propagates x - c >= c - x
scip | SCIP data structure |
var | variable |
center | center of var (original var domain) |
infeasible | pointer to store whether infeasibility is found |
nreductions | pointer to store number of reductions |
peekmode | whether function is called in peek mode |
varidx | index of var (or NULL) |
peeklbs | lower bounds of variables in peek mode (or NULL) |
peekubs | upper bounds of variables in peek mode (or NULL) |
peekbdset | whether peek bounds have been set (or NULL) |
Definition at line 932 of file symmetry_lexred.c.
References assert(), FALSE, getVarBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), SCIPtightenVarLb(), SCIPvarGetName(), TRUE, var, and varidx.
Referenced by propagateVariablePair().
|
static |
propagates lexicographic order for one pair of symmetric variables
scip | SCIP data structure |
var1 | first variable in pair |
var2 | second variable in pair |
center1 | center of var1 (original var domain) |
center2 | center of var2 (original var domain) |
isnegated | whether var2 is negated by symmetry |
infeasible | pointer to store whether infeasibility is found |
nreductions | pointer to store number of reductions |
peekmode | whether function is called in peek mode |
varidx1 | index of var1 (or NULL) |
varidx2 | index of var2 (or NULL) |
peeklbs | lower bounds of variables in peek mode (or NULL) |
peekubs | upper bounds of variables in peek mode (or NULL) |
peekbdset | whether peek bounds have been set (or NULL) |
Definition at line 1003 of file symmetry_lexred.c.
References alwaysLTshiftedVars(), assert(), NULL, propagateLowerBoundVar(), propagateSelfReflectionVar(), propagateUpperBoundSymVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateStaticLexred().
|
static |
checks if the static lexred with a certain variable ordering is feasible in the hypothetical scenario where variables with indices i and j are fixed to fixvalue (i.e., peeking)
scip | SCIP data structure |
lexdata | pointer to data for this permutation |
varorder | array populated with variable order (or NULL for static propagation) |
nselvars | number of variables in the ordering |
fixi | variable index of left fixed column |
fixj | variable index of right fixed column |
fixrow | row index in var ordering, from which to start peeking |
fixvaluei | value on which variables i is fixed |
fixvaluej | value on which variables j is fixed |
peekfeasible | pointer to store whether this is feasible or not |
peeklbs | lower bounds of variables in peek mode (or NULL) |
peekubs | upper bounds of variables in peek mode (or NULL) |
peekbdset | whether peek bounds have been set (or NULL) |
Definition at line 1076 of file symmetry_lexred.c.
References alwaysLTshiftedVars(), assert(), canGTshiftedVars(), FALSE, i, LexRedPermData::invperm, NULL, LexRedPermData::nvars, nvars, LexRedPermData::perm, propagateLowerBoundVar(), propagateUpperBoundSymVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SYM_SYMTYPE_SIGNPERM, LexRedPermData::symtype, TRUE, LexRedPermData::vardomaincenter, varOrderGetIndex(), and LexRedPermData::vars.
Referenced by propagateStaticLexred().
|
static |
propagates static lexicographic reduction with specified variable ordering
scip | SCIP data structure |
lexdata | pointer to data for this permutation |
varorder | array populated with variable order (or NULL if static propagation) |
nselvars | number of variables in the ordering |
infeasible | pointer to store whether the problem is infeasible |
nreductions | pointer to store the number of found domain reductions |
Definition at line 1204 of file symmetry_lexred.c.
References assert(), canGTshiftedVars(), FALSE, getVarBounds(), i, LexRedPermData::invperm, NULL, LexRedPermData::nvars, nvars, peekStaticLexredIsFeasible(), LexRedPermData::perm, propagateVariablePair(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBufferArray, SCIPisIntegral(), SCIPsymEQ(), SCIPsymGE(), SCIPsymGT(), SCIPsymLE(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetType(), SYM_SYMTYPE_SIGNPERM, LexRedPermData::symtype, TRUE, LexRedPermData::vardomaincenter, varOrderGetIndex(), and LexRedPermData::vars.
Referenced by propagateLexredDynamic(), and propagateLexredStatic().
|
static |
propagation method for a dynamic lexicographic reduction
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
lexdata | pointer to data for this permutation |
nodedepthbranchindices | array with (depth, index)-information per variable in rooted path to focus node |
nvarstotal | length of nodedepthbranchindices array |
branchvars | array populated with variables branched on |
nbranchvars | number of elements in branchvars array |
infeasible | pointer to store whether the problem is infeasible |
nreductions | pointer to store the number of found domain reductions |
Definition at line 1536 of file symmetry_lexred.c.
References assert(), getVarOrder(), LexRedPermData::isdynamic, VarArrayNodeDepthBranchIndex::masterdata, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, LexRedPermData::nvars, nvars, propagateStaticLexred(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.
Referenced by propagateLexicographicReductionPerm().
|
static |
propagation method for a dynamic lexicographic reduction
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
lexdata | pointer to data for this permutation |
infeasible | pointer to store whether the problem is infeasible |
nreductions | pointer to store the number of found domain reductions |
Definition at line 1586 of file symmetry_lexred.c.
References assert(), LexRedPermData::isdynamic, VarArrayNodeDepthBranchIndex::masterdata, NULL, LexRedPermData::nvars, propagateStaticLexred(), SCIP_Bool, SCIP_CALL, and SCIP_OKAY.
Referenced by propagateLexicographicReductionPerm().
|
static |
propagation method for applying dynamic lexicographic reduction for a single permutation
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
lexdata | pointer to data for this permutation |
nodedepthbranchindices | array with (depth, index)-information per variable in rooted path to focus node |
nvarstotal | length of that array |
branchvars | array populated with variables branched on |
nbranchvars | number of elements in branchvars array |
infeasible | pointer to store whether the problem is infeasible |
nreductions | pointer to store the number of found domain reductions |
Definition at line 1614 of file symmetry_lexred.c.
References assert(), FALSE, LexRedPermData::isdynamic, VarArrayNodeDepthBranchIndex::masterdata, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, propagateLexredDynamic(), propagateLexredStatic(), SCIP_Bool, SCIP_CALL, and SCIP_OKAY.
Referenced by SCIPlexicographicReductionPropagate().
|
static |
populates array with information of first variable change
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
nodedepthbranchindices | array to populate |
branchvars | array to populate with variables branched on |
nbranchvars | number of elements in branchvars array |
shadowtree | pointer to shadow tree structure |
focusnode | focusnode to which the rooted path is evaluated |
inforesolved | pointer to store whether information is successfully resolved |
Definition at line 1657 of file symmetry_lexred.c.
References assert(), SCIP_ShadowNode::branchingdecisions, c, SCIP_ShadowNode::children, FALSE, i, NodeDepthBranchIndex::index, VarArrayNodeDepthBranchIndex::masterdata, SCIP_ShadowNode::nbranchingdecisions, SCIP_ShadowNode::nchildren, NodeDepthBranchIndex::nodedepth, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, SCIP_ShadowNode::parent, SCIP_Bool, SCIP_OKAY, SCIPhashmapGetImageInt(), SCIPnodeGetDepth(), SCIPshadowTreeGetShadowNode(), SCIPvarIsTransformed(), SCIPwarningMessage(), TRUE, SCIP_ShadowBoundUpdate::var, and var.
Referenced by SCIPlexicographicReductionPropagate().
|
static |
cleans nodedepthbranchindices array
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
nodedepthbranchindices | array populated by nodedepthbranchindices to clean |
branchvars | array populated with variables branched on |
nbranchvars | number of elements in branchvars array |
shadowtree | pointer to shadow tree structure |
focusnode | focusnode to which the rooted path is evaluated |
Definition at line 1773 of file symmetry_lexred.c.
References assert(), SCIP_ShadowNode::branchingdecisions, c, SCIP_ShadowNode::children, i, NodeDepthBranchIndex::index, VarArrayNodeDepthBranchIndex::masterdata, SCIP_ShadowNode::nbranchingdecisions, SCIP_ShadowNode::nchildren, NodeDepthBranchIndex::nodedepth, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, SCIP_ShadowNode::parent, SCIP_OKAY, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPnodeGetDepth(), SCIPshadowTreeGetShadowNode(), SCIP_ShadowBoundUpdate::var, and var.
Referenced by SCIPlexicographicReductionPropagate().
SCIP_RETCODE SCIPlexicographicReductionGetStatistics | ( | SCIP * | scip, |
SCIP_LEXREDDATA * | masterdata, | ||
int * | nred, | ||
int * | ncutoff ) |
prints lexicographic reduction propagation data
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
nred | total number of reductions applied |
ncutoff | total number of cutoffs applied |
Definition at line 1871 of file symmetry_lexred.c.
References assert(), VarArrayNodeDepthBranchIndex::masterdata, NULL, and SCIP_OKAY.
Referenced by SCIP_DECL_TABLEOUTPUT().
SCIP_RETCODE SCIPlexicographicReductionPrintStatistics | ( | SCIP * | scip, |
SCIP_LEXREDDATA * | masterdata ) |
prints lexicographic reduction propagation data
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
Definition at line 1889 of file symmetry_lexred.c.
References assert(), i, VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, and SCIPverbMessage().
Referenced by SCIPdisplaySymmetryStatistics().
SCIP_RETCODE SCIPlexicographicReductionPropagate | ( | SCIP * | scip, |
SCIP_LEXREDDATA * | masterdata, | ||
SCIP_Bool * | infeasible, | ||
int * | nred, | ||
SCIP_Bool * | didrun ) |
applies lexicographic reduction propagation
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
infeasible | pointer to store whether infeasibility is found |
nred | pointer to store the number of domain reductions |
didrun | a global pointer maintaining if any symmetry propagator has run only set this to TRUE when a reduction is found, never set to FALSE |
Definition at line 1922 of file symmetry_lexred.c.
References assert(), FALSE, VarArrayNodeDepthBranchIndex::masterdata, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, propagateLexicographicReductionPerm(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPgetFocusNode(), SCIPgetShadowTree(), shadowtreeFillNodeDepthBranchIndices(), shadowtreeUndoNodeDepthBranchIndices(), and TRUE.
Referenced by propagateSymmetry().
SCIP_RETCODE SCIPlexicographicReductionAddPermutation | ( | SCIP * | scip, |
SCIP_LEXREDDATA * | masterdata, | ||
SCIP_VAR ** | permvars, | ||
int | npermvars, | ||
int * | perm, | ||
SYM_SYMTYPE | symtype, | ||
SCIP_Real * | permvardomaincenter, | ||
SCIP_Bool | usedynamicorder, | ||
SCIP_Bool * | success ) |
adds permutation for lexicographic reduction propagation
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
permvars | variable array of the permutation |
npermvars | number of variables in that array |
perm | permutation |
symtype | type of symmetries in perm |
permvardomaincenter | array containing center point for each variable domain |
usedynamicorder | whether a dynamic variable order shall be used |
success | to store whether the component is successfully added |
Definition at line 2033 of file symmetry_lexred.c.
References assert(), FALSE, lexdataCreate(), VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPisTransformed(), SCIPreallocBlockMemoryArray, SYM_SYMTYPE_PERM, and SYM_SYMTYPE_SIGNPERM.
Referenced by addOrbitopesDynamic(), and tryAddOrbitalRedLexRed().
SCIP_RETCODE SCIPlexicographicReductionReset | ( | SCIP * | scip, |
SCIP_LEXREDDATA * | masterdata ) |
resets lexicographic reduction propagation (removes all permutations)
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
Definition at line 2097 of file symmetry_lexred.c.
References assert(), FALSE, lexdataFree(), VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPhashmapFree().
Referenced by resetDynamicSymmetryHandling(), and SCIPlexicographicReductionFree().
SCIP_RETCODE SCIPlexicographicReductionFree | ( | SCIP * | scip, |
SCIP_LEXREDDATA ** | masterdata ) |
frees lexicographic reduction data
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
Definition at line 2135 of file symmetry_lexred.c.
References assert(), VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPlexicographicReductionReset().
Referenced by SCIP_DECL_PROPFREE().
SCIP_RETCODE SCIPincludeLexicographicReduction | ( | SCIP * | scip, |
SCIP_LEXREDDATA ** | masterdata, | ||
SCIP_EVENTHDLR * | shadowtreeeventhdlr ) |
initializes structures needed for lexicographic reduction propagation
This is only done exactly once.
scip | SCIP data structure |
masterdata | pointer to global data for lexicographic reduction propagator |
shadowtreeeventhdlr | pointer to the shadow tree eventhdlr |
Definition at line 2158 of file symmetry_lexred.c.
References assert(), FALSE, VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPcheckStage(), and TRUE.
Referenced by SCIPincludePropSymmetry().