Detailed Description
methods for handling symmetries by orbital reduction
methods for handling symmetries based on orbits
Orbital fixing is introduced by
F. Margot: Exploiting orbits in symmetric ILP. Math. Program., 98(1-3):3–21, 2003. The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the 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 variables in the orbit is fixed to 0 or 1, respectively. This method only works for binary variables. Margot considers the subgroup that stabilizes the set of one-fixings setwise. We determine a subgroup of this group, namely the group generated by the given symmetry group component generators, where the generators satisfy the stabilization condition.
A generalisation is given in the unified symmetry handling constraint paper, Section 4.3 and 5.1 in [vD,H]:
J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023, https://doi.org/10.48550/arXiv.2211.01295.
We assume that the provided symmetries (given by a generating permutation set) are symmetries for the problem at the root node. It is possible that dual (presolving) reductions break this symmetry. As an example, in cons_components.c, if the problem contains an independent component (i.e., variables are not connected logically by constraints), then these individual 'components' can be solved. If an optimal solution is easily retrieved, the variables of this component are fixed, even if symmetrically equivalent solutions exist. Another example is 'stuffing' for linear constraints.
To illustrate this, consider the example \(\max\{x_1 + x_2 : x_1 + x_2 \leq 1, Ay \leq b, (x,y) \in \{0,1\}^{2 + n}\} \). Since \(x_1\) and \(x_2\) are independent from the remaining problem, the setppc constraint handler may fix \((x_1,x_2) = (1,0)\). However, since both variables are symmetric, this setting is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different values).
We have observed, and assume, that such dual reductions only take place at presolving or in the root node. So, to avoid this situation, if we detect that a symmetry-breaking reduction is applied at the root node, we disable orbital fixing for certain generating permutations based on the bounds of the affected global variables, see identifyOrbitalSymmetriesBroken.
With the assumption that the symmetries are actual symmetries at the root node, symmetries are broken by the branching decisions. For a branch-and-bound tree node \(\beta\) and variable vector \(x\), let \(\sigma_\beta(x)\) be the permuted and restricted vector \(x\) that enumerates the branching variables, following the path of the root node to \(\beta\) (cf., Example 11 in [vD,H]). Consider a component of the symmetry group, given by a set of generating permutations. Of this set, we select these permutations (not disabled by identifyOrbitalSymmetriesBroken) for which te variable domains of the branched variables \(\sigma_\beta(x)\) are smaller or equal to the variable domains of the permuted variable. This defines a group (cf. [vD,H, Lemma 22]). This group is a subgroup of \(\delta^\beta\) of [vD,H, Section 4.3], meaning that the reductions are valid.
The reductions are:
- For each orbit of the group, every variable domains can be shrunk to the intersection of all variable domains in the orbit.
- The domains of the branching variables are upper bounds to the domains of the variables in its orbits.
For orbital fixing, 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_orbital.c.
#include "blockmemshell/memory.h"
#include "scip/symmetry_orbital.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 <ctype.h>
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | OrbitalReductionComponentData |
Macros | |
#define | EVENTHDLR_SYMMETRY_NAME "symmetry_orbital" |
#define | EVENTHDLR_SYMMETRY_DESC "filter global variable bound reduction event handler for orbital reduction" |
Typedefs | |
typedef struct OrbitalReductionComponentData | ORCDATA |
Macro Definition Documentation
◆ EVENTHDLR_SYMMETRY_NAME
#define EVENTHDLR_SYMMETRY_NAME "symmetry_orbital" |
Definition at line 121 of file symmetry_orbital.c.
◆ EVENTHDLR_SYMMETRY_DESC
#define EVENTHDLR_SYMMETRY_DESC "filter global variable bound reduction event handler for orbital reduction" |
Definition at line 122 of file symmetry_orbital.c.
Typedef Documentation
◆ ORCDATA
typedef struct OrbitalReductionComponentData ORCDATA |
Definition at line 148 of file symmetry_orbital.c.
Function Documentation
◆ identifyOrbitalSymmetriesBroken()
|
static |
identifies the orbits at which symmetry is broken according to the global bounds
An example of a symmetry-breaking constraint is cons_components.
- Parameters
-
scip pointer to SCIP data structure orcdata pointer to data for orbital reduction data
Definition at line 175 of file symmetry_orbital.c.
References FALSE, OrbitalReductionComponentData::globalvarlbs, OrbitalReductionComponentData::globalvarubs, OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::npermvars, OrbitalReductionComponentData::nsymbrokenvarids, NULL, OrbitalReductionComponentData::perms, OrbitalReductionComponentData::permvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPfreeDisjointset(), SCIPreallocBlockMemoryArray, SCIPsort(), SCIPsymEQ(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), OrbitalReductionComponentData::symbrokenvarids, OrbitalReductionComponentData::symmetrybrokencomputed, and TRUE.
Referenced by orbitalReductionPropagateComponent().
◆ orbitalReductionGetSymmetryStabilizerSubgroup()
|
static |
populates chosenperms with a generating set of the symmetry group stabilizing the branching decisions
The symmetry subgroup considered is generated by all permutations where for all branching variables \(x\) with permuted variable \(y\) for all possible variable assignments we have \(x \leq y\). We restrict ourselves to testing this only for the group generators.
- Parameters
-
scip pointer to SCIP data structure orcdata pointer to data for orbital reduction data chosenperms pointer to permutations that are chosen nchosenperms pointer to store the number of chosen permutations varlbs array of orcdata->permvars variable LBs. If NULL, use local bounds varubs array of orcdata->permvars variable UBs. If NULL, use local bounds branchedvarindices array of given branching decisions, in branching order inbranchedvarindices array stating whether variable with index in orcdata->permvars is contained in the branching decisions. nbranchedvarindices number of branching decisions
Definition at line 343 of file symmetry_orbital.c.
References OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::nsymbrokenvarids, NULL, OrbitalReductionComponentData::perms, OrbitalReductionComponentData::permvars, SCIP_OKAY, SCIPsymEQ(), SCIPsymGT(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), OrbitalReductionComponentData::symbrokenvarids, and OrbitalReductionComponentData::symmetrybrokencomputed.
Referenced by applyOrbitalBranchingPropagations(), and applyOrbitalReductionPropagations().
◆ bisectSortedArrayFindFirstGEQ()
|
static |
using bisection, finds the minimal index k (frameleft <= k < frameright) such that ids[idssort[k]] >= findid
If for all k (frameleft <= k < frameright) holds ids[idssort[k]] < findid, returns frameright.
- Parameters
-
ids int array with entries idssort array of indices of ids that sort ids frameleft search in idssort for index range [frameleft, frameright) frameright search in idssort for index range [frameleft, frameright) findid entry value to find
Definition at line 450 of file symmetry_orbital.c.
References NULL.
Referenced by applyOrbitalBranchingPropagations().
◆ applyOrbitalReductionPart()
|
static |
applies the orbital reduction steps for precomputed orbits
Either use the local variable bounds, or variable bounds determined by the varlbs and varubs arrays.
- Precondition
- varubs is NULL if and only if varlbs is NULL.
- Parameters
-
scip pointer to SCIP data structure orcdata pointer to data for orbital reduction data infeasible pointer to store whether infeasibility is detected nred pointer to store the number of determined domain reductions varorbitids array specifying the orbit IDs for variables in array orcdata->vars varorbitidssort an index array that sorts the varorbitids array varlbs array of lower bounds for variable array orcdata->vars to compute with or NULL, if local bounds are used varubs array of upper bounds for variable array orcdata->vars to compute with or NULL, if local bounds are used.
Definition at line 515 of file symmetry_orbital.c.
References OrbitalReductionComponentData::npermvars, NULL, OrbitalReductionComponentData::permvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisInfinity(), SCIPsymGE(), SCIPsymGT(), SCIPsymLE(), SCIPsymLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by applyOrbitalBranchingPropagations(), and applyOrbitalReductionPropagations().
◆ applyOrbitalBranchingPropagations()
|
static |
orbital reduction, the orbital branching part
- Parameters
-
scip pointer to SCIP data structure orcdata pointer to data for orbital reduction data shadowtree pointer to shadow tree infeasible pointer to store whether infeasibility is detected nred pointer to store the number of determined domain reductions
Definition at line 643 of file symmetry_orbital.c.
References applyOrbitalReductionPart(), bisectSortedArrayFindFirstGEQ(), SCIP_ShadowBoundUpdate::boundchgtype, SCIP_ShadowNode::branchingdecisions, FALSE, OrbitalReductionComponentData::globalvarlbs, OrbitalReductionComponentData::globalvarubs, OrbitalReductionComponentData::lastnode, SCIP_ShadowNode::nbranchingdecisions, SCIP_ShadowBoundUpdate::newbound, OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::npermvars, SCIP_ShadowNode::npropagations, NULL, orbitalReductionGetSymmetryStabilizerSubgroup(), SCIP_ShadowNode::parent, OrbitalReductionComponentData::permvarmap, OrbitalReductionComponentData::permvars, SCIP_ShadowNode::propagations, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPfreeDisjointset(), SCIPgetCurrentNode(), SCIPgetFocusNode(), SCIPhashmapGetImageInt(), SCIPisInfinity(), SCIPnodeGetParent(), SCIPshadowTreeGetShadowNode(), SCIPsort(), SCIPsymGE(), SCIPsymGT(), SCIPsymLE(), SCIPsymLT(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPwarningMessage(), OrbitalReductionComponentData::treewarninggiven, TRUE, and SCIP_ShadowBoundUpdate::var.
Referenced by orbitalReductionPropagateComponent().
◆ applyOrbitalReductionPropagations()
|
static |
orbital reduction, the orbital reduction part
- Parameters
-
scip pointer to SCIP data structure orcdata pointer to data for orbital reduction data shadowtree pointer to shadow tree infeasible pointer to store whether infeasibility is detected nred pointer to store the number of determined domain reductions
Definition at line 1021 of file symmetry_orbital.c.
References applyOrbitalReductionPart(), SCIP_ShadowNode::branchingdecisions, FALSE, SCIP_ShadowNode::nbranchingdecisions, OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::npermvars, NULL, orbitalReductionGetSymmetryStabilizerSubgroup(), SCIP_ShadowNode::parent, OrbitalReductionComponentData::permvarmap, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPfreeDisjointset(), SCIPgetCurrentNode(), SCIPgetFocusNode(), SCIPhashmapGetImageInt(), SCIPshadowTreeGetShadowNode(), SCIPsort(), TRUE, and SCIP_ShadowBoundUpdate::var.
Referenced by orbitalReductionPropagateComponent().
◆ orbitalReductionPropagateComponent()
|
static |
applies orbital reduction on a symmetry group component using a two step mechanism
At the parent of our focus node (which is the current node, because we're not probing), compute the symmetry group just before branching. Then, for our branching variable x with variable y in its orbit, we mimic adding the constraint x >= y by variable bound propagations in this node.
In principle, this generalizes orbital branching in the binary case: propagation of x >= y yields
- In the 1-branch: 1 = x >= y is a tautology (since y is in {0, 1}). Nothing happens. 0. In the 0-branch: 0 = x >= y implies y = 0. This is an exact description of orbital branching. REF: Ostrowski, James, et al. "Orbital branching." Mathematical Programming 126.1 (2011): 147-178.
(This only needs to be done once per node.)
At the focus node itself, compute the symmetry group. The symmetry group in this branch-and-bound tree node is a subgroup of the problem symmetry group as described in the function orbitalReductionGetSymmetryStabilizerSubgroup. For this symmetry subgroup, in each orbit, update the variable domains with the intersection of all variable domains in the orbit.
This generalizes orbital fixing in the binary case. REF: Margot 2002, Margot 2003, Orbital Branching, Ostrowski's PhD thesis.
- Parameters
-
scip SCIP data structure orcdata orbital reduction component data shadowtree pointer to shadow tree infeasible pointer to store whether infeasibility is found nred pointer to store the number of domain reductions
Definition at line 1182 of file symmetry_orbital.c.
References applyOrbitalBranchingPropagations(), applyOrbitalReductionPropagations(), identifyOrbitalSymmetriesBroken(), OrbitalReductionComponentData::npermvars, OrbitalReductionComponentData::nsymbrokenvarids, NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPgetNNodes(), SCIPgetStage(), and OrbitalReductionComponentData::symmetrybrokencomputed.
Referenced by SCIPorbitalReductionPropagate().
◆ addComponent()
|
static |
adds component
- Parameters
-
scip SCIP data structure orbireddata pointer to the orbital reduction data permvars variable array of the permutation npermvars number of variables in that array perms permutations in the component nperms number of permutations in the component success to store whether the component is successfully added
Definition at line 1233 of file symmetry_orbital.c.
References FALSE, OrbitalReductionComponentData::globalvarlbs, OrbitalReductionComponentData::globalvarubs, OrbitalReductionComponentData::lastnode, OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::npermvars, OrbitalReductionComponentData::nsymbrokenvarids, NULL, OrbitalReductionComponentData::perms, OrbitalReductionComponentData::permvarmap, OrbitalReductionComponentData::permvars, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIPactivateShadowTree(), SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPcaptureVar(), SCIPcatchVarEvent(), SCIPfreeBlockMemory, SCIPhashmapCreate(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPmarkDoNotMultaggrVar(), SCIPreallocBlockMemoryArray, SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), OrbitalReductionComponentData::symbrokenvarids, OrbitalReductionComponentData::symmetrybrokencomputed, OrbitalReductionComponentData::treewarninggiven, and TRUE.
Referenced by SCIPorbitalReductionAddComponent().
◆ freeComponent()
|
static |
frees component
- Parameters
-
scip SCIP data structure orbireddata pointer to the orbital reduction data orcdata pointer to component data
Definition at line 1405 of file symmetry_orbital.c.
References NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_STAGE_FREE, SCIPdropVarEvent(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetStage(), SCIPhashmapFree(), SCIPisTransformed(), and SCIPreleaseVar().
Referenced by SCIPorbitalReductionReset().
◆ SCIP_DECL_EVENTEXEC()
|
static |
maintains global variable bound reductions found during presolving or at the root node
Definition at line 1479 of file symmetry_orbital.c.
References EVENTHDLR_SYMMETRY_NAME, OrbitalReductionComponentData::globalvarlbs, OrbitalReductionComponentData::globalvarubs, NULL, OrbitalReductionComponentData::permvarmap, SCIP_ERROR, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPABORT, SCIPeventGetNewbound(), SCIPeventGetOldbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetName(), SCIPgetNNodes(), SCIPgetStage(), SCIPhashmapGetImageInt(), SCIPvarIsTransformed(), and OrbitalReductionComponentData::symmetrybrokencomputed.
◆ SCIPorbitalReductionGetStatistics()
SCIP_RETCODE SCIPorbitalReductionGetStatistics | ( | SCIP * | scip, |
SCIP_ORBITALREDDATA * | orbireddata, | ||
int * | nred, | ||
int * | ncutoff | ||
) |
prints orbital reduction data
- Parameters
-
scip SCIP data structure orbireddata orbital reduction data structure nred pointer to store the total number of reductions applied ncutoff pointer to store the total number of cutoffs applied
Definition at line 1534 of file symmetry_orbital.c.
References NULL, and SCIP_OKAY.
Referenced by SCIP_DECL_TABLEOUTPUT().
◆ SCIPorbitalReductionPrintStatistics()
SCIP_RETCODE SCIPorbitalReductionPrintStatistics | ( | SCIP * | scip, |
SCIP_ORBITALREDDATA * | orbireddata | ||
) |
prints orbital reduction data
- Parameters
-
scip SCIP data structure orbireddata orbital reduction data structure
Definition at line 1551 of file symmetry_orbital.c.
References NULL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, and SCIPverbMessage().
Referenced by SCIPdisplaySymmetryStatistics().
◆ SCIPorbitalReductionPropagate()
SCIP_RETCODE SCIPorbitalReductionPropagate | ( | SCIP * | scip, |
SCIP_ORBITALREDDATA * | orbireddata, | ||
SCIP_Bool * | infeasible, | ||
int * | nred, | ||
SCIP_Bool * | didrun | ||
) |
propagates orbital reduction
- Parameters
-
scip SCIP data structure orbireddata orbital reduction data structure 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 1582 of file symmetry_orbital.c.
References FALSE, OrbitalReductionComponentData::nperms, NULL, orbitalReductionPropagateComponent(), SCIP_CALL, SCIP_OKAY, SCIPgetShadowTree(), SCIPinProbing(), SCIPinRepropagation(), and TRUE.
Referenced by propagateSymmetry().
◆ SCIPorbitalReductionAddComponent()
SCIP_RETCODE SCIPorbitalReductionAddComponent | ( | SCIP * | scip, |
SCIP_ORBITALREDDATA * | orbireddata, | ||
SCIP_VAR ** | permvars, | ||
int | npermvars, | ||
int ** | perms, | ||
int | nperms, | ||
SCIP_Bool * | success | ||
) |
adds component for orbital reduction
- Parameters
-
scip SCIP data structure orbireddata orbital reduction data structure permvars variable array of the permutation npermvars number of variables in that array perms permutations in the component nperms number of permutations in the component success to store whether the component is successfully added
Definition at line 1644 of file symmetry_orbital.c.
References addComponent(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPisTransformed().
Referenced by tryAddOrbitalRedLexRed().
◆ SCIPorbitalReductionReset()
SCIP_RETCODE SCIPorbitalReductionReset | ( | SCIP * | scip, |
SCIP_ORBITALREDDATA * | orbireddata | ||
) |
resets orbital reduction data structure (clears all components)
- Parameters
-
scip SCIP data structure orbireddata orbital reduction data structure
Definition at line 1672 of file symmetry_orbital.c.
References freeComponent(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPfreeBlockMemoryArrayNull.
Referenced by resetDynamicSymmetryHandling(), and SCIPorbitalReductionFree().
◆ SCIPorbitalReductionFree()
SCIP_RETCODE SCIPorbitalReductionFree | ( | SCIP * | scip, |
SCIP_ORBITALREDDATA ** | orbireddata | ||
) |
frees orbital reduction data
- Parameters
-
scip SCIP data structure orbireddata orbital reduction data structure
Definition at line 1699 of file symmetry_orbital.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPorbitalReductionReset().
Referenced by SCIP_DECL_PROPFREE().
◆ SCIPincludeOrbitalReduction()
SCIP_RETCODE SCIPincludeOrbitalReduction | ( | SCIP * | scip, |
SCIP_ORBITALREDDATA ** | orbireddata, | ||
SCIP_EVENTHDLR * | shadowtreeeventhdlr | ||
) |
initializes structures needed for orbital reduction
This is only done exactly once.
- Parameters
-
scip SCIP data structure orbireddata pointer to orbital reduction data structure to populate shadowtreeeventhdlr pointer to the shadow tree eventhdlr
Definition at line 1719 of file symmetry_orbital.c.
References EVENTHDLR_SYMMETRY_DESC, EVENTHDLR_SYMMETRY_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPcheckStage(), SCIPincludeEventhdlrBasic(), and TRUE.
Referenced by SCIPincludePropSymmetry().