Symmetry handling is an important feature of SCIP that allows to discard symmetric subproblems from the branch-and-bound tree, and thus, can substantially reduce the running time. To handle symmetries, SCIP automatically detects symmetries and then applies (combinations of) symmetry handling methods.

Symmetry detection

In a purely integer linear setting

$\max \{ c^{\top} x : Ax \leq b,\; x \in \mathbb{Z}^n \},$

a symmetry is a permutation $\gamma$ of $\{1,\dots,n\}$ that acts on vector $x$ by permuting its coordinates via $\gamma(x) = (x_{\gamma^{-1}(1)}, \dots, x_{\gamma^{-1}(n)})$ such that

$\gamma$ leaves the objective invariant, i.e., $c^{\top}x = c^{\top}\gamma(x)$ , and
$\gamma$ maps feasible solutions onto feasible solutions, i.e., $Ax \leq b$ if and only if $A\gamma(x) \leq b$ .

Since this definition depends on the feasible region of the integer program, which is unknown in general, SCIP only computes symmetries that leave the formulation of the optimization problem invariant. To detect such formulation symmetries, SCIP builds an auxiliary colored graph whose color-preserving automorphisms correspond to symmetries of the integer program. The symmetries of the graph, and thus of the integer program, are then computed by an external graph automorphism library that needs to be linked to SCIP. Currently, SCIP ships with two such libraries: The graph automorphism library bliss is the basic workhorse to detect symmetries. Moreover, one can use sassy, a graph symmetry preprocessor which passes the preprocessed graphs to bliss and is the current default.

Note: To detect symmetries, SCIP needs to be built with sassy/bliss, which can be achieved by using the options SYM=sassy and -DSYM=sassy in the Makefile and CMake system, respectively.

Besides purely integer linear problems, SCIP also supports symmetry detection for general constraint mixed-integer programs containing most of the constraint types that can be handled by SCIP. In particular, symmetries of mixed-integer nonlinear problems can be detected.

Processing symmetry information

After symmetries have been computed, SCIP has access to a list $\gamma_1,\dots,\gamma_m$ of permutations that generate a group $\Gamma$ of symmetries of the optimization problem. That is, SCIP has not access to all permutations in $\Gamma$ , but only a set of generators. Based on these generators, SCIP analyzes the group $\Gamma$ and checks whether it can be split into independent factors. That is, whether there exist subgroups $\Gamma_1,\dots,\Gamma_k$ of $\Gamma$ that act on pairwise independent sets of variables such that $\bigcup_{i=1}^k \Gamma_i = \Gamma$ . In this case, SCIP can handle the symmetries of the different subgroups independently. In particular, different subgroups can be treated by different symmetry handling methods.

Symmetry handling methods

To handle symmetries, SCIP uses three different classes of methods, which we detail below.

Symmetry handling constraints

SCIP contains three constraint handlers for handling symmetries of binary variables: the symresack, orbisack, and orbitope constraint handler. Given a symmetry $\gamma$ , the symresack constraint handler enforces that a solution vector $x$ is not lexicographically smaller than its image $\gamma(x)$ . This constraint is enforced by a propagation algorithm and separating inequalities. Moreover, given the disjoint cycle decomposition of $\gamma$ , SCIP checks, for each cycle of $\gamma$ , whether all variables in the cycle are contained in set packing or partitioning constraints. If this is the case, specialized inequalities can be separated.

In case the permutation $\gamma$ is an involution, i.e., $\gamma(\gamma(x)) = x$ , specialized separation and propagation algorithms can be used, which are implemented in the orbisack constraint handler. For orbisack constraints, also facet-defining inequalities of the convex hull of all binary points $x$ being not lexicographically smaller than $\gamma(x)$ can be separated. Since the coefficients in these inequalities grow exponentially large which might cause numerical instabilities, the separation of these inequalities is disabled by default, but can be enabled via the parameter constraints/orbisack/orbiSeparation. Furthermore, to avoid numerical instabilities, the parameter constraints/orbisack/coeffbound controls the maximum absolute value of a coefficient in separated facet-defining inequalities.

Finally, the orbitope constraint handler is able to handle symmetries of special symmetric groups $\Gamma$ . For orbitopes to be applicable, the affected variables need to be arranged in a matrix $X$ such that the symmetries in $\Gamma$ permute the columns of $X$ . Symmetries are then handled by orbitope constraints by enforcing to only compute solution matrices $X$ whose columns are sorted lexicographically non-increasingly. To this end, a propagation algorithm is used and inequalities are separated. In case the variables of each row of the matrix $X$ are contained in a set packing or partitioning constraint, specialized propagation and separation routines are used.

Orbital fixing

Orbital fixing is a propagation algorithm that derives fixings of binary variables based on already fixed variables. These fixings remove feasible solutions of the problem, while it is guaranteed that at least one symmetric solution remains feasible. The reductions found by orbital fixing are derived from the branching decisions. Thus, as SCIP might restart the branch-and-bound process, which removes previously made branching decisions, we need to make sure that correct reductions are found after a restart. This can be guaranteed by either disabling orbital fixing after a restart or recomputing symmetries. In SCIP, this is controlled via the parameter propagating/symmetry/recomputerestart. If it takes value 0, symmetries are not recomputed and orbital fixing is disabled; a value of 1 means that symmetries are always recomputed; if it has value 2, symmetries are only recomputed if orbital fixing has found a reduction before the restart.

