prop_symmetry.c File Reference

Detailed Description

propagator for handling symmetries

Author

Marc Pfetsch

Thomas Rehn

Christopher Hojny

Fabian Wegscheider

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.

Cuts derived from the Schreier Sims table

SST cuts have been introduced by
D. Salvagnin: Symmetry Breaking Inequalities from the Schreier-Sims table. CPAIOR 2018 Proceedings, 521-529, 2018.

These inequalities are computed as follows. Throughout these procedure a set of so-called leaders is maintained. Initially the set of leaders is empty. In a first step, select a variable \(x_i\) and compute its orbit w.r.t. the symmetry group of the mixed-integer program. For each variable \(x_j\) in the orbit of \(x_i\), the inequality \(x_i \geq x_j\) is a valid symmetry handling inequality, which can be added to the mixed-integer program. We call \(x_i\) the leader of this inequality. Add the leader \(x_i\) to the set of leaders and compute the pointwise stabilizer of the leader set. In the next step, select a new variable, compute its orbit w.r.t. the stabilizer group of the leaders, add the inequalities based on this orbit, and add the new leader to the set of leaders. This procedure is iterated until the pointwise stabilizer group of the leaders has become trivial.

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/cons_nonlinear.h>
#include <scip/pub_expr.h>
#include <scip/misc.h>
#include <scip/scip_datastructures.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
struct	SYM_Sortgraphcompvars

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_ONLYBINARYSYMMETRY   TRUE
#define	DEFAULT_CONSSADDLP   TRUE
#define	DEFAULT_ADDSYMRESACKS   FALSE
#define	DEFAULT_DETECTORBITOPES   TRUE
#define	DEFAULT_DETECTSUBGROUPS   TRUE
#define	DEFAULT_ADDWEAKSBCS   TRUE
#define	DEFAULT_ADDSTRONGSBCS   FALSE
#define	DEFAULT_ADDCONSSTIMING   2
#define	DEFAULT_MAXNCONSSSUBGROUP   500000
#define	DEFAULT_USEDYNAMICPROP   TRUE
#define	DEFAULT_PREFERLESSROWS   TRUE
#define	DEFAULT_OFSYMCOMPTIMING   2
#define	DEFAULT_PERFORMPRESOLVING   FALSE
#define	DEFAULT_RECOMPUTERESTART   0
#define	DEFAULT_SSTTIEBREAKRULE   1
#define	DEFAULT_SSTLEADERRULE   0
#define	DEFAULT_SSTLEADERVARTYPE   14
#define	DEFAULT_ADDCONFLICTCUTS   TRUE
#define	DEFAULT_SSTADDCUTS   TRUE
#define	DEFAULT_SSTMIXEDCOMPONENTS   TRUE
#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)
#define	ISSSTACTIVE(x)   (((unsigned) x & SYM_HANDLETYPE_SST) != 0)
#define	ISSSTBINACTIVE(x)   (((unsigned) x & SCIP_SSTTYPE_BINARY) != 0)
#define	ISSSTINTACTIVE(x)   (((unsigned) x & SCIP_SSTTYPE_INTEGER) != 0)
#define	ISSSTIMPLINTACTIVE(x)   (((unsigned) x & SCIP_SSTTYPE_IMPLINT) != 0)
#define	ISSSTCONTACTIVE(x)   (((unsigned) x & SCIP_SSTTYPE_CONTINUOUS) != 0)

