Detailed Description

propagator for handling symmetries

Author: Marc Pfetsch; Thomas Rehn; Christopher Hojny

This propagator combines the following symmetry handling functionalities:

It allows to compute symmetries of the problem and to store this information in adequate form. The symmetry information can be accessed through external functions.
It allows to add the following symmetry breaking constraints:
- symresack constraints, which separate minimal cover inequalities
- orbitope constraints, if special symmetry group structures are detected
It allows to apply orbital fixing.

Symmetry Computation

The following comments apply to symmetry computation.

The generic functionality of the compute_symmetry.h interface is used.
We treat implicit integer variables as if they were continuous/real variables. The reason is that there is currently no distinction between implicit integer and implicit binary. Moreover, currently implicit integer variables hurt our code more than continuous/real variables (we basically do not handle integral variables at all).
We do not copy symmetry information, since it is not clear how this information transfers. Moreover, copying symmetry might inhibit heuristics. But note that solving a sub-SCIP might then happen without symmetry information!

Symmetry Handling Constraints

The following comments apply to adding symmetry handling constraints.

The code automatically detects whether symmetry substructures like symresacks or orbitopes are present and possibly adds the corresponding constraints.
If orbital fixing is active, only orbitopes are added (if present) and no symresacks.
We try to compute symmetry as late as possible and then add constraints based on this information.
Currently, we only allocate memory for pointers to symresack constraints for group generators. If further constraints are considered, we have to reallocate memory.

Orbital Fixing

Orbital fixing is implemented as 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. Different from Margot, the subgroup is obtained by filtering out generators that do not individually stabilize the variables branched to 1.

Precondition: All variable fixings applied by other components are required to be strict, i.e., if one variable is fixed to a certain value v, all other variables in the same variable orbit can be fixed to v as well, c.f.
F. Margot: Symmetry in integer linear programming. 50 Years of Integer Programming, 647-686, Springer 2010.

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). To avoid this situation, we have to assume that all non-strict settings fix variables globally, i.e., we can take care of it by taking variables into account that have been globally fixed to 1. In fact, it suffices to consider one kind of global fixings since stabilizing one kind prevents an orbit to contain variables that have been fixed globally to different values.

Precondition: All non-strict settings are global settings, since otherwise, we cannot (efficiently) take care of them.; No non-strict setting algorithm is interrupted early (e.g., by a time or iteration limit), since this may lead to wrong decisions by orbital fixing as well. For example, if cons_setppc in the above toy example starts by fixing \(x_2 = 0\) and is interrupted afterwards, orbital fixing detects that the orbit \(\{x_1, x_2\}\) contains one variable that is fixed to 0, and thus, it fixes \(x_1\) to 0 as well. Thus, after these reductions, every feasible solution has objective 0 which is not optimal. This situation would not occur if the non-strict setting is complete, because then \(x_1\) is globally fixed to 1, and thus, is stabilized in orbital fixing.

Note that orbital fixing might lead to wrong results if it is called in repropagation of a node, because the path from the node to the root might have been changed. Thus, the stabilizers of global 1-fixing and 1-branchings of the initial propagation and repropagation might differ, which may cause conflicts. For this reason, orbital fixing cannot be called in repropagation.

Note: If, besides orbital fixing, also symmetry handling constraints shall be added, orbital fixing is only applied to symmetry components that are not handled by orbitope constraints.

Definition in file prop_symmetry.c.

#include <scip/cons_linear.h>
#include <scip/cons_knapsack.h>
#include <scip/cons_varbound.h>
#include <scip/cons_setppc.h>
#include <scip/cons_and.h>
#include <scip/cons_logicor.h>
#include <scip/cons_or.h>
#include "scip/cons_orbitope.h"
#include "scip/cons_symresack.h"
#include <scip/cons_xor.h>
#include <scip/cons_linking.h>
#include <scip/cons_bounddisjunction.h>
#include <scip/misc.h>
#include <scip/prop_symmetry.h>
#include <symmetry/compute_symmetry.h>
#include <scip/symmetry.h>
#include <string.h>

Go to the source code of this file.

Data Structures
struct	SYM_Sortrhstype

Macros
#define	PROP_NAME "symmetry"

#define	PROP_DESC "propagator for handling symmetry"

#define	PROP_TIMING SCIP_PROPTIMING_BEFORELP

#define	PROP_PRIORITY -1000000

#define	PROP_FREQ 1

#define	PROP_DELAY FALSE

#define	PROP_PRESOL_PRIORITY -10000000

#define	PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */

#define	PROP_PRESOL_MAXROUNDS -1

#define	DEFAULT_MAXGENERATORS 1500

#define	DEFAULT_CHECKSYMMETRIES FALSE

#define	DEFAULT_DISPLAYNORBITVARS FALSE

#define	DEFAULT_USECOLUMNSPARSITY FALSE

#define	DEFAULT_DOUBLEEQUATIONS FALSE

#define	DEFAULT_COMPRESSSYMMETRIES TRUE

#define	DEFAULT_COMPRESSTHRESHOLD 0.5

#define	DEFAULT_SYMFIXNONBINARYVARS FALSE

#define	DEFAULT_CONSSADDLP TRUE

#define	DEFAULT_ADDSYMRESACKS TRUE

#define	DEFAULT_DETECTORBITOPES TRUE

#define	DEFAULT_ADDCONSSTIMING 2

#define	DEFAULT_OFSYMCOMPTIMING 2

#define	DEFAULT_PERFORMPRESOLVING FALSE

#define	DEFAULT_RECOMPUTERESTART FALSE

#define	DEFAULT_DISABLEOFRESTART FALSE

#define	EVENTHDLR_SYMMETRY_NAME "symmetry"

#define	EVENTHDLR_SYMMETRY_DESC "filter global variable fixing event handler for orbital fixing"

#define	TABLE_NAME_ORBITALFIXING "orbitalfixing"

#define	TABLE_DESC_ORBITALFIXING "orbital fixing statistics"

#define	TABLE_POSITION_ORBITALFIXING 7001

#define	TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING

#define	MAXGENNUMERATOR 64000000

#define	SCIP_SPECIALVAL 1.12345678912345e+19

#define	COMPRESSNVARSLB 25000

#define	ISSYMRETOPESACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0)