SST cuts

The Schreier-Sims table (SST) is a table that contains certain information about symmetry groups and can be used, among others, to derive symmetry handling inequalities. The corresponding SST cuts are symmetry handling inequalities that are defined iteratively in rounds $r = 1,\dots,R$ . In each round $r$ , a leader variable $\ell_r$ is selected and the group $\Gamma_r = \{ \gamma \in \Gamma : \gamma(\ell_i) = \ell_i \text{ for all } i = 1,\dots,r-1\}$ is considered. Then, the symmetry handling inequalities of round $r$ are defined as $x_{\ell_r} \geq x_j$ for all $j \in \{\gamma(i) : i \in \{1,\dots,n\}\}$ . The latter set is called the orbit of leader $\ell_r$ .

SST cuts admit many degrees of freedom. In particular, they are not limited to binary variables but can be used for arbitrary variable types. A user can gain control over the selection process of SST cuts via several parameters. For instance,

sstleadervartype is a bitset encoding the variable types of leaders: the 1-bit models binary, the 2-bit integer, the 4-bit implicit integer, and the 8-bit continuous variables. That is, a value of 9 models that the leader can be a binary or continuous variable.
sstleaderrule ranges from 0 to 2 and models whether a leader is the first variable in its orbit, the last variable in its orbit, or a variable with most conflicts with other variables in the orbit, respectively.
ssttiebreakrule ranges from 0 to 2 and models whether an orbit of minimum size, maximum size or with most variables being in conflict to the leader is selected, respectively.
sstmixedcomponents whether SST cuts are also applied if a symmetries do not only affect variables of a single type.
sstaddcuts whether SST cuts are added to the problem. If no cuts are added, only binary variables might be fixed to 0 if they are in conflict with the leader.

Selecting symmetry handling methods

The three symmetry handling methods explained above can be enabled and disabled via the parameter misc/usesymmetry, which encodes the enabled methods via a bitset that ranges between 0 and 7: the 1-bit encodes symmetry handling constraints, the 2-bit encodes orbital fixing, and the 4-bit encodes SST cuts. For example, misc/usesymmetry = 3 enables symmetry handling constraints and orbital fixing, whereas misc/usesymmetry = 0 disables symmetry handling. In the following, we explain how the combination of different symmetry handling methods works.

The default strategy of SCIP is to handle symmetries via the bitset value 7, i.e., symmetry handling constraints, orbital fixing, and SST cuts are enabled. To make sure that the different methods are compatible, the following steps are carried out:

SCIP determines independent subgroups $\Gamma_1,\dots,\Gamma_k$ as described in Processing symmetry information. Then, for each subgroup $\Gamma_i$ , different symmetry handling methods can be applied.
For each subgroup $\Gamma_i$ , a heuristic is called that checks whether orbitopes are applicable to handle the entire subgroup. If yes, this subgroup is handled by orbitopes and no other symmetry handling methods.
Otherwise, if parameter propagating/symmetry/detectsubgroups is TRUE, a heuristic is called to detect whether "hidden" orbitopes are present. That is, whether some but not all symmetries of $\Gamma_i$ can be handled by orbitopes. If sufficiently many symmetries can be handled by orbitopes, orbitopes are applied and, if parameter propagating/symmetry/addweaksbcs is TRUE, some compatible SST cuts are added, too. Besides this, no further symmetry handling methods are applied for $\Gamma_i$ .
Otherwise, if the majority of variables affected by $\Gamma_i$ are non-binary, SST cuts are applied to handle $\Gamma_i$ . No further symmetry handling methods are applied for $\Gamma_i$ .
Finally, if none of the previous methods has been used to handle $\Gamma_i$ , orbital fixing is used.

Note: If one of the previous methods is disabled via misc/usesymmetry, it might be possible that not all symmetries are handled. For instance, if orbital fixing is disabled and neither SST cuts nor orbitopes are applied to handle $\Gamma_i$ , the parameter propagating/symmetry/addsymresacks needs to be set to TRUE to handle the symmetries of $\Gamma_i$ . If this parameter is TRUE, then orbisack/symresack constraints are also applied to subgroups that are handled via hidden orbitopes or SST cuts (if these cuts are applied for binary variables).

Controlling the timing of symmetry computation

Since presolving might both remove and introduce formulation symmetries, the timing of computing symmetries can be changed via the parameters propagating/symmetry/addconsstiming and propagating/symmetry/ofsymcomptiming depending on whether symmetry handling constraints/SST cuts and orbital fixing are applied, respectively. If both are applied, propagating/symmetry/addconsstiming is dominant. Both parameters take values 0, 1, or 2, corresponding to computing symmetries before presolving, during presolving, or when the symmetry handling methods are applied first, respectively. For the constraint-based approach, the latter means at the end of presolving; for orbital fixing, after the first branching decision.

If a restart occurs, symmetry handling constraints and SST cuts can be inherited to the new run. Since orbital fixing depends on the branching history, which is not available after a restart anymore, symmetries might needed to be recomputed. This is controlled via the parameter propagating/symmetry/recomputerestart, which takes values 0, 1, or 2, corresponding to never recomputing symmetries (i.e., disabling orbital fixing after a restart), always recompute symmetries, or only recomputing symmetries if orbital fixing found a reduction in the previous run, respectively.