# SCIP

Solving Constraint Integer Programs

symmetry_orbital.c File Reference

## 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

## 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)

## ◆ 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.

## ◆ ORCDATA

 typedef struct OrbitalReductionComponentData ORCDATA

Definition at line 148 of file symmetry_orbital.c.

## ◆ identifyOrbitalSymmetriesBroken()

 static SCIP_RETCODE identifyOrbitalSymmetriesBroken ( SCIP * scip, ORCDATA * orcdata )
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.

Referenced by orbitalReductionPropagateComponent().

## ◆ 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
 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.

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

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

Referenced by orbitalReductionPropagateComponent().

## ◆ applyOrbitalReductionPropagations()

 static SCIP_RETCODE applyOrbitalReductionPropagations ( SCIP * scip, ORCDATA * orcdata, SCIP_SHADOWTREE * shadowtree, SCIP_Bool * infeasible, int * nred )
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.

Referenced by orbitalReductionPropagateComponent().

## ◆ 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
 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.

Referenced by SCIPorbitalReductionPropagate().

 static SCIP_RETCODE addComponent ( SCIP * scip, SCIP_ORBITALREDDATA * orbireddata, SCIP_VAR ** permvars, int npermvars, int ** perms, int nperms, SCIP_Bool * success )
static

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.

## ◆ freeComponent()

 static SCIP_RETCODE freeComponent ( SCIP * scip, SCIP_ORBITALREDDATA * orbireddata, ORCDATA ** orcdata )
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.

Referenced by SCIPorbitalReductionReset().

## ◆ SCIP_DECL_EVENTEXEC()

 static SCIP_DECL_EVENTEXEC ( eventExecGlobalBoundChange )
static

maintains global variable bound reductions found during presolving or at the root node

Definition at line 1479 of file symmetry_orbital.c.

## ◆ 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.

Referenced by propagateSymmetry().

 SCIP_RETCODE SCIPorbitalReductionAddComponent ( SCIP * scip, SCIP_ORBITALREDDATA * orbireddata, SCIP_VAR ** permvars, int npermvars, int ** perms, int nperms, SCIP_Bool * success )

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

## ◆ 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.

Referenced by SCIPincludePropSymmetry().