#define	ISORBITALFIXINGACTIVE(x) (((unsigned) x & SYM_HANDLETYPE_ORBITALFIXING) != 0)

Typedefs
typedef struct SYM_Sortrhstype	SYM_SORTRHSTYPE

Functions
static	SCIP_DECL_EVENTEXEC (eventExecSymmetry)

static	SCIP_DECL_TABLEOUTPUT (tableOutputOrbitalfixing)

static	SCIP_DECL_TABLEFREE (tableFreeOrbitalfixing)

static	SCIP_DECL_HASHGETKEY (SYMhashGetKeyVartype)

static	SCIP_DECL_HASHKEYEQ (SYMhashKeyEQVartype)

static	SCIP_DECL_HASHKEYVAL (SYMhashKeyValVartype)

static	SCIP_DECL_SORTINDCOMP (SYMsortRhsTypes)

static	SCIP_DECL_SORTINDCOMP (SYMsortMatCoef)

static SCIP_Bool	checkSymmetryDataFree (SCIP_PROPDATA *propdata)

static SCIP_RETCODE	freeSymmetryData (SCIP scip, SCIP_PROPDATA propdata)

static SCIP_RETCODE	delSymConss (SCIP scip, SCIP_PROPDATA propdata)

static SCIP_Bool	SymmetryFixVar (SYM_SPEC fixedtype, SCIP_VAR *var)

static SCIP_RETCODE	getActiveVariables (SCIP scip, SCIP_VAR vars, SCIP_Real scalars, int nvars, SCIP_Real constant, SCIP_Bool transformed)

static SCIP_RETCODE	collectCoefficients (SCIP scip, SCIP_Bool doubleequations, SCIP_VAR linvars, SCIP_Real linvals, int nlinvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool istransformed, SYM_RHSSENSE rhssense, SYM_MATRIXDATA matrixdata, int nconssforvar)

static SCIP_RETCODE	checkSymmetriesAreSymmetries (SCIP scip, SYM_SPEC fixedtype, SYM_MATRIXDATA matrixdata, int nperms, int **perms)

static int	getNSymhandableConss (SCIP *scip)

static SCIP_RETCODE	setSymmetryData (SCIP scip, SCIP_VAR vars, int nvars, int nbinvars, SCIP_VAR *permvars, int npermvars, int nbinpermvars, int perms, int nperms, int nmovedvars, SCIP_Bool binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool compressed)

static SCIP_RETCODE	computeSymmetryGroup (SCIP scip, SCIP_Bool doubleequations, SCIP_Bool compresssymmetries, SCIP_Real compressthreshold, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool local, SCIP_Bool checksymmetries, SCIP_Bool usecolumnsparsity, int npermvars, int nbinpermvars, SCIP_VAR *permvars, int nperms, int nmaxperms, int *perms, SCIP_Real log10groupsize, int nmovedvars, SCIP_Bool binvaraffected, SCIP_Bool compressed, SCIP_Bool success)

static SCIP_RETCODE	determineSymmetry (SCIP scip, SCIP_PROPDATA propdata, SYM_SPEC symspecrequire, SYM_SPEC symspecrequirefixed)

static SCIP_RETCODE	detectOrbitopes (SCIP scip, SCIP_PROPDATA propdata, int components, int componentbegins, int ncomponents)

static SCIP_RETCODE	addSymresackConss (SCIP scip, SCIP_PROP prop, int components, int componentbegins, int ncomponents)

static SCIP_RETCODE	tryAddSymmetryHandlingConss (SCIP scip, SCIP_PROP prop, SCIP_Bool *earlyterm)

static SCIP_RETCODE	performOrbitalFixing (SCIP scip, SCIP_VAR permvars, int npermvars, int orbits, int orbitbegins, int norbits, SCIP_Bool infeasible, int nfixedzero, int nfixedone)

static SCIP_RETCODE	computeBranchingVariables (SCIP scip, int nvars, SCIP_HASHMAP varmap, SCIP_Shortbool bg1, int bg1list, int *nbg1)

static SCIP_RETCODE	propagateOrbitalFixing (SCIP scip, SCIP_PROPDATA propdata, SCIP_Bool infeasible, int nprop)

static	SCIP_DECL_PROPINITPRE (propInitpreSymmetry)

static	SCIP_DECL_PROPEXITPRE (propExitpreSymmetry)

static	SCIP_DECL_PROPPRESOL (propPresolSymmetry)

static	SCIP_DECL_PROPEXEC (propExecSymmetry)

static	SCIP_DECL_PROPEXIT (propExitSymmetry)

static	SCIP_DECL_PROPRESPROP (propRespropSymmetry)

static	SCIP_DECL_PROPFREE (propFreeSymmetry)

SCIP_RETCODE	SCIPincludePropSymmetry (SCIP *scip)

SCIP_RETCODE	SCIPgetSymmetry (SCIP scip, int npermvars, SCIP_VAR *permvars, SCIP_HASHMAP permvarmap, int nperms, int perms, int permstrans, SCIP_Real log10groupsize, SCIP_Bool binvaraffected, int components, int componentbegins, int vartocomponent, int ncomponents)

SCIP_Bool	SCIPisOrbitalfixingEnabled (SCIP *scip)

int	SCIPgetSymmetryNGenerators (SCIP *scip)

Macro Definition Documentation

◆ PROP_NAME

#define PROP_NAME "symmetry"

Definition at line 133 of file prop_symmetry.c.

Referenced by SCIP_DECL_PROPEXIT(), SCIP_DECL_PROPEXITPRE(), SCIP_DECL_PROPFREE(), SCIP_DECL_PROPPRESOL(), SCIPgetSymmetry(), SCIPgetSymmetryNGenerators(), SCIPincludePropSymmetry(), and SCIPisOrbitalfixingEnabled().

◆ PROP_DESC

#define PROP_DESC "propagator for handling symmetry"

Definition at line 134 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ PROP_TIMING

#define PROP_TIMING SCIP_PROPTIMING_BEFORELP

propagation timing mask

Definition at line 135 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ PROP_PRIORITY

#define PROP_PRIORITY -1000000

propagator priority

Definition at line 136 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ PROP_FREQ

#define PROP_FREQ 1

propagator frequency

Definition at line 137 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ PROP_DELAY

#define PROP_DELAY FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 138 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ PROP_PRESOL_PRIORITY

