Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

methods for handling symmetries by orbital reduction

methods for handling symmetries based on orbits

Author
Jasper van Doornmalen

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 .

Author
Jasper van Doornmalen

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
 

Functions

static SCIP_RETCODE identifyOrbitalSymmetriesBroken (SCIP *scip, ORCDATA *orcdata)
 
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)
 
static int bisectSortedArrayFindFirstGEQ (int *ids, int *idssort, int frameleft, int frameright, int findid)
 
static SCIP_RETCODE applyOrbitalReductionPart (SCIP *scip, ORCDATA *orcdata, SCIP_Bool *infeasible, int *nred, int *varorbitids, int *varorbitidssort, SCIP_Real *varlbs, SCIP_Real *varubs)
 
static SCIP_RETCODE applyOrbitalBranchingPropagations (SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
 
static SCIP_RETCODE applyOrbitalReductionPropagations (SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
 
static SCIP_RETCODE orbitalReductionPropagateComponent (SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
 
static SCIP_RETCODE addComponent (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
 
static SCIP_RETCODE freeComponent (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, ORCDATA **orcdata)
 
static SCIP_DECL_EVENTEXEC (eventExecGlobalBoundChange)
 
SCIP_RETCODE SCIPorbitalReductionGetStatistics (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, int *nred, int *ncutoff)
 
SCIP_RETCODE SCIPorbitalReductionPrintStatistics (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
 
SCIP_RETCODE SCIPorbitalReductionPropagate (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
 
SCIP_RETCODE SCIPorbitalReductionAddComponent (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
 
SCIP_RETCODE SCIPorbitalReductionReset (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
 
SCIP_RETCODE SCIPorbitalReductionFree (SCIP *scip, SCIP_ORBITALREDDATA **orbireddata)
 
SCIP_RETCODE SCIPincludeOrbitalReduction (SCIP *scip, SCIP_ORBITALREDDATA **orbireddata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
 

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

Definition at line 148 of file symmetry_orbital.c.

Function Documentation

◆ identifyOrbitalSymmetriesBroken()

◆ orbitalReductionGetSymmetryStabilizerSubgroup()

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 
)
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
scippointer to SCIP data structure
orcdatapointer to data for orbital reduction data
chosenpermspointer to permutations that are chosen
nchosenpermspointer to store the number of chosen permutations
varlbsarray of orcdata->permvars variable LBs. If NULL, use local bounds
varubsarray of orcdata->permvars variable UBs. If NULL, use local bounds
branchedvarindicesarray of given branching decisions, in branching order
inbranchedvarindicesarray stating whether variable with index in orcdata->permvars is contained in the branching decisions.
nbranchedvarindicesnumber 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 int bisectSortedArrayFindFirstGEQ ( int *  ids,
int *  idssort,
int  frameleft,
int  frameright,
int  findid 
)
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
idsint array with entries
idssortarray of indices of ids that sort ids
frameleftsearch in idssort for index range [frameleft, frameright)
framerightsearch in idssort for index range [frameleft, frameright)
findidentry value to find

Definition at line 450 of file symmetry_orbital.c.

References NULL.

Referenced by applyOrbitalBranchingPropagations().

◆ applyOrbitalReductionPart()

static SCIP_RETCODE applyOrbitalReductionPart ( SCIP scip,
ORCDATA orcdata,
SCIP_Bool infeasible,
int *  nred,
int *  varorbitids,
int *  varorbitidssort,
SCIP_Real varlbs,
SCIP_Real varubs 
)
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
scippointer to SCIP data structure
orcdatapointer to data for orbital reduction data
infeasiblepointer to store whether infeasibility is detected
nredpointer to store the number of determined domain reductions
varorbitidsarray specifying the orbit IDs for variables in array orcdata->vars
varorbitidssortan index array that sorts the varorbitids array
varlbsarray of lower bounds for variable array orcdata->vars to compute with or NULL, if local bounds are used
varubsarray 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 SCIP_RETCODE applyOrbitalBranchingPropagations ( SCIP scip,
ORCDATA orcdata,
SCIP_SHADOWTREE shadowtree,
SCIP_Bool infeasible,
int *  nred 
)
static

orbital reduction, the orbital branching part

Parameters
scippointer to SCIP data structure
orcdatapointer to data for orbital reduction data
shadowtreepointer to shadow tree
infeasiblepointer to store whether infeasibility is detected
nredpointer 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 SCIP_RETCODE applyOrbitalReductionPropagations ( SCIP scip,
ORCDATA orcdata,
SCIP_SHADOWTREE shadowtree,
SCIP_Bool infeasible,
int *  nred 
)
static

◆ orbitalReductionPropagateComponent()

static SCIP_RETCODE orbitalReductionPropagateComponent ( SCIP scip,
ORCDATA orcdata,
SCIP_SHADOWTREE shadowtree,
SCIP_Bool infeasible,
int *  nred 
)
static

applies orbital reduction on a symmetry group component using a two step mechanism

  1. 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

    1. 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.)

  2. 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
scipSCIP data structure
orcdataorbital reduction component data
shadowtreepointer to shadow tree
infeasiblepointer to store whether infeasibility is found
nredpointer 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 SCIP_RETCODE addComponent ( SCIP scip,
SCIP_ORBITALREDDATA orbireddata,
SCIP_VAR **  permvars,
int  npermvars,
int **  perms,
int  nperms,
SCIP_Bool success 
)
static

◆ freeComponent()

static SCIP_RETCODE freeComponent ( SCIP scip,
SCIP_ORBITALREDDATA orbireddata,
ORCDATA **  orcdata 
)
static

frees component

Parameters
scipSCIP data structure
orbireddatapointer to the orbital reduction data
orcdatapointer 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()

◆ SCIPorbitalReductionGetStatistics()

SCIP_RETCODE SCIPorbitalReductionGetStatistics ( SCIP scip,
SCIP_ORBITALREDDATA orbireddata,
int *  nred,
int *  ncutoff 
)

prints orbital reduction data

Parameters
scipSCIP data structure
orbireddataorbital reduction data structure
nredpointer to store the total number of reductions applied
ncutoffpointer 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
scipSCIP data structure
orbireddataorbital 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
scipSCIP data structure
orbireddataorbital reduction data structure
infeasiblepointer to store whether infeasibility is found
nredpointer to store the number of domain reductions
didruna 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
scipSCIP data structure
orbireddataorbital reduction data structure
permvarsvariable array of the permutation
npermvarsnumber of variables in that array
permspermutations in the component
npermsnumber of permutations in the component
successto 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
scipSCIP data structure
orbireddataorbital 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
scipSCIP data structure
orbireddataorbital 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
scipSCIP data structure
orbireddatapointer to orbital reduction data structure to populate
shadowtreeeventhdlrpointer 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().