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

SCIP can detect two types of symmetries: permutation symmetries and signed permutation symmetries. In a purely integer linear setting

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

a permutation 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\).

Signed permutation symmetries are defined similarly and allow to also handle symmetries arising from reflections of the feasible region along standard hyperplanes, e.g., mapping \(x_i\) to \(-x_i\) and keeping the remaining entries of a solution vector \(x\) invariant. Formally, a signed permutation \(\gamma\) is a permutation of the set \(\{\pm 1, \dots, \pm n\}\) such that \(\gamma(-i) = - \gamma(i)\) for all \(i \in \{1,\dots,n\}\). A signed permutation acts on a vector \(x\) as \(\gamma(x) = (\mathrm{sgn}(\gamma^{-1}(1))x_{|\gamma^{-1}(1)|},\dots, \mathrm{sgn}(\gamma^{-1}(n))x_{|\gamma^{-1}(n)|})\), where \(\mathrm{sgn}(\cdot)\) is the sign function. The remaining properties of a symmetry are the same. It is possible to switch between these two types of symmetries via the parameter propagating/symmetry/symtype. Moreover, to detect more general signed permutations, one can shift variables with a bounded domain to be centered at the origin. This way, also variables with, e.g., domains \([1,2]\) and \([0,1]\) can be symmetric. In SCIP, we implement this shift only within symmetry detection to find generalized signed permutations; the variable bounds of the problem itself remain unchanged.

Since both definitions depend 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 libraries bliss or nauty/traces are the basic workhorses to detect symmetries. Moreover, one can use sassy, a graph symmetry preprocessor which passes the preprocessed graphs to bliss or nauty/traces. The current default is to use bliss in combination with sassy for symmetry detection.

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. Moreover, symmetries can also be detected in code containing customized constraints. To this end, a suitable callback needs to be implemented, see Symmetry detection for customized constraints.

Processing symmetry information

After symmetries have been computed, SCIP has access to a list \(\gamma_1,\dots,\gamma_m\) of (signed) 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

Most symmetry handling methods available in SCIP have only been implemented for ordinary permutation symmetries, and not for signed permutation symmetries. In the following, we silently assume that the described methods deal with ordinary permutation symmetries if not mentioned differently. To handle symmetries, SCIP uses three different classes of methods, which we detail below.

Static symmetry handling constraints for binary variable domains

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.

Dynamic symmetry handling by propagation

Static symmetry handling enforces a lexicographic ordering on the variable solution vectors. The pro of that approach, is that throughout the solving process, the same lexicographic ordering constraint is used. This means that already during presolving certain symmetry reductions can be made. The con of this approach is that an ordering of the variables for lexicographic comparisons have to be made before solving. Consequently, if reductions of certain variable domains are found, but these variables are compared late by the lexicographic comparison order, the effect for symmetry handling is very slim.

Dynamic symmetry handling addresses this issue by propagating symmetry handling constraints, where the variable comparison ordering are determined while solving, attempting to make strong symmetry handling reductions early on. Dynamic symmetry handling removes feasible solutions of the problem, while it is guaranteed that at least one symmetric solution remains feasible.

Whether dynamic or static symmetry handling methods are used, is determined by the boolean parameter propagating/symmetry/usedynamicprop. SCIP features three dynamic symmetry handling methods. SCIP only provides propagation methods for handling these symmetries, and the methods work on variables with arbitrary (so also non-binary) variable domains.

Orbitopal reduction is the dynamic counterpart of orbitopal fixing. This method can be used if the variables can be arranged without duplicates in a matrix, and symmetries permute the columns of this matrix. This method propagates the variable domains such that solutions in matrix-form have lexicographically decreasing columns, with respect to the dynamically chosen row and column order. Orbitopal reduction respects the parameter propagating/symmetry/detectorbitopes.
Lexicographic reduction is the dynamic counterpart of symresack and orbisack propagation. Lexicographic reduction respects the parameter propagating/symmetry/addsymresacks. At the moment, the implementation of this method is the only one that allows to also handle signed permutation symmetries.
Orbital reduction is a generalization of orbital fixing that also works for non-binary variable domains. Orbital reduction respects the 2-bit of the bitset misc/usesymmetry. See method selection. Since there is no static counterpart, this method ignores propagating/symmetry/usedynamicprop.