Typedefs
typedef struct SCIP_NodeData	SCIP_NODEDATA
typedef struct SYM_Sortrhstype	SYM_SORTRHSTYPE
typedef struct SYM_Sortgraphcompvars	SYM_SORTGRAPHCOMPVARS

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_DECL_SORTINDCOMP (SYMsortGraphCompVars)
static SCIP_Bool	checkSymmetryDataFree (SCIP_PROPDATA *propdata)
static SCIP_Bool	isLeadervartypeCompatible (SCIP_VAR *var, int leadervartype)
static SCIP_Bool	isSymmetryRecomputationRequired (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	setSymmetryMethodEnabledValues (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, SCIP_CONSHDLR *conshdlr_nonlinear)
static SCIP_Bool	hasNonlinearConstraints (SCIP_PROPDATA *propdata)
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, SCIP_CONSHDLR *conshdlr_nonlinear, int *npermvars, int *nbinpermvars, SCIP_VAR ***permvars, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, int *nmovedvars, SCIP_Bool **isnonlinvar, 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	checkTwoCyclePermsAreOrbitope (SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int *activeperms, int ntwocycles, int nactiveperms, int **orbitopevaridx, int *columnorder, int *nusedelems, int *nusedcols, SCIP_Shortbool *rowisbinary, SCIP_Bool *isorbitope, SCIP_Shortbool *activevars)
static SCIP_RETCODE	chooseOrderOfGenerators (SCIP *scip, SCIP_PROPDATA *propdata, int compidx, int **genorder, int *ntwocycleperms)
static SCIP_RETCODE	buildSubgroupGraph (SCIP *scip, SCIP_PROPDATA *propdata, int *genorder, int ntwocycleperms, int compidx, int **graphcomponents, int **graphcompbegins, int **compcolorbegins, int *ngraphcomponents, int *ncompcolors, int **usedperms, int *nusedperms, int usedpermssize, SCIP_Shortbool *permused)
static SCIP_RETCODE	addOrbitopeSubgroup (SCIP *scip, SCIP_PROPDATA *propdata, int *usedperms, int nusedperms, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int graphcoloridx, int nrows, int ncols, int *firstvaridx, int *compidxfirstrow, int **lexorder, int *nvarslexorder, int *maxnvarslexorder, SCIP_Bool mayinteract, SCIP_Bool *success)
static SCIP_RETCODE	addStrongSBCsSubgroup (SCIP *scip, SCIP_PROPDATA *propdata, int *graphcompbegins, int *graphcomponents, int graphcompidx, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
static SCIP_RETCODE	addWeakSBCsSubgroup (SCIP *scip, SCIP_PROPDATA *propdata, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int ncompcolors, int *chosencomppercolor, int *firstvaridxpercolor, int symgrpcompidx, int *naddedconss, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
static SCIP_RETCODE	adaptSymmetryDataSST (SCIP *scip, int **origperms, int **modifiedperms, int nperms, SCIP_VAR **origpermvars, SCIP_VAR **modifiedpermvars, int npermvars, int *leaders, int nleaders)
static int	getNOrbitopesInComp (SCIP_VAR **permvars, int *graphcomponents, int *graphcompbegins, int *compcolorbegins, int ncompcolors, int symcompsize)
static SCIP_RETCODE	detectAndHandleSubgroups (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	SCIPsortOrbitope (SCIP *scip, int **orbitopevaridx, SCIP_VAR ***vars, int nrows, int ncols)
static SCIP_RETCODE	detectOrbitopes (SCIP *scip, SCIP_PROPDATA *propdata, int *components, int *componentbegins, int ncomponents)
static SCIP_RETCODE	updateSymInfoConflictGraphSST (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_VAR **permvars, int npermvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *varmap, int *orbits, int *orbitbegins, int norbits)
static SCIP_RETCODE	createConflictGraphSST (SCIP *scip, SCIP_DIGRAPH **conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *permvarmap, SCIP_Bool *success)
static SCIP_RETCODE	freeConflictGraphSST (SCIP *scip, SCIP_DIGRAPH **conflictgraph, int nnodes)
static SCIP_RETCODE	addSymresackConss (SCIP *scip, SCIP_PROP *prop, int *components, int *componentbegins, int ncomponents)
static SCIP_RETCODE	addSSTConssOrbitAndUpdateSST (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_PROPDATA *propdata, SCIP_VAR **permvars, int *orbits, int *orbitbegins, int orbitidx, int orbitleaderidx, SCIP_Shortbool *orbitvarinconflict, int norbitvarinconflict, int *nchgbds, SCIP_Bool useconflictgraph)
static SCIP_RETCODE	selectOrbitLeaderSSTConss (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_HASHMAP *varmap, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, int leaderrule, int tiebreakrule, SCIP_VARTYPE leadervartype, int *orbitidx, int *leaderidx, SCIP_Shortbool *orbitvarinconflict, int *norbitvarinconflict, SCIP_Bool useconflictgraph, SCIP_Bool *success)
static SCIP_RETCODE	addSSTConss (SCIP *scip, SCIP_PROPDATA *propdata, int *nchgbds)
static SCIP_RETCODE	tryAddSymmetryHandlingConss (SCIP *scip, SCIP_PROP *prop, int *nchgbds, 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 162 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 163 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

PROP_TIMING

#define PROP_TIMING   SCIP_PROPTIMING_BEFORELP

propagation timing mask

Definition at line 164 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

PROP_PRIORITY

#define PROP_PRIORITY   -1000000

propagator priority

Definition at line 165 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

PROP_FREQ

#define PROP_FREQ   1

propagator frequency

Definition at line 166 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 167 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 169 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 170 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 171 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 175 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_CHECKSYMMETRIES

#define DEFAULT_CHECKSYMMETRIES   FALSE

Should all symmetries be checked after computation?

Definition at line 176 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 177 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 178 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_DOUBLEEQUATIONS

#define DEFAULT_DOUBLEEQUATIONS   FALSE

Double equations to positive/negative version?

Definition at line 179 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 180 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 181 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 182 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_ONLYBINARYSYMMETRY

#define DEFAULT_ONLYBINARYSYMMETRY   TRUE

Is only symmetry on binary variables used?

Definition at line 183 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 186 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_ADDSYMRESACKS

#define DEFAULT_ADDSYMRESACKS   FALSE

Add inequalities for symresacks for each generator?

Definition at line 187 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 188 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_DETECTSUBGROUPS

#define DEFAULT_DETECTSUBGROUPS   TRUE

Should we try to detect orbitopes in subgroups of the symmetry group?

Definition at line 189 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_ADDWEAKSBCS

#define DEFAULT_ADDWEAKSBCS   TRUE

Should we add weak SBCs for enclosing orbit of symmetric subgroups?

Definition at line 190 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_ADDSTRONGSBCS

#define DEFAULT_ADDSTRONGSBCS   FALSE

Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used?

Definition at line 191 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 192 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_MAXNCONSSSUBGROUP

#define DEFAULT_MAXNCONSSSUBGROUP   500000

Maximum number of constraints up to which subgroup structures are detected

Definition at line 193 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_USEDYNAMICPROP

#define DEFAULT_USEDYNAMICPROP   TRUE

whether dynamic propagation should be used for full orbitopes

Definition at line 194 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_PREFERLESSROWS

#define DEFAULT_PREFERLESSROWS   TRUE

Shall orbitopes with less rows be preferred in detection?

Definition at line 195 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 198 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_PERFORMPRESOLVING

#define DEFAULT_PERFORMPRESOLVING   FALSE

Run orbital fixing during presolving?

Definition at line 199 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_RECOMPUTERESTART

#define DEFAULT_RECOMPUTERESTART   0

Recompute symmetries after a restart has occurred? (0 = never, 1 = always, 2 = if OF found reduction)

Definition at line 200 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_SSTTIEBREAKRULE

#define DEFAULT_SSTTIEBREAKRULE   1

index of tie break rule for selecting orbit for Schreier Sims constraints?

Definition at line 203 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_SSTLEADERRULE

#define DEFAULT_SSTLEADERRULE   0

index of rule for selecting leader variables for Schreier Sims constraints?

Definition at line 204 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_SSTLEADERVARTYPE

#define DEFAULT_SSTLEADERVARTYPE   14

bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous); if multiple types are allowed, take the one with most affected vars

Definition at line 205 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_ADDCONFLICTCUTS

#define DEFAULT_ADDCONFLICTCUTS   TRUE

Should Schreier Sims constraints be added if we use a conflict based rule?

Definition at line 208 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_SSTADDCUTS

#define DEFAULT_SSTADDCUTS   TRUE

Should Schreier Sims constraints be added?

Definition at line 209 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

DEFAULT_SSTMIXEDCOMPONENTS

#define DEFAULT_SSTMIXEDCOMPONENTS   TRUE

Should Schreier Sims constraints be added if a symmetry component contains variables of different types?

Definition at line 210 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

EVENTHDLR_SYMMETRY_NAME

#define EVENTHDLR_SYMMETRY_NAME   "symmetry"

Definition at line 213 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 214 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

TABLE_NAME_ORBITALFIXING

#define TABLE_NAME_ORBITALFIXING   "orbitalfixing"

Definition at line 217 of file prop_symmetry.c.

Referenced by SCIPincludePropSymmetry().

TABLE_DESC_ORBITALFIXING

#define TABLE_DESC_ORBITALFIXING   "orbital fixing statistics"

Definition at line 218 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 219 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 220 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 224 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 225 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 226 of file prop_symmetry.c.

Referenced by setSymmetryData().

ISSYMRETOPESACTIVE

#define ISSYMRETOPESACTIVE

(

x

)

(((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0)

Definition at line 229 of file prop_symmetry.c.

Referenced by setSymmetryMethodEnabledValues().

ISORBITALFIXINGACTIVE

#define ISORBITALFIXINGACTIVE

(

x

)

(((unsigned) x & SYM_HANDLETYPE_ORBITALFIXING) != 0)

Definition at line 230 of file prop_symmetry.c.

Referenced by freeSymmetryData(), and setSymmetryMethodEnabledValues().

ISSSTACTIVE

#define ISSSTACTIVE

(

x

)

(((unsigned) x & SYM_HANDLETYPE_SST) != 0)

Definition at line 231 of file prop_symmetry.c.

Referenced by setSymmetryMethodEnabledValues().

ISSSTBINACTIVE

#define ISSSTBINACTIVE

(

x

)

(((unsigned) x & SCIP_SSTTYPE_BINARY) != 0)

Definition at line 233 of file prop_symmetry.c.

Referenced by addSSTConss(), and addSymresackConss().

ISSSTINTACTIVE

#define ISSSTINTACTIVE

(

x

)

(((unsigned) x & SCIP_SSTTYPE_INTEGER) != 0)

Definition at line 234 of file prop_symmetry.c.

Referenced by addSSTConss(), addSymresackConss(), and determineSymmetry().

ISSSTIMPLINTACTIVE

#define ISSSTIMPLINTACTIVE

(

x

)

(((unsigned) x & SCIP_SSTTYPE_IMPLINT) != 0)

Definition at line 235 of file prop_symmetry.c.

Referenced by addSSTConss(), addSymresackConss(), and determineSymmetry().

ISSSTCONTACTIVE

#define ISSSTCONTACTIVE

(

x

)

(((unsigned) x & SCIP_SSTTYPE_CONTINUOUS) != 0)

Definition at line 236 of file prop_symmetry.c.

Referenced by addSSTConss(), addSymresackConss(), and determineSymmetry().

Typedef Documentation

SCIP_NODEDATA

typedef struct SCIP_NodeData SCIP_NODEDATA

Definition at line 363 of file prop_symmetry.c.

SYM_SORTRHSTYPE

typedef struct SYM_Sortrhstype SYM_SORTRHSTYPE

Definition at line 559 of file prop_symmetry.c.

SYM_SORTGRAPHCOMPVARS

typedef struct SYM_Sortgraphcompvars SYM_SORTGRAPHCOMPVARS

Definition at line 567 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 379 of file prop_symmetry.c.

References EVENTHDLR_SYMMETRY_NAME, NULL, SCIP_DECL_TABLEOUTPUT(), 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 455 of file prop_symmetry.c.

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

Referenced by SCIP_DECL_EVENTEXEC().

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 479 of file prop_symmetry.c.

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

Referenced by SCIP_DECL_TABLEOUTPUT().

SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyVartype  )

static

gets the key of the given element

Definition at line 498 of file prop_symmetry.c.

References SCIP_DECL_HASHKEYEQ().

Referenced by SCIP_DECL_TABLEFREE().

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 508 of file prop_symmetry.c.

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

Referenced by SCIP_DECL_HASHGETKEY().

SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValVartype  )

static

returns the hash value of the key

Definition at line 543 of file prop_symmetry.c.

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

Referenced by SCIP_DECL_HASHKEYEQ().

SCIP_DECL_SORTINDCOMP() [1/3]

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 579 of file prop_symmetry.c.

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

Referenced by SCIP_DECL_SORTINDCOMP().

SCIP_DECL_SORTINDCOMP() [2/3]

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 613 of file prop_symmetry.c.

References SCIP_DECL_SORTINDCOMP(), and SCIP_Real.

SCIP_DECL_SORTINDCOMP() [3/3]

static SCIP_DECL_SORTINDCOMP ( SYMsortGraphCompVars  )

static

sorts variable indices according to their corresponding component in the graph

Variables are sorted first by the color of their component and then by the component index.

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 640 of file prop_symmetry.c.

References checkSymmetryDataFree(), SYM_Sortgraphcompvars::colors, SYM_Sortgraphcompvars::components, and SCIP_Bool.

checkSymmetryDataFree()

static SCIP_Bool checkSymmetryDataFree ( SCIP_PROPDATA *  propdata )

static

checks that symmetry data is all freed

Parameters

propdata

propagator data

Definition at line 668 of file prop_symmetry.c.

References FALSE, isLeadervartypeCompatible(), NULL, SCIP_Bool, and TRUE.

Referenced by determineSymmetry(), freeSymmetryData(), and SCIP_DECL_SORTINDCOMP().

isLeadervartypeCompatible()

static SCIP_Bool isLeadervartypeCompatible ( SCIP_VAR *  var, int  leadervartype  )

static

checks whether a variable has a type compatible with the leader vartype

Parameters

var	variable to check
leadervartype	bit set encoding possible leader variable types

Definition at line 717 of file prop_symmetry.c.

References isSymmetryRecomputationRequired(), NULL, SCIP_Bool, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, and SCIPvarGetType().

Referenced by checkSymmetryDataFree(), and determineSymmetry().

isSymmetryRecomputationRequired()

static SCIP_Bool isSymmetryRecomputationRequired ( SCIP *  scip, SCIP_PROPDATA *  propdata  )

static

returns whether a recomputation of symmetries is required

Parameters

scip	SCIP pointer
propdata	propagator data

Definition at line 746 of file prop_symmetry.c.

References FALSE, NULL, SCIP_RECOMPUTESYM_ALWAYS, SCIP_RECOMPUTESYM_NEVER, SCIP_RECOMPUTESYM_OFFOUNDRED, SCIPgetNRuns(), setSymmetryMethodEnabledValues(), and TRUE.

Referenced by determineSymmetry(), isLeadervartypeCompatible(), SCIP_DECL_PROPEXEC(), SCIP_DECL_PROPINITPRE(), and tryAddSymmetryHandlingConss().

setSymmetryMethodEnabledValues()

static SCIP_RETCODE setSymmetryMethodEnabledValues ( SCIP_PROPDATA *  propdata )

static

sets in propdata which symmetry handling methods are active

Parameters

propdata

propagator data

Definition at line 775 of file prop_symmetry.c.

References FALSE, freeSymmetryData(), ISORBITALFIXINGACTIVE, ISSSTACTIVE, ISSYMRETOPESACTIVE, NULL, SCIP_OKAY, and TRUE.

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

freeSymmetryData()

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

static

frees symmetry data

Parameters

scip	SCIP pointer
propdata	propagator data

Definition at line 802 of file prop_symmetry.c.

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

Referenced by determineSymmetry(), SCIP_DECL_PROPEXIT(), setSymmetryMethodEnabledValues(), and tryAddSymmetryHandlingConss().

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 1033 of file prop_symmetry.c.

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

Referenced by determineSymmetry(), freeSymmetryData(), and tryAddSymmetryHandlingConss().

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 1115 of file prop_symmetry.c.

References FALSE, getActiveVariables(), 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(), computeSymmetryGroup(), and delSymConss().

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_1*x_1 + ... + a_n*x_n + c
nvars	pointer to number of variables and values in vars and vals array
constant	pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c
transformed	transformed constraint?

Definition at line 1136 of file prop_symmetry.c.

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

Referenced by collectCoefficients(), and SymmetryFixVar().

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 1182 of file prop_symmetry.c.

References checkSymmetriesAreSymmetries(), FALSE, getActiveVariables(), SYM_Matrixdata::matcoef, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::nmaxmatcoef, SYM_Matrixdata::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, and TRUE.

Referenced by computeSymmetryGroup(), and getActiveVariables().

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 1409 of file prop_symmetry.c.

References FALSE, getNSymhandableConss(), SYM_Matrixdata::matcoef, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, NULL, SYM_Matrixdata::permvars, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhssense, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPcompareExpr(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMsg, SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetConsCopy(), SCIPgetConsNVars(), SCIPgetConsVars(), SCIPgetExprNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPhashmapRemoveAll(), SCIPisEQ(), SCIPisZero(), SCIPreleaseCons(), SCIPreleaseExpr(), SCIPsimplifyExpr(), SCIPvarGetProbindex(), SymmetryFixVar(), and TRUE.

Referenced by collectCoefficients(), and computeSymmetryGroup().

getNSymhandableConss()

static int getNSymhandableConss ( SCIP *  scip, SCIP_CONSHDLR *  conshdlr_nonlinear  )

static

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

Parameters

scip	SCIP instance
conshdlr_nonlinear	nonlinear constraint handler, if included

Definition at line 1667 of file prop_symmetry.c.

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

Referenced by checkSymmetriesAreSymmetries(), computeSymmetryGroup(), and determineSymmetry().

hasNonlinearConstraints()

static SCIP_Bool hasNonlinearConstraints ( SCIP_PROPDATA *  propdata )

static

returns whether there are any active nonlinear constraints

Parameters

propdata

propagator data

Definition at line 1705 of file prop_symmetry.c.

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

Referenced by getNSymhandableConss(), propagateOrbitalFixing(), SCIP_DECL_PROPEXITPRE(), SCIP_DECL_PROPINITPRE(), SCIP_DECL_PROPPRESOL(), and tryAddSymmetryHandlingConss().

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 1716 of file prop_symmetry.c.

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

Referenced by computeSymmetryGroup(), and hasNonlinearConstraints().

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, SCIP_CONSHDLR *  conshdlr_nonlinear, int *  npermvars, int *  nbinpermvars, SCIP_VAR ***  permvars, int *  nperms, int *  nmaxperms, int ***  perms, SCIP_Real *  log10groupsize, int *  nmovedvars, SCIP_Bool **  isnonlinvar, 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?
conshdlr_nonlinear	Nonlinear constraint handler, if included
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
isnonlinvar	pointer to store which variables appear nonlinearly
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 1847 of file prop_symmetry.c.

References checkSymmetriesAreSymmetries(), collectCoefficients(), SYM_Vartype::color, determineSymmetry(), 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_Exprdata::nuniquecoefs, SYM_Exprdata::nuniqueconstants, SYM_Matrixdata::nuniquemat, SYM_Exprdata::nuniqueoperators, 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_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, 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(), SCIPconshdlrGetNActiveConss(), SCIPconshdlrGetName(), SCIPconsIsActive(), SCIPconsIsConflict(), SCIPconsIsTransformed(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPexprGetNChildren(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterGetParentDFS(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeExpriter(), SCIPgetBinvarsLinking(), SCIPgetBoundsBounddisjunction(), SCIPgetBoundtypesBounddisjunction(), SCIPgetCapacityKnapsack(), SCIPgetConss(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprNonlinear(), 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(), SCIPgetVarExprVar(), SCIPgetVars(), SCIPgetVarsAnd(), SCIPgetVarsBounddisjunction(), SCIPgetVarsKnapsack(), SCIPgetVarsLinear(), SCIPgetVarsLogicor(), SCIPgetVarsOr(), SCIPgetVarsSetppc(), SCIPgetVarsXor(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPgetWeightsKnapsack(), SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetInsert(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPinfinity(), SCIPisEQ(), SCIPisExprSum(), SCIPisExprValue(), SCIPisExprVar(), 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(), and setSymmetryData().

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 2662 of file prop_symmetry.c.

References checkSymmetryDataFree(), checkTwoCyclePermsAreOrbitope(), computeSymmetryGroup(), delSymConss(), FALSE, freeSymmetryData(), getNSymhandableConss(), isLeadervartypeCompatible(), ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, isSymmetryRecomputationRequired(), MAXGENNUMERATOR, NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_SSTTYPE_BINARY, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, 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 computeSymmetryGroup(), propagateOrbitalFixing(), SCIP_DECL_PROPEXITPRE(), SCIP_DECL_PROPINITPRE(), SCIP_DECL_PROPPRESOL(), and tryAddSymmetryHandlingConss().

checkTwoCyclePermsAreOrbitope()

static SCIP_RETCODE checkTwoCyclePermsAreOrbitope ( SCIP *  scip, SCIP_VAR **  permvars, int  npermvars, int **  perms, int *  activeperms, int  ntwocycles, int  nactiveperms, int **  orbitopevaridx, int *  columnorder, int *  nusedelems, int *  nusedcols, SCIP_Shortbool *  rowisbinary, SCIP_Bool *  isorbitope, SCIP_Shortbool *  activevars  )

static

Checks whether given set of 2-cycle permutations forms an orbitope and if so, builds the variable index matrix.

If activevars == NULL, then the function assumes all permutations of the component are active and therefore all moved vars are considered.

We need to keep track of the number of generatored columns, because we might not be able to detect all orbitopes. For example (1,2), (2,3), (3,4), (3,5) defines the symmetric group on {1,2,3,4,5}, but the generators we expect in our construction need shape (1,2), (2,3), (3,4), (4,5).

Precondition

orbitopevaridx has to be an initialized 2D array of size ntwocycles x nperms

columnorder has to be an initialized array of size nperms

nusedelems has to be an initialized array of size npermvars

Parameters

scip	SCIP instance
permvars	array of all permutation variables
npermvars	number of permutation variables
perms	array of all permutations of the symmety group
activeperms	indices of the relevant permutations in perms
ntwocycles	number of 2-cycles in the permutations
nactiveperms	number of active permutations
orbitopevaridx	pointer to store variable index matrix
columnorder	pointer to store column order
nusedelems	pointer to store how often each element was used
nusedcols	pointer to store numer of columns used in orbitope (or NULL)
rowisbinary	pointer to store which rows are binary (or NULL)
isorbitope	buffer to store result
activevars	bitset to store whether a variable is active (or NULL)

Definition at line 3169 of file prop_symmetry.c.

References chooseOrderOfGenerators(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPextendSubOrbitope(), SCIPfreeBufferArray, SCIPvarIsBinary(), and TRUE.

Referenced by addOrbitopeSubgroup(), detectOrbitopes(), and determineSymmetry().

chooseOrderOfGenerators()

static SCIP_RETCODE chooseOrderOfGenerators ( SCIP *  scip, SCIP_PROPDATA *  propdata, int  compidx, int **  genorder, int *  ntwocycleperms  )

static

choose an order in which the generators should be added for subgroup detection

Parameters

scip	SCIP instance
propdata	pointer to data of symmetry propagator
compidx	index of component
genorder	(initialized) buffer to store the resulting order of generator
ntwocycleperms	pointer to store the number of 2-cycle permutations in component compidx

Definition at line 3354 of file prop_symmetry.c.

References buildSubgroupGraph(), SYM_Sortgraphcompvars::components, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInvolutionPerm(), and SCIPsortIntInt().

Referenced by checkTwoCyclePermsAreOrbitope(), and detectAndHandleSubgroups().

buildSubgroupGraph()

static SCIP_RETCODE buildSubgroupGraph ( SCIP *  scip, SCIP_PROPDATA *  propdata, int *  genorder, int  ntwocycleperms, int  compidx, int **  graphcomponents, int **  graphcompbegins, int **  compcolorbegins, int *  ngraphcomponents, int *  ncompcolors, int **  usedperms, int *  nusedperms, int  usedpermssize, SCIP_Shortbool *  permused  )

static

builds the graph for symmetric subgroup detection from the given permutation of generators

After execution, graphcomponents contains all permvars sorted by their color and component, graphcompbegins points to the indices where new components in graphcomponents start and compcolorbegins points to the indices where new colors in graphcompbegins start.

Parameters

scip	SCIP instance
propdata	pointer to data of symmetry propagator
genorder	order in which the generators should be considered
ntwocycleperms	number of 2-cycle permutations in this component
compidx	index of the component
graphcomponents	buffer to store the components of the graph (ordered var indices)
graphcompbegins	buffer to store the indices of each new graph component
compcolorbegins	buffer to store at which indices a new color begins
ngraphcomponents	pointer to store the number of graph components
ncompcolors	pointer to store the number of different colors
usedperms	buffer to store the indices of permutations that were used
nusedperms	pointer to store the number of used permutations in the graph
usedpermssize	initial size of usedperms
permused	initialized buffer to store which permutations have been used (identified by index in component)

Definition at line 3432 of file prop_symmetry.c.

References addOrbitopeSubgroup(), SYM_Sortgraphcompvars::colors, SYM_Sortgraphcompvars::components, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetGetComponentCount(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPfreeDisjointset(), SCIPreallocBufferArray, SCIPsort(), and TRUE.

Referenced by chooseOrderOfGenerators(), and detectAndHandleSubgroups().

addOrbitopeSubgroup()

static SCIP_RETCODE addOrbitopeSubgroup ( SCIP *  scip, SCIP_PROPDATA *  propdata, int *  usedperms, int  nusedperms, int *  compcolorbegins, int *  graphcompbegins, int *  graphcomponents, int  graphcoloridx, int  nrows, int  ncols, int *  firstvaridx, int *  compidxfirstrow, int **  lexorder, int *  nvarslexorder, int *  maxnvarslexorder, SCIP_Bool  mayinteract, SCIP_Bool *  success  )

static

adds an orbitope constraint for a suitable color of the subgroup graph

Parameters

scip	SCIP instance
propdata	pointer to data of symmetry propagator
usedperms	array of the permutations that build the orbitope
nusedperms	number of permutations in usedperms
compcolorbegins	array indicating where a new graphcolor begins
graphcompbegins	array indicating where a new graphcomponent begins
graphcomponents	array of all variable indices sorted by color and comp
graphcoloridx	index of the graph color
nrows	number of rows in the orbitope
ncols	number of columns in the orbitope
firstvaridx	buffer to store the index of the largest variable (or NULL)
compidxfirstrow	buffer to store the comp index for the first row (or NULL)
lexorder	pointer to array storing lexicographic order defined by sub orbitopes
nvarslexorder	number of variables in lexicographic order
maxnvarslexorder	maximum number of variables in lexicographic order
mayinteract	whether orbitope's symmetries might interact with other symmetries
success	whether the orbitpe could be added

Definition at line 3699 of file prop_symmetry.c.

References addStrongSBCsSubgroup(), checkTwoCyclePermsAreOrbitope(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_Shortbool, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateConsOrbitope(), SCIPfreeBufferArray, SCIPgenerateOrbitopeVarsMatrix(), SCIPsnprintf(), SCIPvarIsBinary(), and TRUE.

Referenced by buildSubgroupGraph(), and detectAndHandleSubgroups().

addStrongSBCsSubgroup()

static SCIP_RETCODE addStrongSBCsSubgroup ( SCIP *  scip, SCIP_PROPDATA *  propdata, int *  graphcompbegins, int *  graphcomponents, int  graphcompidx, SCIP_Bool  storelexorder, int **  lexorder, int *  nvarsorder, int *  maxnvarsorder  )

static

adds strong SBCs for a suitable color of the subgroup graph

Parameters

scip	SCIP instance
propdata	pointer to data of symmetry propagator
graphcompbegins	array indicating where a new graphcomponent begins
graphcomponents	array of all variable indices sorted by color and comp
graphcompidx	index of the graph component
storelexorder	whether the lexicographic order induced by the orbitope shall be stored
lexorder	pointer to array storing lexicographic order defined by sub orbitopes
nvarsorder	number of variables in lexicographic order
maxnvarsorder	maximum number of variables in lexicographic order

Definition at line 3910 of file prop_symmetry.c.

References addWeakSBCsSubgroup(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPcreateConsLinear(), SCIPinfinity(), SCIPinfoMessage(), SCIPprintCons(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPvarGetName(), and TRUE.

Referenced by addOrbitopeSubgroup(), and detectAndHandleSubgroups().

addWeakSBCsSubgroup()

static SCIP_RETCODE addWeakSBCsSubgroup ( SCIP *  scip, SCIP_PROPDATA *  propdata, int *  compcolorbegins, int *  graphcompbegins, int *  graphcomponents, int  ncompcolors, int *  chosencomppercolor, int *  firstvaridxpercolor, int  symgrpcompidx, int *  naddedconss, SCIP_Bool  storelexorder, int **  lexorder, int *  nvarsorder, int *  maxnvarsorder  )

static

adds weak SBCs for a suitable color of the subgroup graph

Parameters

scip	SCIP instance
propdata	pointer to data of symmetry propagator
compcolorbegins	array indicating where a new graphcolor begins
graphcompbegins	array indicating where a new graphcomponent begins
graphcomponents	array of all variable indices sorted by color and comp
ncompcolors	number of colors in the graph
chosencomppercolor	array indicating which comp was handled per color
firstvaridxpercolor	array indicating the largest variable per color
symgrpcompidx	index of the component of the symmetry group
naddedconss	buffer to store the number of added constraints
storelexorder	whether the lexicographic order induced by the orbitope shall be stored
lexorder	pointer to array storing lexicographic order defined by sub orbitopes
nvarsorder	number of variables in lexicographic order
maxnvarsorder	maximum number of variables in lexicographic order

Definition at line 4004 of file prop_symmetry.c.

References adaptSymmetryDataSST(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPallocClearBufferArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPcomputeOrbitVar(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapInsertInt(), SCIPinfinity(), SCIPinfoMessage(), SCIPprintCons(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPvarGetName(), and TRUE.

Referenced by addStrongSBCsSubgroup(), and detectAndHandleSubgroups().

adaptSymmetryDataSST()

static SCIP_RETCODE adaptSymmetryDataSST ( SCIP *  scip, int **  origperms, int **  modifiedperms, int  nperms, SCIP_VAR **  origpermvars, SCIP_VAR **  modifiedpermvars, int  npermvars, int *  leaders, int  nleaders  )

static

temporarily adapt symmetry data to new variable order given by Schreier Sims

Parameters

scip	SCIP instance
origperms	permutation matrix w.r.t. original variable ordering
modifiedperms	memory for permutation matrix w.r.t. new variable ordering
nperms	number of permutations
origpermvars	array of permutation vars w.r.t. original variable ordering
modifiedpermvars	memory for array of permutation vars w.r.t. new variable ordering
npermvars	length or modifiedpermvars array
leaders	leaders of Schreier Sims constraints
nleaders	number of leaders

Definition at line 4249 of file prop_symmetry.c.

References getNOrbitopesInComp(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by addSymresackConss(), addWeakSBCsSubgroup(), and detectAndHandleSubgroups().

getNOrbitopesInComp()

static int getNOrbitopesInComp ( SCIP_VAR **  permvars, int *  graphcomponents, int *  graphcompbegins, int *  compcolorbegins, int  ncompcolors, int  symcompsize  )

static

Parameters

permvars	array of variables affected by symmetry
graphcomponents	array of graph components
graphcompbegins	array indicating starting position of graph components
compcolorbegins	array indicating starting positions of potential orbitopes
ncompcolors	number of components encoded in compcolorbegins
symcompsize	size of symmetry component for that we detect suborbitopes

Definition at line 4331 of file prop_symmetry.c.

References detectAndHandleSubgroups(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPvarIsBinary(), and TRUE.

Referenced by adaptSymmetryDataSST(), and detectAndHandleSubgroups().

detectAndHandleSubgroups()

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

static

checks whether subgroups of the components are symmetric groups and adds SBCs for them

Parameters

scip	SCIP instance
propdata	pointer to data of symmetry propagator

Definition at line 4414 of file prop_symmetry.c.

References adaptSymmetryDataSST(), addOrbitopeSubgroup(), addStrongSBCsSubgroup(), addWeakSBCsSubgroup(), buildSubgroupGraph(), chooseOrderOfGenerators(), FALSE, getNOrbitopesInComp(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Shortbool, SCIP_VERBLEVEL_HIGH, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNConss(), SCIPsnprintf(), SCIPsortOrbitope(), SCIPvarGetName(), SCIPvarIsBinary(), SCIPvarIsIntegral(), SCIPverbMessage(), SYM_HANDLETYPE_SYMBREAK, and TRUE.

Referenced by getNOrbitopesInComp(), and tryAddSymmetryHandlingConss().

SCIPsortOrbitope()

static SCIP_RETCODE SCIPsortOrbitope ( SCIP *  scip, int **  orbitopevaridx, SCIP_VAR ***  vars, int  nrows, int  ncols  )

static

sorts orbitope vars matrix such that rows are sorted increasingly w.r.t. minimum variable index in row; columns are sorted such that first row is sorted increasingly w.r.t. variable indices

Parameters

scip	SCIP instance
orbitopevaridx	variable index matrix of orbitope
vars	variable matrix of orbitope
nrows	number of binary rows of orbitope
ncols	number of columns of orbitope

Definition at line 4935 of file prop_symmetry.c.

References detectOrbitopes(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortIntIntPtr(), and SCIPsortIntPtr().

Referenced by detectAndHandleSubgroups(), and detectOrbitopes().

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 5017 of file prop_symmetry.c.

References checkTwoCyclePermsAreOrbitope(), SYM_Sortgraphcompvars::components, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_Shortbool, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateConsOrbitope(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgenerateOrbitopeVarsMatrix(), SCIPisInvolutionPerm(), SCIPsnprintf(), SCIPsortOrbitope(), SYM_HANDLETYPE_SYMBREAK, TRUE, and updateSymInfoConflictGraphSST().

Referenced by SCIPsortOrbitope(), and tryAddSymmetryHandlingConss().

updateSymInfoConflictGraphSST()

static SCIP_RETCODE updateSymInfoConflictGraphSST ( SCIP *  scip, SCIP_DIGRAPH *  conflictgraph, SCIP_VAR **  graphvars, int  ngraphvars, SCIP_VAR **  permvars, int  npermvars, SCIP_Bool  onlypermvars, SCIP_HASHMAP *  varmap, int *  orbits, int *  orbitbegins, int  norbits  )

static

update symmetry information of conflict graph

Parameters

scip	SCIP instance
conflictgraph	conflict graph
graphvars	variables encoded in conflict graph (either all vars or permvars)
ngraphvars	number of nodes/vars in conflict graph
permvars	variables considered in permutations
npermvars	number of permvars
onlypermvars	whether conflict graph contains only permvars
varmap	map from graphvar to node label in conflict graph (or NULL if onlypermvars == TRUE)
orbits	array of non-trivial orbits
orbitbegins	array containing begin positions of new orbits in orbits array
norbits	number of non-trivial orbits

Definition at line 5222 of file prop_symmetry.c.

References createConflictGraphSST(), nodedata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), and TRUE.

Referenced by addSSTConss(), and detectOrbitopes().

createConflictGraphSST()

static SCIP_RETCODE createConflictGraphSST ( SCIP *  scip, SCIP_DIGRAPH **  conflictgraph, SCIP_VAR **  graphvars, int  ngraphvars, SCIP_Bool  onlypermvars, SCIP_HASHMAP *  permvarmap, SCIP_Bool *  success  )

static

create conflict graph either for symmetric or for all variables

This routine just creates the graph, but does not add (symmetry) information to its nodes. This has to be done separately by the routine updateSymInfoConflictGraphSST().

Parameters

scip	SCIP instance
conflictgraph	pointer to store conflict graph
graphvars	variables encoded in conflict graph
ngraphvars	number of vars encoded in conflict graph
onlypermvars	whether conflict graph contains only permvars
permvarmap	map of variables to indices in permvars array (or NULL)
success	pointer to store whether conflict graph could be created successfully

Definition at line 5367 of file prop_symmetry.c.

References FALSE, freeConflictGraphSST(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_COVERING, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateDigraph(), SCIPdebugMsg, SCIPdigraphAddArcSafe(), SCIPfindConshdlr(), SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPhashmapGetImageInt(), SCIPvarGetProbindex(), and TRUE.

Referenced by addSSTConss(), and updateSymInfoConflictGraphSST().

freeConflictGraphSST()

static SCIP_RETCODE freeConflictGraphSST ( SCIP *  scip, SCIP_DIGRAPH **  conflictgraph, int  nnodes  )

static

frees conflict graph

Parameters

scip	SCIP instance
conflictgraph	conflict graph
nnodes	number of nodes in conflict graph

Definition at line 5491 of file prop_symmetry.c.

References addSymresackConss(), nnodes, nodedata, NULL, SCIP_OKAY, SCIPdigraphFree(), SCIPdigraphGetNodeData(), and SCIPfreeBlockMemory.

Referenced by addSSTConss(), and createConflictGraphSST().

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 5528 of file prop_symmetry.c.

References adaptSymmetryDataSST(), addSSTConssOrbitAndUpdateSST(), SYM_Sortgraphcompvars::components, FALSE, ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPpropGetData(), SCIPsnprintf(), SYM_HANDLETYPE_ORBITALFIXING, SYM_HANDLETYPE_SST, SYM_HANDLETYPE_SYMBREAK, and TRUE.

Referenced by freeConflictGraphSST(), and tryAddSymmetryHandlingConss().

addSSTConssOrbitAndUpdateSST()

static SCIP_RETCODE addSSTConssOrbitAndUpdateSST ( SCIP *  scip, SCIP_DIGRAPH *  conflictgraph, SCIP_PROPDATA *  propdata, SCIP_VAR **  permvars, int *  orbits, int *  orbitbegins, int  orbitidx, int  orbitleaderidx, SCIP_Shortbool *  orbitvarinconflict, int  norbitvarinconflict, int *  nchgbds, SCIP_Bool  useconflictgraph  )

static

add Schreier Sims constraints for a specific orbit and update Schreier Sims table

Parameters

scip	SCIP instance
conflictgraph	conflict graph or NULL if useconflictgraph == FALSE
propdata	data of symmetry propagator
permvars	permvars array
orbits	symmetry orbits
orbitbegins	array storing begin position for each orbit
orbitidx	index of orbit for Schreier Sims constraints
orbitleaderidx	index of leader variable for Schreier Sims constraints
orbitvarinconflict	indicator whether orbitvar is in conflict with orbit leader
norbitvarinconflict	number of variables in conflict with orbit leader
nchgbds	pointer to store number of bound changes (or NULL)
useconflictgraph	whether conflict graph shall be used

Definition at line 5692 of file prop_symmetry.c.

References FALSE, nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_LEADERRULE_MAXCONFLICTS, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPchgVarUb(), SCIPcreateConsLinear(), SCIPdigraphGetNodeData(), SCIPinfinity(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), selectOrbitLeaderSSTConss(), and TRUE.

Referenced by addSSTConss(), and addSymresackConss().

selectOrbitLeaderSSTConss()

static SCIP_RETCODE selectOrbitLeaderSSTConss ( SCIP *  scip, SCIP_DIGRAPH *  conflictgraph, SCIP_VAR **  graphvars, int  ngraphvars, SCIP_HASHMAP *  varmap, SCIP_VAR **  permvars, int  npermvars, int *  orbits, int *  orbitbegins, int  norbits, int  leaderrule, int  tiebreakrule, SCIP_VARTYPE  leadervartype, int *  orbitidx, int *  leaderidx, SCIP_Shortbool *  orbitvarinconflict, int *  norbitvarinconflict, SCIP_Bool  useconflictgraph, SCIP_Bool *  success  )

static

selection rule of next orbit/leader in orbit for Schreier Sims constraints

Parameters

scip	SCIP instance
conflictgraph	conflict graph or NULL if useconflictgraph == FALSE
graphvars	variables encoded in conflict graph
ngraphvars	number of variables encoded in conflict graph
varmap	map from variable to node label in conflict graph or NULL if useconflictgraph == FALSE
permvars	vars encoded in a permutation
npermvars	number of vars in a permutation
orbits	orbits of stabilizer subgroup
orbitbegins	array storing the begin position of each orbit in orbits
norbits	number of orbits
leaderrule	rule to select leader
tiebreakrule	tie break rule to select leader
leadervartype	variable type of leader
orbitidx	pointer to index of selected orbit
leaderidx	pointer to leader in orbit
orbitvarinconflict	array to store whether a var in the orbit is conflicting with leader
norbitvarinconflict	pointer to store number of vars in the orbit in conflict with leader
useconflictgraph	whether conflict graph shall be used
success	pointer to store whether orbit cut be selected successfully

Definition at line 5852 of file prop_symmetry.c.

References addSSTConss(), FALSE, nodedata, NULL, SCIP_LEADERRULE_FIRSTINORBIT, SCIP_LEADERRULE_LASTINORBIT, SCIP_LEADERRULE_MAXCONFLICTS, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXORBIT, SCIP_LEADERTIEBREAKRULE_MINORBIT, SCIP_OKAY, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPhashmapGetImageInt(), SCIPvarGetProbindex(), SCIPvarGetType(), and TRUE.

Referenced by addSSTConss(), and addSSTConssOrbitAndUpdateSST().

addSSTConss()

static SCIP_RETCODE addSSTConss ( SCIP *  scip, SCIP_PROPDATA *  propdata, int *  nchgbds  )

static

add Schreier Sims constraints to the problem

Parameters

scip	SCIP instance
propdata	datas of symmetry propagator
nchgbds	pointer to store number of bound changes (or NULL)

Definition at line 6101 of file prop_symmetry.c.

References addSSTConssOrbitAndUpdateSST(), SYM_Sortgraphcompvars::components, createConflictGraphSST(), FALSE, freeConflictGraphSST(), ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LEADERRULE_FIRSTINORBIT, SCIP_LEADERRULE_MAXCONFLICTS, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXORBIT, SCIP_OKAY, SCIP_Shortbool, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPblkmem(), SCIPcomputeOrbitsFilterSym(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapInsertInt(), SCIPvarGetType(), selectOrbitLeaderSSTConss(), SYM_HANDLETYPE_SST, TRUE, tryAddSymmetryHandlingConss(), and updateSymInfoConflictGraphSST().

Referenced by selectOrbitLeaderSSTConss(), and tryAddSymmetryHandlingConss().

tryAddSymmetryHandlingConss()

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

static

finds problem symmetries

Parameters

scip	SCIP instance
prop	symmetry breaking propagator
nchgbds	pointer to store number of bound changes (or NULL)
earlyterm	pointer to store whether we terminated early (or NULL)

Definition at line 6424 of file prop_symmetry.c.

References addSSTConss(), addSymresackConss(), delSymConss(), detectAndHandleSubgroups(), detectOrbitopes(), determineSymmetry(), FALSE, freeSymmetryData(), hasNonlinearConstraints(), isSymmetryRecomputationRequired(), NULL, performOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPfreeBlockMemoryArrayNull, SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNRuns(), SCIPisStopped(), SCIPpropGetData(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.

Referenced by addSSTConss(), 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 6586 of file prop_symmetry.c.

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

Referenced by propagateOrbitalFixing(), and tryAddSymmetryHandlingConss().

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 6724 of file prop_symmetry.c.

References NULL, propagateOrbitalFixing(), 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 performOrbitalFixing(), and 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 6816 of file prop_symmetry.c.

References SYM_Sortgraphcompvars::components, computeBranchingVariables(), determineSymmetry(), FALSE, hasNonlinearConstraints(), NULL, performOrbitalFixing(), SCIP_CALL, SCIP_DECL_PROPINITPRE(), 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 computeBranchingVariables(), 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 7084 of file prop_symmetry.c.

References determineSymmetry(), hasNonlinearConstraints(), isSymmetryRecomputationRequired(), NULL, SCIP_CALL, SCIP_DECL_PROPEXITPRE(), SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPdebugMsg, SCIPfindConshdlr(), SCIPgetIntParam(), SCIPgetNRuns(), SCIPpropGetData(), SCIPverbMessage(), setSymmetryMethodEnabledValues(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and tryAddSymmetryHandlingConss().

Referenced by propagateOrbitalFixing().

SCIP_DECL_PROPEXITPRE()

static SCIP_DECL_PROPEXITPRE ( propExitpreSymmetry  )

static

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

Definition at line 7139 of file prop_symmetry.c.

References determineSymmetry(), hasNonlinearConstraints(), NULL, PROP_NAME, SCIP_CALL, SCIP_DECL_PROPPRESOL(), SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPdebugMsg, SCIPgetStatus(), SCIPpropGetData(), SCIPpropGetName(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and tryAddSymmetryHandlingConss().

Referenced by SCIP_DECL_PROPINITPRE().

SCIP_DECL_PROPPRESOL()

static SCIP_DECL_PROPPRESOL ( propPresolSymmetry  )

static

presolving method of propagator

Definition at line 7181 of file prop_symmetry.c.

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

Referenced by SCIP_DECL_PROPEXITPRE().

SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecSymmetry  )

static

execution method of propagator

Definition at line 7337 of file prop_symmetry.c.

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

Referenced by SCIP_DECL_PROPPRESOL().

SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitSymmetry  )

static

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

Definition at line 7416 of file prop_symmetry.c.

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

Referenced by SCIP_DECL_PROPEXEC().

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 7458 of file prop_symmetry.c.

References NULL, SCIP_DECL_PROPFREE(), SCIP_DIDNOTFIND, and SCIP_OKAY.

Referenced by SCIP_DECL_PROPEXIT().

SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeSymmetry  )

static

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

Definition at line 7470 of file prop_symmetry.c.

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

Referenced by SCIP_DECL_PROPRESPROP().

SCIPincludePropSymmetry()

SCIP_RETCODE SCIPincludePropSymmetry

(

SCIP *

scip

)

include symmetry propagator

Parameters

scip	SCIP data structure

Definition at line 7494 of file prop_symmetry.c.

References DEFAULT_ADDCONFLICTCUTS, DEFAULT_ADDCONSSTIMING, DEFAULT_ADDSTRONGSBCS, DEFAULT_ADDSYMRESACKS, DEFAULT_ADDWEAKSBCS, DEFAULT_CHECKSYMMETRIES, DEFAULT_COMPRESSSYMMETRIES, DEFAULT_COMPRESSTHRESHOLD, DEFAULT_CONSSADDLP, DEFAULT_DETECTORBITOPES, DEFAULT_DETECTSUBGROUPS, DEFAULT_DISPLAYNORBITVARS, DEFAULT_DOUBLEEQUATIONS, DEFAULT_MAXGENERATORS, DEFAULT_MAXNCONSSSUBGROUP, DEFAULT_OFSYMCOMPTIMING, DEFAULT_ONLYBINARYSYMMETRY, DEFAULT_PERFORMPRESOLVING, DEFAULT_PREFERLESSROWS, DEFAULT_RECOMPUTERESTART, DEFAULT_SSTADDCUTS, DEFAULT_SSTLEADERRULE, DEFAULT_SSTLEADERVARTYPE, DEFAULT_SSTMIXEDCOMPONENTS, DEFAULT_SSTTIEBREAKRULE, DEFAULT_SYMFIXNONBINARYVARS, DEFAULT_USECOLUMNSPARSITY, DEFAULT_USEDYNAMICPROP, 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, SCIPgetSymmetry(), 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 SCIP_DECL_PROPFREE(), and 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 (or NULL)
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 7751 of file prop_symmetry.c.

References SYM_Sortgraphcompvars::components, NULL, PROP_NAME, SCIP_Bool, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPerrorMessage, SCIPfindProp(), SCIPisOrbitalfixingEnabled(), SCIPpropGetData(), and SCIPpropGetName().

Referenced by initOrbits(), and SCIPincludePropSymmetry().

SCIPisOrbitalfixingEnabled()

SCIP_Bool SCIPisOrbitalfixingEnabled

(

SCIP *

scip

)

return whether orbital fixing is enabled

Parameters

scip	SCIP data structure

Definition at line 7831 of file prop_symmetry.c.

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

Referenced by SCIPgetSymmetry().

SCIPgetSymmetryNGenerators()

int SCIPgetSymmetryNGenerators

(

SCIP *

scip

)

return number of the symmetry group's generators

Parameters

scip	SCIP data structure

Definition at line 7851 of file prop_symmetry.c.

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

Referenced by SCIPisOrbitalfixingEnabled().