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)

Macro Definition Documentation

◆ EVENTHDLR_SYMMETRY_NAME

#define EVENTHDLR_SYMMETRY_NAME "symmetry_orbital"

Definition at line 121 of file symmetry_orbital.c.

Referenced by identifyOrbitalSymmetriesBroken().

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

Referenced by identifyOrbitalSymmetriesBroken().

Typedef Documentation

◆ ORCDATA

typedef struct OrbitalReductionComponentData ORCDATA

Definition at line 148 of file symmetry_orbital.c.

Function Documentation

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

SCIP

Detailed Description

Data Structures

Macros

Typedefs