In all cases, the dynamic variable ordering is derived from the branching decisions. In particular, at different branch-and-bound tree nodes, a different variable ordering can be active. Since the symmetries are handled for independent factors of the symmetry group, a different variable ordering method can be used for handling symmetries in different factors. In SCIP, the same method is used for orbital reduction and for lexicographic reduction, which means that these two methods are compatible and can be used simultaneously in the same factor. Orbitopal reduction uses a different method.

As SCIP might restart the branch-and-bound process, which removes information regarding the branching decisions, we need to make sure that correct reductions are found after a restart. If a restart occurs, static symmetry handling methods are preserved. Since dynamic symmetry handling methods depend on the branch-and-bound tree structure, and because the prior branch-and-bound tree is removed, the dynamic symmetry handling methods are disabled after a 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 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 reduction, and the 4-bit encodes SST cuts. For example, misc/usesymmetry = 3 enables symmetry handling constraints and orbital reduction, 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 reduction, 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 and propagating/symmetry/usedynamicprop is FALSE, 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, orbital reduction is used. If propagating/symmetry/usedynamicprop and propagating/symmetry/addsymresacks are TRUE, then also the dynamic lexicographic reduction method is used.
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\).

Note: If orbital reduction is enabled, a factor \(\Gamma_i\) can always be handled by this method. As such, by default, no SST cuts will be added.; Depending on the setting of misc/usesymmetry, it might be possible that a symmetry component is not handled. For instance, if only orbitopal reduction is used (i.e., propagating/symmetry/detectorbitopes is set to 1), and if a symmetry component is no orbitope, no symmetry is handled for that component at all.

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 parameter propagating/symmetry/symtiming. The parameter takes value 0, 1, or 2, corresponding to computing symmetries before presolving, during presolving, or at the end of presolving, respectively. Based on the computed symmetries, SCIP enables some symmetry handling methods as explained above.

Symmetry detection for customized constraints

To detect (signed) permutation symmetries, SCIP requests from each constraint present in the problem to be solved a node and edge colored graph whose symmetries correspond to the symmetries of the corresponding constraint. This information is provided by two callbacks, the SCIP_DECL_CONSGETPERMSYMGRAPH callback for permutation symmetries and the SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH callback for signed permutation symmetries. If a constraint handler does not implement one of these callbacks, SCIP will not detect symmetries of the corresponding type.

In the following, we briefly describe how such a symmetry detection graph looks like for linear constraints. Afterwards, we mention the basic setup of the symmetry detection graphs and how the callbacks could be implemented for customized constraints.

Symmetry detection graphs for linear constraints

Simple permutation symmetries of a linear constraint \(\sum_{i = 1}^n a_ix_i \leq \beta\) are given by permutations that exchange equivalent variables with the same coefficients. These symmetries can be encoded by a graph with the following structure. For every variable \(x_i\), the graph contains a node \(v_i\) that receives a color that uniquely determines the type of the variable (lower/upper bound, objective coefficient, integrality). Moreover, the graph contains a node \(w\) that receives a color corresponding to the right-hand side \(\beta\). Node \(w\) is then connected with all nodes corresponding to variables. Edge \(\{w,v_i\}\) then receives a color corresponding to the coefficient \(a_i\). Then, every automorphism of this graph corresponds to a permutation symmetry of the linear constraint.

For signed permutation symmetries, almost the same construction can be used. The only difference is that also nodes \(v_{-i}\) need to be introduced that correspond to the negation of variable \(x_i\). These negated variable nodes are then also connected with node \(\beta\) and the corresponding edge receives color \(-a_i\). Finally, to make sure that the corresponding symmetry corresponds to a signed permutation \(\gamma\), i.e., \(\gamma(-i) = - \gamma(i)\), one also needs to add the edges \(\{v_i,v_{-i}\}\) that remain uncolored. Note that the color of node \(v_{-i}\) also needs to uniquely determine the negated variable bounds and objective coefficient.

Principles for building symmetry detection graphs

A symmetry detection graph of a constraint needs to have the property that each of its automorphisms corresponds to a (signed) permutation of the constraint. Moreover, the corresponding constraint handler of the constraints needs to be encoded in the graph to make sure that only symmetries between equivalent constraints can be computed. Among others, this can be achieved by assigning the nodes and edges appropriate colors. To make sure that the colors are compatible between the different symmetry detection graphs, SCIP automatically determines the colors of nodes and edges based on information that is provided by the user (or the creator of the graph).