#define PROP_PRESOL_PRIORITY -10000000

priority of the presolving method (>= 0: before, < 0: after constraint handlers)

Definition at line 140 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ PROP_PRESOLTIMING

#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */

Definition at line 141 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ PROP_PRESOL_MAXROUNDS

#define PROP_PRESOL_MAXROUNDS -1

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 142 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_MAXGENERATORS

#define DEFAULT_MAXGENERATORS 1500

limit on the number of generators that should be produced within symmetry detection (0 = no limit)

Definition at line 146 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_CHECKSYMMETRIES

#define DEFAULT_CHECKSYMMETRIES FALSE

Should all symmetries be checked after computation?

Definition at line 147 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_DISPLAYNORBITVARS

#define DEFAULT_DISPLAYNORBITVARS FALSE

Should the number of variables affected by some symmetry be displayed?

Definition at line 148 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_USECOLUMNSPARSITY

#define DEFAULT_USECOLUMNSPARSITY FALSE

Should the number of conss a variable is contained in be exploited in symmetry detection?

Definition at line 149 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_DOUBLEEQUATIONS

#define DEFAULT_DOUBLEEQUATIONS FALSE

Double equations to positive/negative version?

Definition at line 150 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_COMPRESSSYMMETRIES

#define DEFAULT_COMPRESSSYMMETRIES TRUE

Should non-affected variables be removed from permutation to save memory?

Definition at line 151 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_COMPRESSTHRESHOLD

#define DEFAULT_COMPRESSTHRESHOLD 0.5

Compression is used if percentage of moved vars is at most the threshold.

Definition at line 152 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_SYMFIXNONBINARYVARS

#define DEFAULT_SYMFIXNONBINARYVARS FALSE

Whether all non-binary variables shall be not affected by symmetries if OF is active?

Definition at line 153 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_CONSSADDLP

#define DEFAULT_CONSSADDLP TRUE

Should the symmetry breaking constraints be added to the LP?

Definition at line 156 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_ADDSYMRESACKS

#define DEFAULT_ADDSYMRESACKS TRUE

Add inequalities for symresacks for each generator?

Definition at line 157 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_DETECTORBITOPES

#define DEFAULT_DETECTORBITOPES TRUE

Should we check whether the components of the symmetry group can be handled by orbitopes?

Definition at line 158 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_ADDCONSSTIMING

#define DEFAULT_ADDCONSSTIMING 2

timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)

Definition at line 159 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_OFSYMCOMPTIMING

#define DEFAULT_OFSYMCOMPTIMING 2

timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)

Definition at line 162 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_PERFORMPRESOLVING

#define DEFAULT_PERFORMPRESOLVING FALSE

Run orbital fixing during presolving?

Definition at line 163 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_RECOMPUTERESTART

#define DEFAULT_RECOMPUTERESTART FALSE

Recompute symmetries after a restart has occurred?

Definition at line 164 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ DEFAULT_DISABLEOFRESTART

#define DEFAULT_DISABLEOFRESTART FALSE

whether OF shall be disabled if OF has found a reduction and a restart occurs

Definition at line 165 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ EVENTHDLR_SYMMETRY_NAME

#define EVENTHDLR_SYMMETRY_NAME "symmetry"

Definition at line 169 of file prop_symmetry.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludePropSymmetry().

◆ EVENTHDLR_SYMMETRY_DESC

#define EVENTHDLR_SYMMETRY_DESC "filter global variable fixing event handler for orbital fixing"

Definition at line 170 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ TABLE_NAME_ORBITALFIXING

#define TABLE_NAME_ORBITALFIXING "orbitalfixing"

Definition at line 173 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ TABLE_DESC_ORBITALFIXING

#define TABLE_DESC_ORBITALFIXING "orbital fixing statistics"

Definition at line 174 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ TABLE_POSITION_ORBITALFIXING

#define TABLE_POSITION_ORBITALFIXING 7001

the position of the statistics table

Definition at line 175 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ TABLE_EARLIEST_ORBITALFIXING

#define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING

output of the statistics table is only printed from this stage onwards

Definition at line 176 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

◆ MAXGENNUMERATOR

#define MAXGENNUMERATOR 64000000

determine maximal number of generators by dividing this number by the number of variables

Definition at line 180 of file prop_symmetry.c.

Referenced by determineSymmetry().

◆ SCIP_SPECIALVAL

#define SCIP_SPECIALVAL 1.12345678912345e+19

special floating point value for handling zeros in bound disjunctions

Definition at line 181 of file prop_symmetry.c.

Referenced by computeSymmetryGroup().

◆ COMPRESSNVARSLB

#define COMPRESSNVARSLB 25000

lower bound on the number of variables above which compression could be performed

Definition at line 182 of file prop_symmetry.c.

Referenced by setSymmetryData().

◆ ISSYMRETOPESACTIVE

#define ISSYMRETOPESACTIVE ( x ) (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0)

Definition at line 185 of file prop_symmetry.c.

Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPINITPRE().

◆ ISORBITALFIXINGACTIVE

#define ISORBITALFIXINGACTIVE ( x ) (((unsigned) x & SYM_HANDLETYPE_ORBITALFIXING) != 0)

Definition at line 186 of file prop_symmetry.c.

Referenced by freeSymmetryData(), SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPINITPRE().

Typedef Documentation

◆ SYM_SORTRHSTYPE

typedef struct SYM_Sortrhstype SYM_SORTRHSTYPE

Definition at line 464 of file prop_symmetry.c.

Function Documentation

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecSymmetry )

static

exec the event handler for handling global variable bound changes (necessary for orbital fixing)

Global variable fixings during the solving process might arise because parts of the tree are pruned or if certain preprocessing steps are performed that do not correspond to strict setting algorithms. Since these fixings might be caused by or be in conflict with orbital fixing, they can be in conflict with the symmetry handling decisions of orbital fixing in the part of the tree that is not pruned. Thus, we have to take global fixings into account when filtering out symmetries.

Definition at line 284 of file prop_symmetry.c.

