symmetry_orbital.c
Go to the documentation of this file.
32 * The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the
33 * variables globally fixed or branched to 1. Then one can fix all variables in an orbit to 0 or 1 if one of the other
34 * variables in the orbit is fixed to 0 or 1, respectively. This method only works for binary variables.
35 * Margot considers the subgroup that stabilizes the set of one-fixings setwise. We determine a subgroup of this group,
36 * namely the group generated by the given symmetry group component generators, where the generators satisfy the
39 * A generalisation is given in the unified symmetry handling constraint paper, Section 4.3 and 5.1 in [vD,H]:@n
43 * We assume that the provided symmetries (given by a generating permutation set) are symmetries for the problem at the
44 * root node. It is possible that dual (presolving) reductions break this symmetry. As an example, in cons_components.c,
45 * if the problem contains an independent component (i.e., variables are not connected logically by constraints), then
46 * these individual 'components' can be solved. If an optimal solution is easily retrieved, the variables of this
47 * component are fixed, even if symmetrically equivalent solutions exist. Another example is 'stuffing' for linear
51 * (x,y) \in \{0,1\}^{2 + n}\} \f$. Since \f$x_1\f$ and \f$x_2\f$ are independent from the remaining problem, the
52 * setppc constraint handler may fix \f$(x_1,x_2) = (1,0)\f$. However, since both variables are symmetric, this setting
53 * is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would
54 * declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different
57 * We have observed, and assume, that such dual reductions only take place at presolving or in the root node.
58 * So, to avoid this situation, if we detect that a symmetry-breaking reduction is applied at the root node,
59 * we disable orbital fixing for certain generating permutations based on the bounds of the affected global variables,
62 * With the assumption that the symmetries are actual symmetries at the root node, symmetries are broken by the
65 * let \f$\sigma_\beta(x)\f$ be the permuted and restricted vector \f$x\f$ that enumerates the branching variables,
70 * are smaller or equal to the variable domains of the permuted variable. This defines a group (cf. [vD,H, Lemma 22]).
71 * This group is a subgroup of \f$\delta^\beta\f$ of [vD,H, Section 4.3], meaning that the reductions are valid.
75 * - For each orbit of the group, every variable domains can be shrunk to the intersection of all variable domains in
77 * - The domains of the branching variables are upper bounds to the domains of the variables in its orbits.
79 * For orbital fixing, it is crucial that the vectors \f$\sigma_\beta(x)\f$ are the branching variables up to node
80 * \f$\beta\f$ in the given order. Since SCIP can change the tree structure during solving (re-writing history),
81 * we store the original branching decisions at the moment they are made. See event_shadowtree.c .
84/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
122#define EVENTHDLR_SYMMETRY_DESC "filter global variable bound reduction event handler for orbital reduction"
142 SCIP_Bool symmetrybrokencomputed; /**< whether the symmetry broken information is computed already */
143 int* symbrokenvarids; /**< variables to be stabilized because the symmetry is globally broken */
155 SCIP_EVENTHDLR* globalfixeventhdlr; /**< event handler for handling global variable bound reductions */
157 ORCDATA** componentdatas; /**< array of pointers to individual components for orbital reduction */
218 /* no arithmetic is performed on these bounds, so we can compare floats by their value exactly */
233 /* iterate over all orbits and get the maximal orbit lower bound and minimal orbit upper bound */
254 if ( !SCIPsymEQ(scip, orbitglb, orcdata->globalvarlbs[j]) || !SCIPsymEQ(scip, orbitgub, orcdata->globalvarubs[j]) )
263 /* in case we terminated the orbit due to broken symmetries, find the correct end of the orbit */
271 /* symmetry is broken within this orbit if the intersection of the global variable domains are empty */
324 "Orbital fixing symmetry for %p broken before symmetry. Requires fixing %d/%d affected variables.\n",
336/** populates chosenperms with a generating set of the symmetry group stabilizing the branching decisions
338 * The symmetry subgroup considered is generated by all permutations where for all branching variables \f$x\f$
351 SCIP_Bool* inbranchedvarindices, /**< array stating whether variable with index in orcdata->permvars is
395 /* the variables on which symmetry is broken must be permuted to entries with the same fixed value
397 * Because we check a whole orbit of the group and perm is part of it, it suffices to compare the upper bound
398 * of varid with the lower bound of varidimage. Namely, for all indices i, \f$lb_i \leq ub_i\f$, so we get
445/** using bisection, finds the minimal index k (frameleft <= k < frameright) such that ids[idssort[k]] >= findid
447 * If for all k (frameleft <= k < frameright) holds ids[idssort[k]] < findid, returns frameright.
511 * Either use the local variable bounds, or variable bounds determined by the varlbs and varubs arrays.
608 SCIP_CALL( SCIPtightenVarLb(scip, orcdata->permvars[varid], orbitlb, TRUE, infeasible, &tightened) );
626 SCIP_CALL( SCIPtightenVarUb(scip, orcdata->permvars[varid], orbitub, TRUE, infeasible, &tightened) );
715 SCIPwarningMessage(scip, "Attempting orbital reduction on nodes not existing in the symmetry shadowtree"
808 /* determine symmetry group at this point, apply branched variable, apply orbital branching for this
811 * So, the group before branching is determined, orbital branching to the branching variable, then the branching
818 branchingdecisionvarid = SCIPhashmapGetImageInt(orcdata->permvarmap, (void*) branchingdecision->var);
833 * Note: All information about branching decisions is kept in varlbs, varubs, and the branchedvarindices.
835 SCIP_CALL( orbitalReductionGetSymmetryStabilizerSubgroup(scip, orcdata, chosenperms, &nchosenperms,
853 /* 1. ensure that the bounds are tightest possible just before the branching step (orbital reduction step)
919 assert( orbitbegin == 0 || varorbitids[varorbitidssort[orbitbegin - 1]] < orbitsetcomponentid );
921 orbitend = bisectSortedArrayFindFirstGEQ(varorbitids, varorbitidssort, orbitbegin + 1, orcdata->npermvars,
924 assert( orbitend == orcdata->npermvars || varorbitids[varorbitidssort[orbitend]] > orbitsetcomponentid );
942 * due to orbital reduction. If that was not the case, these steps are applied just before applying
943 * the branching step above. After the branching step, the branching variable bounds are most restricted.
949 /* bound changes already made could only have tightened the variable domains we are thinking about */
957 if ( SCIPsymGT(scip, SCIPvarGetUbLocal(orcdata->permvars[varid]), varubs[branchingdecisionvarid]) )
960 SCIP_CALL( SCIPtightenVarUb(scip, orcdata->permvars[varid], varubs[branchingdecisionvarid], TRUE,
970 /* because variable domains are initially the same, the LB of the x-variables does not need to be modified. */
1093 /* 1. compute the orbit of the branching variable of the stabilized symmetry subgroup at this point. */
1096 SCIP_CALL( orbitalReductionGetSymmetryStabilizerSubgroup(scip, orcdata, chosenperms, &nchosenperms,
1128 SCIP_CALL( applyOrbitalReductionPart(scip, orcdata, infeasible, nred, varorbitids, varorbitidssort, NULL, NULL) );
1162 * compute the symmetry group just before branching. Then, for our branching variable x with variable y in its
1165 * In principle, this generalizes orbital branching in the binary case: propagation of x >= y yields
1167 * 0. In the 0-branch: 0 = x >= y implies y = 0. This is an exact description of orbital branching.
1168 * REF: Ostrowski, James, et al. "Orbital branching." Mathematical Programming 126.1 (2011): 147-178.
1173 * The symmetry group in this branch-and-bound tree node is a subgroup of the problem symmetry group
1175 * For this symmetry subgroup, in each orbit, update the variable domains with the intersection of all variable
1265 /* determine the number of vars that are moved by the component, assign to orcdata->npermvars */
1337 assert( newidx < orcdata->npermvars ); /* this is in the orbit of any permutation, so cannot be INT_MAX */
1356 SCIP_CALL( SCIPcatchVarEvent(scip, orcdata->permvars[i], SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED,
1433 SCIPfreeBlockMemoryArrayNull(scip, &(*orcdata)->symbrokenvarids, (*orcdata)->nsymbrokenvarids);
1496 /* identifyOrbitalSymmetriesBroken is only called when we're propagating, which is only done for during solving */
1511 /* can assert with equality, because no arithmetic must be applied after inheriting the value of oldbound */
1573 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%d", orbireddata->componentdatas[i]->nperms);
1686 SCIP_CALL( freeComponent(scip, orbireddata, &(orbireddata->componentdatas[--orbireddata->ncomponents])) );
1721 SCIP_ORBITALREDDATA** orbireddata, /**< pointer to orbital reduction data structure to populate */
1729 SCIP_CALL( SCIPcheckStage(scip, "SCIPincludeOrbitalReduction", 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
void SCIPfreeDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset)
Definition: scip_datastructures.c:669
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11269
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11296
SCIP_RETCODE SCIPcreateDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
Definition: scip_datastructures.c:654
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_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
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
#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_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 SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5538
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
SCIP_Bool symmetrybrokencomputed
Definition: symmetry_orbital.c:142
SCIP_HASHMAP * permvarmap
Definition: symmetry_orbital.c:140
int * symbrokenvarids
Definition: symmetry_orbital.c:143
SCIP_Real * globalvarlbs
Definition: symmetry_orbital.c:134
int nsymbrokenvarids
Definition: symmetry_orbital.c:144
SCIP_Real * globalvarubs
Definition: symmetry_orbital.c:135
SCIP_Bool treewarninggiven
Definition: symmetry_orbital.c:146
Definition: struct_misc.h:278
Definition: struct_event.h:205
Definition: struct_misc.h:138
Definition: struct_tree.h:142
Definition: event_shadowtree.h:57
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
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_RETCODE applyOrbitalReductionPropagations(SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
Definition: symmetry_orbital.c:1021
static SCIP_RETCODE applyOrbitalBranchingPropagations(SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
Definition: symmetry_orbital.c:643
SCIP_RETCODE SCIPorbitalReductionFree(SCIP *scip, SCIP_ORBITALREDDATA **orbireddata)
Definition: symmetry_orbital.c:1699
SCIP_RETCODE SCIPorbitalReductionGetStatistics(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, int *nred, int *ncutoff)
Definition: symmetry_orbital.c:1534
SCIP_RETCODE SCIPincludeOrbitalReduction(SCIP *scip, SCIP_ORBITALREDDATA **orbireddata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
Definition: symmetry_orbital.c:1719
SCIP_RETCODE SCIPorbitalReductionPrintStatistics(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
Definition: symmetry_orbital.c:1551
static SCIP_RETCODE orbitalReductionGetSymmetryStabilizerSubgroup(SCIP *scip, ORCDATA *orcdata, int **chosenperms, int *nchosenperms, SCIP_Real *varlbs, SCIP_Real *varubs, int *branchedvarindices, SCIP_Bool *inbranchedvarindices, int nbranchedvarindices)
Definition: symmetry_orbital.c:343
SCIP_RETCODE SCIPorbitalReductionAddComponent(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
Definition: symmetry_orbital.c:1644
static SCIP_RETCODE applyOrbitalReductionPart(SCIP *scip, ORCDATA *orcdata, SCIP_Bool *infeasible, int *nred, int *varorbitids, int *varorbitidssort, SCIP_Real *varlbs, SCIP_Real *varubs)
Definition: symmetry_orbital.c:515
static SCIP_DECL_EVENTEXEC(eventExecGlobalBoundChange)
Definition: symmetry_orbital.c:1479
SCIP_RETCODE SCIPorbitalReductionReset(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
Definition: symmetry_orbital.c:1672
SCIP_RETCODE SCIPorbitalReductionPropagate(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
Definition: symmetry_orbital.c:1582
static SCIP_RETCODE identifyOrbitalSymmetriesBroken(SCIP *scip, ORCDATA *orcdata)
Definition: symmetry_orbital.c:175
static SCIP_RETCODE orbitalReductionPropagateComponent(SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
Definition: symmetry_orbital.c:1182
static int bisectSortedArrayFindFirstGEQ(int *ids, int *idssort, int frameleft, int frameright, int findid)
Definition: symmetry_orbital.c:450
static SCIP_RETCODE freeComponent(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, ORCDATA **orcdata)
Definition: symmetry_orbital.c:1405
static SCIP_RETCODE addComponent(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
Definition: symmetry_orbital.c:1233
struct SCIP_OrbitalReductionData SCIP_ORBITALREDDATA
Definition: symmetry_orbital.h:52
type definitions for problem variables