A pointer to a globally maintained symmetry detection graph is provided to the callbacks. The nodes and edges of the graph of a constraint are added to this global graph. The nodes of the graph need to be added via the functions SCIPaddSymgraphValnode() and SCIPaddSymgraphConsnode(). The first function can be used to create nodes corresponding to a numerical value like \(\beta\) in the above example, the latter function creates a node corresponding to a provided constraint. This ensures that only symmetry detection graphs from the same constraint handler can be isomorphic. The colors of the nodes are then computed automatically by SCIP based on the information that is provided the functions creating these nodes. This ensures that node colors are compatible.

Edges are created via the function SCIPaddSymgraphEdge() which receives, among others, the indices of created nodes. Note that there is no function for creating variable nodes as SCIP automatically creates nodes for variables. Their indices can be accessed via SCIPgetSymgraphVarnodeidx() for original variables and SCIPgetSymgraphNegatedVarnodeidx() for negated variables used for signed permutations. The edges between variables \(x_i\) and \(-x_i\) are also automatically present in the symmetry detection graph for signed permutation symmetries. The function SCIPaddSymgraphEdge() also takes a numerical value as argument, which allows to assign an edge a weight (e.g., \(a_i\) as in the above example).

Moreover, special nodes, so-called operator nodes, can be added via SCIPaddSymgraphOpnode(). Such nodes allow to model special structures of a constraint, which allow to have more degrees of freedom in creating symmetry detection graphs. Different operators are distinguished by an integral value. Their encoding is thus similar to the one of nodes created by SCIPaddSymgraphValnode(). In computing colors, operator nodes are treated differently though, which allows to distinguish operator 2 from the numerical value 2.

Example for creating symmetry detection callbacks

Let \(G = (V,E)\) be an undirected graph with node weights \(c_v\), \(v \in C\). The maximum weight stable set problem can be modeled via the integer program

\[ \max\Big\{ \sum_{v \in V} c_vx_v : x_u + x_v \leq 1 \text{ for all } \{u,v\} \in E,\; x \in \{0,1\}^V\Big\}.\]

Suppose a user wants to implement a constraint handler cons_stableset that enforces a solution to define a stable set in \(G\), e.g., by propagation methods and separating edge and clique inequalities. Then, the symmetries of the constraint are the weight-preserving automorphisms of the underlying graph \(G\). The symmetry detection graph thus can be almost a copy of \(G\).

In our construction, we introduce for each node \(v\) of the graph an operator node \(v'\). Moreover, for each edge \(\{u,v\}\in E\), we add the edges \(\{u',v'\}\) to the symmetry detection graph. To identify the symmetry detection graph as derived from cons_stableset, we add a constraint node that is connected with all operator nodes, which preserves the automorphisms of \(G\). Finally, each node \(v'\) is connected with the corresponding variable node for \(x_v\) by an edge.

In the following, we present a code snippet showing how to implement the above mentioned symmetry detection graph. We assume that the constraint data consdata contains the following fields

nnodes number of nodes in graph;
nedges number of edges in graph;
first array containing the first nodes of each edge;
second array containing the second nodes of each edge;
weights array containing for each node its corresponding weight;
vars array containing a binary variable for each node modeling whether node is present in stable set.

The code for creating the symmetry detection callback could then look like this.

#define NODEOP 1
static
SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphStableSet)
{
   SCIP_CONSDATA* consdata;
   int* idx;
   int vidx;
   int nnodes;
   int v;
 
   consdata = SCIPconsGetData(cons);
   nnodes = consdata->nnodes;
 
   SCIP_CALL( SCIPallocBufferArray(scip, &idx, nnodes + 1) );
 
   // create operator nodes and constraint node
   for( v = 0; v < nnodes; ++v )
   {
      SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, NODEOP, &idx[v]) );
   }
   SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, 0.0, 0.0, &idx[nnodes]) );
 
   // add edges of underlying graph
   for( v = 0; v < consdata->nedges; ++v )
   {
      SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, idx[consdata->first[v]], idx[consdata->second[v]], FALSE, 0.0) );
   }
 
   // connect nodes with constraint node
   for( v = 0; v < nnodes; ++v )
   {
      SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, idx[v], nodeidx[nnodes], FALSE, 0.0) );
   }
 
   // connect operator nodes with variable nodes, assign edges weight of node
   for( v = 0; v < nnodes; ++v )
   {
      vidx = SCIPgetSymgraphVarnodeidx(scip, graph, consdata->vars[v]);
      SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, idx[v], vidx, TRUE, consdata->weights[v]) );
   }
 
   SCIPfreeBufferArray(scip, &idx);
 
   return SCIP_OKAY;
}