symmetry_lexred.c
Go to the documentation of this file.
30 * This implements lexicographic reduction, which generalizes symresack propagation to work for non-binary variable
31 * domains, and is dynamified. Whereas static lexicographic reduction propagates that a vector \f$x\f$ is
32 * lexicographically larger than its permuted counterpart (i.e., \f$x \succeq \gamma(x)\f$ with \f$\succeq\f$ being
33 * standard elementwise lexicographic comparison), the dynamic variant determines the variable vector ordering
34 * dynamically. Just as in orbital reduction (cf. symmetry_orbital.c), the variable order is chosen as the variables
37 * where \f$\sigma_\beta(\cdot)\f$ permutes and restricts the variable vector such that it corresponds to the branched
44 * For dynamic lexicographic reduction, it is crucial that the vectors \f$\sigma_\beta(x)\f$ are the branching
45 * variables up to node \f$\beta\f$ in the given order. Since SCIP can change the tree structure during solving
46 * (re-writing history), we store the original branching decisions at the moment they are made. See event_shadowtree.c .
49/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
107 SCIP_HASHMAP* symvarmap; /**< map of variables affected by some permutation handled by a LEXDATA */
114 SCIP_Bool hasdynamicperm; /**< whether there exists a permutation that is treated dynamically */
119/** to store branch-and-bound tree paths, (depth, index)-information per variable in rooted path */
131 NODEDEPTHBRANCHINDEX* nodedepthbranchindices; /**< pointer to branch-and-bound tree information */
132 SCIP_LEXREDDATA* masterdata; /**< pointer to global data for lexicographic reduction propagator */
224 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
323 assert( (*lexdata)->nvars <= (*lexdata)->perm[i] && (*lexdata)->perm[i] < 2 * (*lexdata)->nvars );
363 /* make sure that we deal with transformed variables and that variables cannot be multi-aggregated, and capture */
408/** comparator used in the getVarOrder() function, for sorting an array of NODEDEPTHBRANCHINDEX by depth, then by index
418 * -1: the depth of ind1 is smaller than the depth of ind2, or it's equal and the index is smaller
419 * 1: the depth of ind2 is smaller than the depth of ind1, or it's equal and the index is smaller
483 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
485 NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array with (depth, index)-information per variable in rooted path to focus node */
487 SCIP_VAR** branchvars, /**< array populated with variables branched on in the symvarmap hashset */
546 /* for permutations where the support is larger than the number of branched vars, check for the branched vars */
576 /* sort the first n elements of varorder by depth, then by index, as indicated by nodedepthbranchindices. */
581 SCIPsortInd(varorder, sortbynodedepthbranchindices, (void*) &vararraynodedepthbranchindices, *nselvars);
671 SCIP_CALL_ABORT( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
718 SCIP_CALL_ABORT( getVarBounds(var1, var2, peekmode, varidx1, varidx2, peeklbs, peekubs, peekbdset,
1055 SCIP_CALL( propagateSelfReflectionVar(scip, var1, center1, infeasible, nreductions, peekmode, varidx1,
1060 SCIP_CALL( propagateLowerBoundVar(scip, var1, var2, center1, center2, isnegated, infeasible, nreductions, peekmode,
1065 SCIP_CALL( propagateUpperBoundSymVar(scip, var1, var2, center1, center2, isnegated, infeasible, nreductions, peekmode,
1072/** checks if the static lexred with a certain variable ordering is feasible in the hypothetical scenario where
1179 /* vari >= varj can never hold if the maximal value of vari is smaller than the minimal value of varj */
1180 if ( alwaysLTshiftedVars(scip, vari, varj, centeri, centerj, isnegated, TRUE, i, j, peeklbs, peekubs, peekbdset) )
1187 SCIP_CALL( propagateLowerBoundVar(scip, vari, varj, centeri, centerj, isnegated, &infeasible, &nreductions, TRUE,
1190 SCIP_CALL( propagateUpperBoundSymVar(scip, vari, varj, centeri, centerj, isnegated, &infeasible, &nreductions, TRUE,
1284 SCIP_CALL( propagateVariablePair(scip, vari, varj, centeri, centerj, isnegated, infeasible, nreductions, FALSE,
1290 /* terminate if there exists a solution being lexicographically strictly larger than its image */
1300 /* if the variables in "row" are fixed to the same value, we might find further propagations */
1322 assert( SCIPsymGE(scip, lb1, lexdata->vardomaincenter[i]) ); /* propagation enforces xi - center >= center - xi */
1337 /* both variables cannot be the same, so the non-negated variable must be greater than the domain center */
1344 SCIP_CALL( SCIPtightenVarLb(scip, vari, lexdata->vardomaincenter[i] + 1.0, TRUE, infeasible, &success) );
1363 SCIPerrorMessage("unsupported variable type encountered at the lexicographic reduction propagator\n");
1382 * If it turns out infeasible, then we know vari cannot take value lbi, so we can increase the lower bound.
1430 /* vari cannot take value lb1, so we increase the lower bound. (do not use lbi as this is a shifted domain bound) */
1457 SCIPerrorMessage("unsupported variable type encountered at the lexicographic reduction propagator\n");
1467 * If it turns out infeasible, then we know varj cannot take value ubj, so we can decrease the upper bound.
1469 assert( SCIPsymGE(scip, ubi, ubj) ); /* this must be the case after reductions in the for-loop */
1485 /* varj cannot take value ub2, so we decrease the upper or lower bound. (do not use ubj as this is a shifted domain bound)*/
1538 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1540 NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array with (depth, index)-information per variable in rooted path to focus node */
1568 SCIP_CALL( getVarOrder(scip, masterdata, lexdata, nodedepthbranchindices, nvarstotal, branchvars, nbranchvars,
1576 SCIP_CALL( propagateStaticLexred(scip, lexdata, varorder, nvarorder, infeasible, nreductions) );
1588 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1606 SCIP_CALL( propagateStaticLexred(scip, lexdata, NULL, lexdata->nvars, infeasible, nreductions) );
1616 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1618 NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array with (depth, index)-information per variable in rooted path to focus node */
1659 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1696 SCIPwarningMessage(scip, "Attempting lexicographic reduction on nodes not existing in the symmetry shadowtree"
1710 /* Now, walk from the leaf to the root. Each time look at all the children of the node considered,
1711 * and save the variable depth and index in the branching array. It is important to consider all children each time,
1712 * because we need to comply with the instance where in different branches it is branched on different variables.
1723 /* get the variables branched on, for each of the children (that's likely 1 variable each time) */
1742 /* the variable is either not seen (nodedepth == 0), or it is at a higher level (nodedepth > shadowdepth) */
1763 /* In the last iteration, we handled the branching decisions at the root node, so shadowdepth must have value 0. */
1775 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1776 NODEDEPTHBRANCHINDEX* nodedepthbranchindices, /**< array populated by nodedepthbranchindices to clean */
1783 /* undo the operations from shadowtreeFillNodeDepthBranchIndices, which makes nodedepthbranchindices clean */
1820 /* now, walk from the leaf to the root. Each time look at all the children of the node considered,
1821 * and save the variable depth and index in the branching array. It is important to consider all children each time,
1822 * because we need to comply with the instance where in different branches it is branched on different variables.
1833 /* get the variables branched on, for each of the children (that's likely 1 variable each time) */
1858 /* In the last iteration, we handled the branching decisions at the root node, so shadowdepth must have value 0. */
1873 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1891 SCIP_LEXREDDATA* masterdata /**< pointer to global data for lexicographic reduction propagator */
1901 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " lexicographic reduction: no permutations\n");
1905 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " lexicographic reduction: %4d permutations with support sizes ",
1924 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
1967 * this is an array that maps every variable index to (depth, index) = (0, 0) if the variable is not branched on,
1968 * or (depth, index) is the depth (branching at root node: depth 1) and variable index when it was branched thereon.
1978 /* if the information cannot be resolved because a node is missing from the shadowtree, do not propagate */
1997 nodedepthbranchindices, masterdata->nsymvars, branchvars, nbranchvars, infeasible, &nlocalred) );
2035 SCIP_LEXREDDATA* masterdata, /**< pointer to global data for lexicographic reduction propagator */
2099 SCIP_LEXREDDATA* masterdata /**< pointer to global data for lexicographic reduction propagator */
2137 SCIP_LEXREDDATA** masterdata /**< pointer to global data for lexicographic reduction propagator */
2160 SCIP_LEXREDDATA** masterdata, /**< pointer to global data for lexicographic reduction propagator */
2168 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeLexicographicReduction", TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE,
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2208
methods for debugging
SCIP_RETCODE SCIPactivateShadowTree(SCIP *scip, SCIP_EVENTHDLR *eventhdlr)
Definition: event_shadowtree.c:639
SCIP_SHADOWTREE * SCIPgetShadowTree(SCIP_EVENTHDLR *eventhdlr)
Definition: event_shadowtree.c:624
SCIP_SHADOWNODE * SCIPshadowTreeGetShadowNode(SCIP_SHADOWTREE *shadowtree, SCIP_NODE *node)
Definition: event_shadowtree.c:158
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8715
void SCIPsortInd(int *indarray, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
memory allocation routines
Definition: objbenders.h:44
public methods for managing constraints
public methods for message output
public methods for problem variables
SCIP callable library.
public methods for branching rule plugins and branching
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for SCIP variables
Definition: symmetry_lexred.c:90
Definition: symmetry_lexred.c:121
Definition: struct_event.h:205
Definition: struct_misc.h:138
Definition: struct_tree.h:142
Definition: event_shadowtree.h:66
SCIP_SHADOWBOUNDUPDATE * branchingdecisions
Definition: event_shadowtree.h:72
Definition: event_shadowtree.h:85
Definition: struct_var.h:208
Definition: struct_scip.h:70
NODEDEPTHBRANCHINDEX * nodedepthbranchindices
Definition: symmetry_lexred.c:131
SCIP_LEXREDDATA * masterdata
Definition: symmetry_lexred.c:132
datastructures for block memory pools and memory buffers
SCIP main data structure.
data structures for branch and bound tree
datastructures for problem variables
methods for handling symmetries
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)
Definition: symmetry_lexred.c:691
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)
Definition: symmetry_lexred.c:735
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)
Definition: symmetry_lexred.c:1003
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)
Definition: symmetry_lexred.c:1536
SCIP_RETCODE SCIPlexicographicReductionPropagate(SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
Definition: symmetry_lexred.c:1922
static SCIP_DECL_SORTINDCOMP(sortbynodedepthbranchindices)
Definition: symmetry_lexred.c:422
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)
Definition: symmetry_lexred.c:644
SCIP_RETCODE SCIPlexicographicReductionGetStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata, int *nred, int *ncutoff)
Definition: symmetry_lexred.c:1871
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)
Definition: symmetry_lexred.c:1076
SCIP_RETCODE SCIPlexicographicReductionReset(SCIP *scip, SCIP_LEXREDDATA *masterdata)
Definition: symmetry_lexred.c:2097
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)
Definition: symmetry_lexred.c:822
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)
Definition: symmetry_lexred.c:590
SCIP_RETCODE SCIPlexicographicReductionPrintStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata)
Definition: symmetry_lexred.c:1889
static SCIP_RETCODE propagateLexredStatic(SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, SCIP_Bool *infeasible, int *nreductions)
Definition: symmetry_lexred.c:1586
static SCIP_RETCODE lexdataFree(SCIP *scip, LEXDATA **lexdata)
Definition: symmetry_lexred.c:144
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)
Definition: symmetry_lexred.c:481
static SCIP_RETCODE shadowtreeUndoNodeDepthBranchIndices(SCIP *scip, SCIP_LEXREDDATA *masterdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, SCIP_VAR **branchvars, int *nbranchvars, SCIP_SHADOWTREE *shadowtree, SCIP_NODE *focusnode)
Definition: symmetry_lexred.c:1773
SCIP_RETCODE SCIPlexicographicReductionFree(SCIP *scip, SCIP_LEXREDDATA **masterdata)
Definition: symmetry_lexred.c:2135
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)
Definition: symmetry_lexred.c:1614
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)
Definition: symmetry_lexred.c:2033
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)
Definition: symmetry_lexred.c:932
static SCIP_RETCODE propagateStaticLexred(SCIP *scip, LEXDATA *lexdata, int *varorder, int nselvars, SCIP_Bool *infeasible, int *nreductions)
Definition: symmetry_lexred.c:1204
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)
Definition: symmetry_lexred.c:1657
SCIP_RETCODE SCIPincludeLexicographicReduction(SCIP *scip, SCIP_LEXREDDATA **masterdata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
Definition: symmetry_lexred.c:2158
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)
Definition: symmetry_lexred.c:222
static int varOrderGetIndex(int *varorder, int pos)
Definition: symmetry_lexred.c:466
methods for handling symmetries by dynamic lexicographic ordering reduction
type definitions for problem variables