References EVENTHDLR_SYMMETRY_NAME, NULL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPABORT, SCIPdebugMsg, SCIPerrorMessage, SCIPeventGetNewbound(), SCIPeventGetOldbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetName(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisEQ(), SCIPvarGetName(), SCIPvarGetType(), and TRUE.

◆ SCIP_DECL_TABLEOUTPUT()

static SCIP_DECL_TABLEOUTPUT ( tableOutputOrbitalfixing )

static

output method of orbital fixing propagator statistics table to output file stream 'file'

Definition at line 360 of file prop_symmetry.c.

References NULL, SCIP_OKAY, SCIP_VERBLEVEL_MINIMAL, SCIPtableGetData(), and SCIPverbMessage().

◆ SCIP_DECL_TABLEFREE()

static SCIP_DECL_TABLEFREE ( tableFreeOrbitalfixing )

static

destructor of statistics table to free user data (called when SCIP is exiting)

Definition at line 384 of file prop_symmetry.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPtableGetData().

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyVartype )

static

gets the key of the given element

Definition at line 403 of file prop_symmetry.c.

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQVartype )

static

returns TRUE iff both keys are equal

Compare the types of two variables according to objective, lower and upper bound, variable type, and column sparsity.

Definition at line 413 of file prop_symmetry.c.

References FALSE, SYM_Vartype::lb, SYM_Vartype::nconss, SYM_Vartype::obj, SCIPisEQ(), TRUE, SYM_Vartype::type, and SYM_Vartype::ub.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValVartype )

static

returns the hash value of the key

Definition at line 448 of file prop_symmetry.c.

References SYM_Vartype::lb, SYM_Vartype::nconss, SYM_Vartype::obj, SCIPhashFour, SCIPrealHashCode(), and SYM_Vartype::ub.

◆ SCIP_DECL_SORTINDCOMP() [1/2]

static SCIP_DECL_SORTINDCOMP ( SYMsortRhsTypes )

static

sorts rhs types - first by sense, then by value

Due to numerical issues, we first sort by sense, then by value.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

0: ind2 comes after (is worse than) ind2

Definition at line 476 of file prop_symmetry.c.

References SYM_Sortrhstype::nrhscoef, SCIP_Real, SYM_Sortrhstype::senses, and SYM_Sortrhstype::vals.

◆ SCIP_DECL_SORTINDCOMP() [2/2]

static SCIP_DECL_SORTINDCOMP ( SYMsortMatCoef )

static

sorts matrix coefficients

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

0: ind2 comes after (is worse than) ind2

Definition at line 510 of file prop_symmetry.c.

References SCIP_Real, and SYM_Sortrhstype::vals.

◆ checkSymmetryDataFree()

static SCIP_Bool checkSymmetryDataFree ( SCIP_PROPDATA * propdata )

static

checks that symmetry data is all freed

Parameters

propdata propagator data

Definition at line 536 of file prop_symmetry.c.

References FALSE, NULL, and TRUE.

Referenced by determineSymmetry(), and freeSymmetryData().

◆ freeSymmetryData()

static SCIP_RETCODE freeSymmetryData	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata
	)

static

frees symmetry data

Parameters

scip	SCIP pointer
propdata	propagator data

Definition at line 575 of file prop_symmetry.c.

References checkSymmetryDataFree(), FALSE, ISORBITALFIXINGACTIVE, NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPdropVarEvent(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPhashmapFree(), SCIPreleaseCons(), SCIPreleaseVar(), and SCIPvarGetType().

Referenced by determineSymmetry(), and SCIP_DECL_PROPEXIT().

◆ delSymConss()

static SCIP_RETCODE delSymConss	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata
	)

static

deletes symmetry handling constraints

Parameters

scip	SCIP pointer
propdata	propagator data

Definition at line 732 of file prop_symmetry.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdelCons(), SCIPfreeBlockMemoryArray, and SCIPreleaseCons().

Referenced by determineSymmetry().

◆ SymmetryFixVar()

static SCIP_Bool SymmetryFixVar	(	SYM_SPEC	fixedtype,
		SCIP_VAR *	var
	)

static

determines whether variable should be fixed by permutations

Parameters

fixedtype	bitset of variable types that should be fixed
var	variable to be considered

Definition at line 773 of file prop_symmetry.c.

References FALSE, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.

Referenced by checkSymmetriesAreSymmetries(), and computeSymmetryGroup().

◆ getActiveVariables()

static SCIP_RETCODE getActiveVariables	(	SCIP *	scip,
		SCIP_VAR ***	vars,
		SCIP_Real **	scalars,
		int *	nvars,
		SCIP_Real *	constant,
		SCIP_Bool	transformed
	)

static

Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.

Note: constant needs to be initialized!

Parameters

scip	SCIP data structure
vars	pointer to vars array to get active variables for
scalars	pointer to scalars a_1, ..., a_n in linear sum a_1x_1 + ... + a_nx_n + c
nvars	pointer to number of variables and values in vars and vals array
constant	pointer to constant c in linear sum a_1x_1 + ... + a_nx_n + c
transformed	transformed constraint?

Definition at line 794 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPgetProbvarLinearSum(), SCIPreallocBufferArray, SCIPvarGetOrigvarSum(), and TRUE.

Referenced by collectCoefficients().

◆ collectCoefficients()

static SCIP_RETCODE collectCoefficients	(	SCIP *	scip,
		SCIP_Bool	doubleequations,
		SCIP_VAR **	linvars,
		SCIP_Real *	linvals,
		int	nlinvars,
		SCIP_Real	lhs,
		SCIP_Real	rhs,
		SCIP_Bool	istransformed,
		SYM_RHSSENSE	rhssense,
		SYM_MATRIXDATA *	matrixdata,
		int *	nconssforvar
	)

static

fills in matrix elements into coefficient arrays

Parameters

scip	SCIP data structure
doubleequations	Double equations to positive/negative version?
linvars	array of linear variables
linvals	array of linear coefficients values (or NULL if all linear coefficient values are 1)
nlinvars	number of linear variables
lhs	left hand side
rhs	right hand side
istransformed	whether the constraint is transformed
rhssense	identifier of constraint type
matrixdata	matrix data to be filled in
nconssforvar	pointer to array to store for each var the number of conss

Definition at line 840 of file prop_symmetry.c.

References FALSE, getActiveVariables(), SYM_Matrixdata::matcoef, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::nmaxmatcoef, SYM_Matrixdata::nrhscoef, SYM_Sortrhstype::nrhscoef, NULL, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhsidx, SYM_Matrixdata::rhssense, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPisEQ(), SCIPisInfinity(), SCIPisPositive(), SCIPreallocBlockMemoryArray, SCIPvarGetProbindex(), SYM_SENSE_BOUNDIS_TYPE_2, SYM_SENSE_EQUATION, SYM_SENSE_INEQUALITY, SYM_SENSE_XOR, TRUE, and SYM_Sortrhstype::vals.

Referenced by computeSymmetryGroup().

◆ checkSymmetriesAreSymmetries()

static SCIP_RETCODE checkSymmetriesAreSymmetries	(	SCIP *	scip,
		SYM_SPEC	fixedtype,
		SYM_MATRIXDATA *	matrixdata,
		int	nperms,
		int **	perms
	)

static

checks whether given permutations form a symmetry of a MIP

We need the matrix and rhs in the original order in order to speed up the comparison process. The matrix is needed in the right order to easily check rows. The rhs is used because of cache effects.

Parameters

scip	SCIP data structure
fixedtype	variable types that must be fixed by symmetries
matrixdata	matrix data
nperms	number of permutations
perms	permutations

Definition at line 1067 of file prop_symmetry.c.

References FALSE, SYM_Matrixdata::matcoef, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, SYM_Sortrhstype::nrhscoef, NULL, SYM_Matrixdata::permvars, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhssense, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPisEQ(), SCIPisZero(), SymmetryFixVar(), and TRUE.

Referenced by computeSymmetryGroup().

◆ getNSymhandableConss()

static int getNSymhandableConss ( SCIP * scip )

static

returns the number of active constraints that can be handled by symmetry

Parameters

scip	SCIP instance

Definition at line 1213 of file prop_symmetry.c.

References NULL, SCIPconshdlrGetNActiveConss(), and SCIPfindConshdlr().

Referenced by computeSymmetryGroup(), and determineSymmetry().

◆ setSymmetryData()

static SCIP_RETCODE setSymmetryData	(	SCIP *	scip,
		SCIP_VAR **	vars,
		int	nvars,
		int	nbinvars,
		SCIP_VAR ***	permvars,
		int *	npermvars,
		int *	nbinpermvars,
		int **	perms,
		int	nperms,
		int *	nmovedvars,
		SCIP_Bool *	binvaraffected,
		SCIP_Bool	usecompression,
		SCIP_Real	compressthreshold,
		SCIP_Bool *	compressed
	)

static

set symmetry data

Parameters

scip	SCIP pointer
vars	vars present at time of symmetry computation
nvars	number of vars present at time of symmetry computation
nbinvars	number of binary vars present at time of symmetry computation
permvars	pointer to permvars array
npermvars	pointer to store number of permvars
nbinpermvars	pointer to store number of binary permvars
perms	permutations matrix (nperms x nvars)
nperms	number of permutations
nmovedvars	pointer to store number of vars affected by symmetry (if usecompression) or NULL
binvaraffected	pointer to store whether a binary variable is affected by symmetry
usecompression	whether symmetry data shall be compressed
compressthreshold	if percentage of moved vars is at most threshold, compression is done
compressed	pointer to store whether compression has been performed

Definition at line 1249 of file prop_symmetry.c.

References COMPRESSNVARSLB, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPisGE(), SCIPisLE(), SCIPreallocBlockMemoryArray, SCIPvarIsBinary(), and TRUE.

Referenced by computeSymmetryGroup().

◆ computeSymmetryGroup()

static SCIP_RETCODE computeSymmetryGroup	(	SCIP *	scip,
		SCIP_Bool	doubleequations,
		SCIP_Bool	compresssymmetries,
		SCIP_Real	compressthreshold,
		int	maxgenerators,
		SYM_SPEC	fixedtype,
		SCIP_Bool	local,
		SCIP_Bool	checksymmetries,
		SCIP_Bool	usecolumnsparsity,
		int *	npermvars,
		int *	nbinpermvars,
		SCIP_VAR ***	permvars,
		int *	nperms,
		int *	nmaxperms,
		int ***	perms,
		SCIP_Real *	log10groupsize,
		int *	nmovedvars,
		SCIP_Bool *	binvaraffected,
		SCIP_Bool *	compressed,
		SCIP_Bool *	success
	)

static

computes symmetry group of a MIP

Parameters

scip	SCIP pointer
doubleequations	Double equations to positive/negative version?
compresssymmetries	Should non-affected variables be removed from permutation to save memory?
compressthreshold	Compression is used if percentage of moved vars is at most the threshold.
maxgenerators	maximal number of generators constructed (= 0 if unlimited)
fixedtype	variable types that must be fixed by symmetries
local	Use local variable bounds?
checksymmetries	Should all symmetries be checked after computation?
usecolumnsparsity	Should the number of conss a variable is contained in be exploited in symmetry detection?
npermvars	pointer to store number of variables for permutations
nbinpermvars	pointer to store number of binary variables for permutations
permvars	pointer to store variables on which permutations act
nperms	pointer to store number of permutations
nmaxperms	pointer to store maximal number of permutations (needed for freeing storage)
perms	pointer to store permutation generators as (nperms x npermvars) matrix
log10groupsize	pointer to store log10 of size of group
nmovedvars	pointer to store number of moved vars
binvaraffected	pointer to store wether a binary variable is affected by symmetry
compressed	pointer to store whether compression has been performed
success	pointer to store whether symmetry computation was successful

Definition at line 1380 of file prop_symmetry.c.

References checkSymmetriesAreSymmetries(), collectCoefficients(), SYM_Vartype::color, FALSE, getNSymhandableConss(), SYM_Vartype::lb, SYM_Matrixdata::matcoef, SYM_Matrixdata::matcoefcolors, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, MAX, SYM_Vartype::nconss, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::nmaxmatcoef, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, SYM_Sortrhstype::nrhscoef, NULL, SYM_Matrixdata::nuniquemat, SYM_Matrixdata::nuniquerhs, SYM_Matrixdata::nuniquevars, SYM_Vartype::obj, SYM_Matrixdata::permvarcolors, SYM_Matrixdata::permvars, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhscoefcolors, SYM_Matrixdata::rhsidx, SYM_Matrixdata::rhssense, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_ERROR, SCIP_INVALID, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIP_SPECIALVAL, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_SOLVING, SCIP_VERBLEVEL_HIGH, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemoryArray, SCIPblkmem(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsActive(), SCIPconsIsConflict(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetBinvarsLinking(), SCIPgetBoundsBounddisjunction(), SCIPgetBoundtypesBounddisjunction(), SCIPgetCapacityKnapsack(), SCIPgetConss(), SCIPgetIntVarXor(), SCIPgetLhsLinear(), SCIPgetLhsVarbound(), SCIPgetLinkvarLinking(), SCIPgetNActiveConss(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNFixedVars(), SCIPgetNVars(), SCIPgetNVarsAnd(), SCIPgetNVarsBounddisjunction(), SCIPgetNVarsKnapsack(), SCIPgetNVarsLinear(), SCIPgetNVarsLogicor(), SCIPgetNVarsOr(), SCIPgetNVarsSetppc(), SCIPgetNVarsXor(), SCIPgetResultantAnd(), SCIPgetResultantOr(), SCIPgetRhsLinear(), SCIPgetRhsVarbound(), SCIPgetRhsXor(), SCIPgetStage(), SCIPgetTypeSetppc(), SCIPgetValsLinear(), SCIPgetValsLinking(), SCIPgetVars(), SCIPgetVarsAnd(), SCIPgetVarsBounddisjunction(), SCIPgetVarsKnapsack(), SCIPgetVarsLinear(), SCIPgetVarsLogicor(), SCIPgetVarsOr(), SCIPgetVarsSetppc(), SCIPgetVarsXor(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPgetWeightsKnapsack(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPinfinity(), SCIPisEQ(), SCIPisStopped(), SCIPisZero(), SCIPsort(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPverbMessage(), SYM_Sortrhstype::senses, setSymmetryData(), SYM_SENSE_AND, SYM_SENSE_BOUNDIS_TYPE_1, SYM_SENSE_BOUNDIS_TYPE_2, SYM_SENSE_EQUATION, SYM_SENSE_INEQUALITY, SYM_SENSE_OR, SYM_SENSE_UNKOWN, SYM_SENSE_XOR, SYMcanComputeSymmetry(), SYMcomputeSymmetryGenerators(), SymmetryFixVar(), TRUE, SYM_Vartype::type, SYM_Vartype::ub, and SYM_Sortrhstype::vals.

Referenced by determineSymmetry().

◆ determineSymmetry()

static SCIP_RETCODE determineSymmetry	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SYM_SPEC	symspecrequire,
		SYM_SPEC	symspecrequirefixed
	)

static

determines symmetry

Parameters

scip	SCIP instance
propdata	propagator data
symspecrequire	symmetry specification for which we need to compute symmetries
symspecrequirefixed	symmetry specification of variables which must be fixed by symmetries

Definition at line 2107 of file prop_symmetry.c.

References checkSymmetryDataFree(), computeSymmetryGroup(), delSymConss(), FALSE, freeSymmetryData(), getNSymhandableConss(), MAXGENNUMERATOR, NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIP_VERBLEVEL_HIGH, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcaptureVar(), SCIPcatchVarEvent(), SCIPcomputeComponentsSym(), SCIPdetermineNVarsAffectedSym(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetNActiveBenders(), SCIPgetNActiveConss(), SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNRuns(), SCIPgetNVars(), SCIPgetSolvingTime(), SCIPhashmapCreate(), SCIPhashmapInsertInt(), SCIPisReoptEnabled(), SCIPmarkDoNotMultaggrVar(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarIsBinary(), SCIPverbMessage(), SCIPwarningMessage(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, SYMcanComputeSymmetry(), and TRUE.

Referenced by propagateOrbitalFixing(), SCIP_DECL_PROPPRESOL(), and tryAddSymmetryHandlingConss().

◆ detectOrbitopes()

static SCIP_RETCODE detectOrbitopes	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		int *	components,
		int *	componentbegins,
		int	ncomponents
	)

static

checks whether components of the symmetry group can be completely handled by orbitopes

Parameters

scip	SCIP instance
propdata	pointer to data of symmetry propagator
components	array containing components of symmetry group
componentbegins	array containing begin positions of components in components array
ncomponents	number of components

Definition at line 2499 of file prop_symmetry.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateConsOrbitope(), SCIPextendSubOrbitope(), SCIPfreeBufferArray, SCIPgenerateOrbitopeVarsMatrix(), SCIPgetPropertiesPerm(), and TRUE.

Referenced by tryAddSymmetryHandlingConss().

◆ addSymresackConss()

static SCIP_RETCODE addSymresackConss	(	SCIP *	scip,
		SCIP_PROP *	prop,
		int *	components,
		int *	componentbegins,
		int	ncomponents
	)

static

adds symresack constraints

Parameters

scip	SCIP instance
prop	symmetry breaking propagator
components	array containing components of symmetry group
componentbegins	array containing begin positions of components in components array
ncomponents	number of components

Definition at line 2766 of file prop_symmetry.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPpropGetData(), SCIPsnprintf(), and TRUE.

Referenced by tryAddSymmetryHandlingConss().

◆ tryAddSymmetryHandlingConss()

static SCIP_RETCODE tryAddSymmetryHandlingConss	(	SCIP *	scip,
		SCIP_PROP *	prop,
		SCIP_Bool *	earlyterm
	)

static

finds problem symmetries

Parameters

scip	SCIP instance
prop	symmetry breaking propagator
earlyterm	pointer to store whether we terminated early (or NULL)

Definition at line 2871 of file prop_symmetry.c.

References addSymresackConss(), detectOrbitopes(), determineSymmetry(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPisStopped(), SCIPpropGetData(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.

Referenced by SCIP_DECL_PROPEXITPRE(), SCIP_DECL_PROPINITPRE(), and SCIP_DECL_PROPPRESOL().

◆ performOrbitalFixing()

static SCIP_RETCODE performOrbitalFixing	(	SCIP *	scip,
		SCIP_VAR **	permvars,
		int	npermvars,
		int *	orbits,
		int *	orbitbegins,
		int	norbits,
		SCIP_Bool *	infeasible,
		int *	nfixedzero,
		int *	nfixedone
	)

static

performs orbital fixing

Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be fixed.

Parameters

scip	SCIP pointer
permvars	variables
npermvars	number of variables
orbits	array of non-trivial orbits
orbitbegins	array containing begin positions of new orbits in orbits array
norbits	number of orbits
infeasible	pointer to store whether problem is infeasible
nfixedzero	pointer to store number of variables fixed to 0
nfixedone	pointer to store number of variables fixed to 1

Definition at line 2974 of file prop_symmetry.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propagateOrbitalFixing().

◆ computeBranchingVariables()

static SCIP_RETCODE computeBranchingVariables	(	SCIP *	scip,
		int	nvars,
		SCIP_HASHMAP *	varmap,
		SCIP_Shortbool *	bg1,
		int *	bg1list,
		int *	nbg1
	)

static

Gets branching variables on the path to root

The variables are added to bg1 and bg1list, which are prefilled with the variables globally fixed to 1.

Parameters

scip	SCIP pointer
nvars	number of variables
varmap	map of variables to indices in vars array
bg1	bitset marking the variables globally fixed or branched to 1
bg1list	array to store the variable indices globally fixed or branched to 1
nbg1	pointer to store the number of variables in bg1 and bg1list

Definition at line 3112 of file prop_symmetry.c.

References NULL, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPboundchgGetBoundchgtype(), SCIPboundchgGetVar(), SCIPdomchgGetBoundchg(), SCIPdomchgGetNBoundchgs(), SCIPgetCurrentNode(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPnodeGetDepth(), SCIPnodeGetDomchg(), SCIPnodeGetParent(), SCIPprintNodeRootPath(), SCIPvarGetLbLocal(), SCIPvarGetType(), and TRUE.

Referenced by propagateOrbitalFixing().

◆ propagateOrbitalFixing()

static SCIP_RETCODE propagateOrbitalFixing	(	SCIP *	scip,
		SCIP_PROPDATA *	propdata,
		SCIP_Bool *	infeasible,
		int *	nprop
	)

static

propagates orbital fixing

Parameters

scip	SCIP pointer
propdata	data of symmetry breaking propagator
infeasible	pointer to store whether the node is detected to be infeasible
nprop	pointer to store the number of propagations

Definition at line 3204 of file prop_symmetry.c.

References computeBranchingVariables(), determineSymmetry(), FALSE, NULL, performOrbitalFixing(), SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPallocBufferArray, SCIPcomputeOrbitsFilterSym(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPisEQ(), SCIPvarGetLbGlobal(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.

Referenced by SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPPRESOL().

◆ SCIP_DECL_PROPINITPRE()

static SCIP_DECL_PROPINITPRE ( propInitpreSymmetry )

static

presolving initialization method of propagator (called when presolving is about to begin)

Definition at line 3472 of file prop_symmetry.c.

References FALSE, ISORBITALFIXINGACTIVE, ISSYMRETOPESACTIVE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetIntParam(), SCIPpropGetData(), TRUE, and tryAddSymmetryHandlingConss().

◆ SCIP_DECL_PROPEXITPRE()

static SCIP_DECL_PROPEXITPRE ( propExitpreSymmetry )

static

presolving deinitialization method of propagator (called after presolving has been finished)

Definition at line 3512 of file prop_symmetry.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPdebugMsg, SCIPgetStatus(), SCIPpropGetData(), SCIPpropGetName(), and tryAddSymmetryHandlingConss().

◆ SCIP_DECL_PROPPRESOL()

static SCIP_DECL_PROPPRESOL ( propPresolSymmetry )

static

presolving method of propagator

Definition at line 3539 of file prop_symmetry.c.

References determineSymmetry(), FALSE, NULL, PROP_NAME, propagateOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PROPTIMING_ALWAYS, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIPconsGetName(), SCIPdebugMsg, SCIPgetStage(), SCIPisPresolveFinished(), SCIPisStopped(), SCIPpresolCons(), SCIPpropGetData(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, TRUE, and tryAddSymmetryHandlingConss().

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecSymmetry )

static

execution method of propagator

Definition at line 3658 of file prop_symmetry.c.

References FALSE, ISORBITALFIXINGACTIVE, ISSYMRETOPESACTIVE, NULL, propagateOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetIntParam(), SCIPgetStage(), SCIPinProbing(), SCIPinRepropagation(), SCIPnodeGetNumber(), SCIPpropGetData(), SCIPpropGetName(), and TRUE.

◆ SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitSymmetry )

static

deinitialization method of propagator (called before transformed problem is freed)

Definition at line 3739 of file prop_symmetry.c.

References FALSE, freeSymmetryData(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPpropGetData(), and SCIPpropGetName().

◆ SCIP_DECL_PROPRESPROP()

static SCIP_DECL_PROPRESPROP ( propRespropSymmetry )

static

propagation conflict resolving method of propagator

Note that this is relatively difficult to obtain: One needs to include all bounds of variables that are responsible for creating the orbit in which the variables that was propagated lies. This includes all variables that are moved by the permutations which are involved in creating the orbit.

Definition at line 3780 of file prop_symmetry.c.

References NULL, SCIP_DIDNOTFIND, and SCIP_OKAY.

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeSymmetry )

static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 3792 of file prop_symmetry.c.

References NULL, PROP_NAME, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropGetName().

◆ SCIPincludePropSymmetry()

SCIP_RETCODE SCIPincludePropSymmetry ( SCIP * scip )

include symmetry propagator

Parameters

scip	SCIP data structure

Definition at line 3816 of file prop_symmetry.c.

References DEFAULT_ADDCONSSTIMING, DEFAULT_ADDSYMRESACKS, DEFAULT_CHECKSYMMETRIES, DEFAULT_COMPRESSSYMMETRIES, DEFAULT_COMPRESSTHRESHOLD, DEFAULT_CONSSADDLP, DEFAULT_DETECTORBITOPES, DEFAULT_DISABLEOFRESTART, DEFAULT_DISPLAYNORBITVARS, DEFAULT_DOUBLEEQUATIONS, DEFAULT_MAXGENERATORS, DEFAULT_OFSYMCOMPTIMING, DEFAULT_PERFORMPRESOLVING, DEFAULT_RECOMPUTERESTART, DEFAULT_SYMFIXNONBINARYVARS, DEFAULT_USECOLUMNSPARSITY, EVENTHDLR_SYMMETRY_DESC, EVENTHDLR_SYMMETRY_NAME, FALSE, NULL, PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRESOL_MAXROUNDS, PROP_PRESOL_PRIORITY, PROP_PRESOLTIMING, PROP_PRIORITY, PROP_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPincludeEventhdlrBasic(), SCIPincludeExternalCodeInformation(), SCIPincludePropBasic(), SCIPincludeTable(), SCIPsetPropExit(), SCIPsetPropExitpre(), SCIPsetPropFree(), SCIPsetPropInitpre(), SCIPsetPropPresol(), SCIPsetPropResprop(), SYMcanComputeSymmetry(), SYMsymmetryGetDesc(), SYMsymmetryGetName(), TABLE_DESC_ORBITALFIXING, TABLE_EARLIEST_ORBITALFIXING, TABLE_NAME_ORBITALFIXING, TABLE_POSITION_ORBITALFIXING, and TRUE.

Referenced by SCIPincludeDefaultPlugins().

◆ SCIPgetSymmetry()

SCIP_RETCODE SCIPgetSymmetry	(	SCIP *	scip,
		int *	npermvars,
		SCIP_VAR ***	permvars,
		SCIP_HASHMAP **	permvarmap,
		int *	nperms,
		int ***	perms,
		int ***	permstrans,
		SCIP_Real *	log10groupsize,
		SCIP_Bool *	binvaraffected,
		int **	components,
		int **	componentbegins,
		int **	vartocomponent,
		int *	ncomponents
	)

return currently available symmetry group information

Parameters

scip	SCIP data structure
npermvars	pointer to store number of variables for permutations
permvars	pointer to store variables on which permutations act
permvarmap	pointer to store hash map of permvars (or NULL)
nperms	pointer to store number of permutations
perms	pointer to store permutation generators as (nperms x npermvars) matrix (or NULL)
permstrans	pointer to store permutation generators as (npermvars x nperms) matrix (or NULL)
log10groupsize	pointer to store log10 of group size (or NULL)
binvaraffected	pointer to store whether binary variables are affected
components	pointer to store components of symmetry group (or NULL)
componentbegins	pointer to store begin positions of components in components array (or NULL)
vartocomponent	pointer to store assignment from variable to its component (or NULL)
ncomponents	pointer to store number of components (or NULL)

Definition at line 3993 of file prop_symmetry.c.

References NULL, PROP_NAME, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPerrorMessage, SCIPfindProp(), SCIPpropGetData(), and SCIPpropGetName().

Referenced by initOrbits().

◆ SCIPisOrbitalfixingEnabled()

SCIP_Bool SCIPisOrbitalfixingEnabled ( SCIP * scip )

return whether orbital fixing is enabled

Parameters

scip	SCIP data structure

Definition at line 4073 of file prop_symmetry.c.

References FALSE, NULL, PROP_NAME, SCIPfindProp(), and SCIPpropGetData().

Referenced by isRestartApplicable().

◆ SCIPgetSymmetryNGenerators()

int SCIPgetSymmetryNGenerators ( SCIP * scip )

return number of the symmetry group's generators

Parameters

scip	SCIP data structure

Definition at line 4093 of file prop_symmetry.c.

References NULL, PROP_NAME, SCIPfindProp(), and SCIPpropGetData().

Referenced by isRestartApplicable().

SCIP

Detailed Description

Symmetry Computation

Symmetry Handling Constraints

Orbital Fixing

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ PROP_NAME

◆ PROP_DESC

◆ PROP_TIMING

◆ PROP_PRIORITY

◆ PROP_FREQ

◆ PROP_DELAY

◆ PROP_PRESOL_PRIORITY

◆ PROP_PRESOLTIMING

◆ PROP_PRESOL_MAXROUNDS

◆ DEFAULT_MAXGENERATORS

◆ DEFAULT_CHECKSYMMETRIES

◆ DEFAULT_DISPLAYNORBITVARS

◆ DEFAULT_USECOLUMNSPARSITY

◆ DEFAULT_DOUBLEEQUATIONS

◆ DEFAULT_COMPRESSSYMMETRIES

◆ DEFAULT_COMPRESSTHRESHOLD

◆ DEFAULT_SYMFIXNONBINARYVARS

◆ DEFAULT_CONSSADDLP

◆ DEFAULT_ADDSYMRESACKS

◆ DEFAULT_DETECTORBITOPES

◆ DEFAULT_ADDCONSSTIMING

◆ DEFAULT_OFSYMCOMPTIMING

◆ DEFAULT_PERFORMPRESOLVING

◆ DEFAULT_RECOMPUTERESTART

◆ DEFAULT_DISABLEOFRESTART

◆ EVENTHDLR_SYMMETRY_NAME

◆ EVENTHDLR_SYMMETRY_DESC

◆ TABLE_NAME_ORBITALFIXING

◆ TABLE_DESC_ORBITALFIXING

◆ TABLE_POSITION_ORBITALFIXING

◆ TABLE_EARLIEST_ORBITALFIXING

◆ MAXGENNUMERATOR

◆ SCIP_SPECIALVAL

◆ COMPRESSNVARSLB

◆ ISSYMRETOPESACTIVE

◆ ISORBITALFIXINGACTIVE

Typedef Documentation

◆ SYM_SORTRHSTYPE

Function Documentation

◆ SCIP_DECL_EVENTEXEC()

◆ SCIP_DECL_TABLEOUTPUT()

◆ SCIP_DECL_TABLEFREE()

◆ SCIP_DECL_HASHGETKEY()

◆ SCIP_DECL_HASHKEYEQ()

◆ SCIP_DECL_HASHKEYVAL()

◆ SCIP_DECL_SORTINDCOMP() [1/2]

◆ SCIP_DECL_SORTINDCOMP() [2/2]

◆ checkSymmetryDataFree()

◆ freeSymmetryData()

◆ delSymConss()

◆ SymmetryFixVar()

◆ getActiveVariables()

◆ collectCoefficients()

◆ checkSymmetriesAreSymmetries()

◆ getNSymhandableConss()

◆ setSymmetryData()

◆ computeSymmetryGroup()

◆ determineSymmetry()

◆ detectOrbitopes()

◆ addSymresackConss()

◆ tryAddSymmetryHandlingConss()

◆ performOrbitalFixing()

◆ computeBranchingVariables()

◆ propagateOrbitalFixing()

◆ SCIP_DECL_PROPINITPRE()

◆ SCIP_DECL_PROPEXITPRE()

◆ SCIP_DECL_PROPPRESOL()

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPEXIT()

◆ SCIP_DECL_PROPRESPROP()