prop_symmetry.c File Reference

Detailed Description

propagator for handling symmetries

Author

Marc Pfetsch

Thomas Rehn

Christopher Hojny

Fabian Wegscheider

Jasper van Doornmalen

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 implements various methods to handle the symmetries:
  • orbital reduction, which generalizes orbital fixing. See symmetry_orbital.c
  • (dynamic) orbitopal reduction, which generalizes (dynamic) orbital fixing. See symmetry_orbitopal.c
  • static orbitopal fixing (for binary variable domains) for full orbitopes. See cons_orbitope.c
  • static orbitopal fixing (for binary variable domains) for packing-partitioning orbitopes. See cons_orbitope.c
  • (dynamic) lexicographic reduction. See symmetry_lexred.c
  • static lexicographic fixing for binary variable domains (i.e., symresack propagation). See cons_symresack.c
  • static lexicographic fixing for binary variable domains on involutions (i.e., orbisacks). See cons_orbisack.c
  • Symmetry breaking inequalities based on the Schreier-Sims Table (i.e., SST cuts).
  • Strong and weak symmetry breaking inequalities.

Symmetry Computation

The generic functionality of the compute_symmetry.h interface is used. 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 by the (unified) symmetry handling constraints

Many common methods are captured by a framework that dynamifies symmetry handling constraints. The ideas are described in
J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023, https://doi.org/10.48550/arXiv.2211.01295.

This paper shows that various symmetry handling methods are compatible under certain conditions, and provides generalizations to common symmetry handling constraints from binary variable domains to arbitrary variable domains. This includes symresack propagation, orbitopal fixing, and orbital fixing, that are generalized to lexicographic reduction, orbitopal reduction and orbital reduction, respectively. For a description and implementation, see symmetry_lexred.c, symmetry_orbitopal.c and symmetry_orbital.c, respectively. The static counterparts on binary variable domains are cons_symresack.c and cons_orbisack.c for lexicographic reduction (cf. symresack propagation), and cons_orbitope.c and cons_orbisack.c for orbitopal reduction (cf. orbitopal fixing). We refer to the description of tryAddSymmetryHandlingMethods for the order in which these methods are applied.

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_indicator.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_sos1.h"
#include "scip/cons_sos2.h"
#include "scip/expr_pow.h"
#include "scip/expr_product.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/event_shadowtree.h"
#include "scip/symmetry.h"
#include "scip/symmetry_graph.h"
#include "scip/symmetry_orbitopal.h"
#include "scip/symmetry_orbital.h"
#include "scip/symmetry_lexred.h"
#include <math.h>
#include <string.h>

Go to the source code of this file.

Data Structures
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_ENFORCECOMPUTESYMMETRY   FALSE
#define	DEFAULT_SYMTYPE   (int) SYM_SYMTYPE_PERM
#define	DEFAULT_CONSSADDLP   TRUE
#define	DEFAULT_ADDSYMRESACKS   TRUE
#define	DEFAULT_DETECTDOUBLELEX   TRUE
#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_SYMCOMPTIMING   2
#define	DEFAULT_PERFORMPRESOLVING   0
#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	TABLE_NAME_SYMMETRY   "symmetry"
#define	TABLE_DESC_SYMMETRY   "symmetry handling statistics"
#define	TABLE_POSITION_SYMMETRY   7001
#define	TABLE_EARLIEST_SYMMETRY   SCIP_STAGE_SOLVING
#define	MAXGENNUMERATOR   64000000
#define	COMPRESSNVARSLB   25000
#define	DEFAULT_NAUTYMAXNCELLS   100000
#define	DEFAULT_NAUTYMAXNNODES   10000000
#define	ISSYMRETOPESACTIVE(x)   (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0)
#define	ISORBITALREDUCTIONACTIVE(x)   (((unsigned) x & SYM_HANDLETYPE_ORBITALREDUCTION) != 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)
#define	SYMMETRY_STATISTICS   1

Typedefs
typedef struct SCIP_ConflictData	SCIP_CONFLICTDATA
typedef struct SYM_Sortgraphcompvars	SYM_SORTGRAPHCOMPVARS

Functions
static	SCIP_DECL_SORTPTRCOMP (sortByPointerValue)
static SCIP_Bool	checkSortedArraysHaveOverlappingEntry (void **arr1, int narr1, void **arr2, int narr2, SCIP_DECL_SORTPTRCOMP((*compfunc)))
static SCIP_RETCODE	displayCycleOfSymmetry (SCIP *scip, int *perm, SYM_SYMTYPE symtype, int baseidx, SCIP_Bool *covered, int nvars, SCIP_VAR **vars)
static SCIP_RETCODE	displaySymmetriesWithoutComponents (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	displaySymmetriesWithComponents (SCIP *scip, SCIP_PROPDATA *propdata)
static	SCIP_DECL_DIALOGEXEC (dialogExecDisplaySymmetry)
static	SCIP_DECL_TABLEOUTPUT (tableOutputSymmetry)
static	SCIP_DECL_TABLEFREE (tableFreeSymmetry)
static	SCIP_DECL_SORTINDCOMP (SYMsortGraphCompVars)
static int	compareSymgraphs (SCIP *scip, SYM_GRAPH *G1, SYM_GRAPH *G2)
static	SCIP_DECL_SORTINDCOMP (SYMsortSymgraphs)
static SCIP_Bool	checkSymmetryDataFree (SCIP_PROPDATA *propdata)
static SCIP_RETCODE	resetDynamicSymmetryHandling (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	freeSymmetryData (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	ensureDynamicConsArrayAllocatedAndSufficientlyLarge (SCIP *scip, SCIP_CONS ***consarrptr, int *consarrsizeptr, int consarrsizereq)
static SCIP_RETCODE	setSymmetryData (SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR **vars, int nvars, int nbinvars, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, SCIP_Real **permvardomaincenter, int **perms, int nperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool *compressed)
static SCIP_Bool	conshdlrCanProvideSymInformation (SCIP_CONSHDLR *conshdlr, SYM_SYMTYPE symtype)
static SCIP_Bool	conshdlrsCanProvideSymInformation (SCIP *scip, SYM_SYMTYPE symtype)
static SCIP_RETCODE	estimateSymgraphSize (SCIP *scip, int *nopnodes, int *nvalnodes, int *nconsnodes, int *nedges)
static SCIP_RETCODE	checkSymmetriesAreSymmetries (SCIP *scip, SYM_SYMTYPE symtype, int **perms, int nperms, int npermvars, SYM_SPEC fixedtype)
static SCIP_RETCODE	computeSymmetryGroup (SCIP *scip, SYM_SYMTYPE symtype, SCIP_Bool compresssymmetries, SCIP_Real compressthreshold, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool checksymmetries, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, SCIP_Real **permvardomaincenter, int ***perms, int *nperms, int *nmaxperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool *compressed, SCIP_Real *log10groupsize, SCIP_Real *symcodetime, SCIP_Bool *success)
static SCIP_Bool	isNonstandardPerm (SCIP *scip, int *symmetry, SCIP_VAR **vars, int nvars)
static SCIP_RETCODE	checkComponentsForNonstandardPerms (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	ensureSymmetryComponentsComputed (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	ensureSymmetryPermvarmapComputed (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	ensureSymmetryPermstransComputed (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	ensureSymmetryMovedpermvarscountsComputed (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_Bool	testSymmetryComputationRequired (SCIP *scip, SCIP_PROPDATA *propdata)
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, int cidx)
static SCIP_RETCODE	updateSymInfoConflictGraphSST (SCIP *scip, SCIP_CONFLICTDATA *varconflicts, SCIP_VAR **conflictvars, int nconflictvars, int *orbits, int *orbitbegins, int norbits)
static SCIP_RETCODE	createConflictGraphSST (SCIP *scip, SCIP_CONFLICTDATA **varconflicts, SCIP_VAR **conflictvars, int nconflictvars, SCIP_HASHMAP *conflictvarmap)
static SCIP_RETCODE	freeConflictGraphSST (SCIP *scip, SCIP_CONFLICTDATA **varconflicts, int nvars)
static SCIP_RETCODE	addSymresackConss (SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
static SCIP_RETCODE	addSSTConssOrbitAndUpdateSST (SCIP *scip, SCIP_CONFLICTDATA *varconflicts, SCIP_PROPDATA *propdata, SCIP_VAR **permvars, int *orbits, int *orbitbegins, int orbitidx, int orbitleaderidx, SCIP_Shortbool *orbitvarinconflict, int norbitvarinconflict, int *nchgbds)
static SCIP_RETCODE	selectOrbitLeaderSSTConss (SCIP *scip, SCIP_CONFLICTDATA *varconflicts, SCIP_VAR **conflictvars, int nconflictvars, int *orbits, int *orbitbegins, int norbits, int leaderrule, int tiebreakrule, SCIP_VARTYPE leadervartype, int *orbitidx, int *leaderidx, SCIP_Shortbool *orbitvarinconflict, int *norbitvarinconflict, SCIP_Bool *success)
static SCIP_RETCODE	addSSTConss (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool onlywithcontvars, int *nchgbds, int cidx)
static SCIP_RETCODE	addOrbitopesDynamic (SCIP *scip, SCIP_PROPDATA *propdata, int id, int **varidxmatrix, int nrows, int ncols, SCIP_Bool *success)
static SCIP_RETCODE	componentPackingPartitioningOrbisackUpgrade (SCIP *scip, SCIP_PROPDATA *propdata, int **componentperms, int componentsize, SCIP_Bool hassignedperm, SCIP_Bool *success)
static SCIP_RETCODE	tryAddOrbitalRedLexRed (SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
static SCIP_RETCODE	SCIPdisplaySymmetryStatistics (SCIP *scip, SCIP_PROPDATA *propdata)
static SCIP_RETCODE	handleOrbitope (SCIP *scip, SCIP_PROPDATA *propdata, int id, int **varidxmatrix, int nrows, int ncols, SCIP_Bool *success)
static SCIP_RETCODE	handleDoublelLexMatrix (SCIP *scip, SCIP_PROPDATA *propdata, int id, int **varidxmatrix, int nrows, int ncols, int *rowsbegin, int *colsbegin, int nrowblocks, int ncolblocks, SCIP_Bool *success)
static SCIP_RETCODE	tryHandleSingleOrDoubleLexMatricesComponent (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool detectsinglelex, int cidx)
static SCIP_RETCODE	tryHandleSubgroups (SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
static SCIP_RETCODE	tryAddSymmetryHandlingMethodsComponent (SCIP *scip, SCIP_PROPDATA *propdata, int cidx, int *nchgbds)
static SCIP_RETCODE	tryAddSymmetryHandlingMethods (SCIP *scip, SCIP_PROP *prop, int *nchgbds, SCIP_Bool *earlyterm)
static SCIP_RETCODE	propagateSymmetry (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
static	SCIP_DECL_PROPINITPRE (propInitpreSymmetry)
static	SCIP_DECL_PROPEXITPRE (propExitpreSymmetry)
static	SCIP_DECL_PROPEXITSOL (propExitsolSymmetry)
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)
int	SCIPgetSymmetryNGenerators (SCIP *scip)
SCIP_RETCODE	SCIPcreateSymOpNodeType (SCIP *scip, const char *opnodename, int *nodetype)
SCIP_RETCODE	SCIPgetSymOpNodeType (SCIP *scip, const char *opnodename, int *nodetype)

Macro Definition Documentation

PROP_NAME

#define PROP_NAME   "symmetry"

Definition at line 141 of file prop_symmetry.c.

PROP_DESC

#define PROP_DESC   "propagator for handling symmetry"

Definition at line 142 of file prop_symmetry.c.

PROP_TIMING

#define PROP_TIMING   SCIP_PROPTIMING_BEFORELP

propagation timing mask

Definition at line 143 of file prop_symmetry.c.

PROP_PRIORITY

#define PROP_PRIORITY   -1000000

propagator priority

Definition at line 144 of file prop_symmetry.c.

PROP_FREQ

#define PROP_FREQ   1

propagator frequency

Definition at line 145 of file prop_symmetry.c.

PROP_DELAY

#define PROP_DELAY   FALSE

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

Definition at line 146 of file prop_symmetry.c.

PROP_PRESOL_PRIORITY

#define PROP_PRESOL_PRIORITY   -10000000

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

Definition at line 148 of file prop_symmetry.c.

PROP_PRESOLTIMING

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

Definition at line 149 of file prop_symmetry.c.

PROP_PRESOL_MAXROUNDS

#define PROP_PRESOL_MAXROUNDS   -1

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

Definition at line 150 of file prop_symmetry.c.

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

DEFAULT_CHECKSYMMETRIES

#define DEFAULT_CHECKSYMMETRIES   FALSE

Should all symmetries be checked after computation?

Definition at line 155 of file prop_symmetry.c.

DEFAULT_DISPLAYNORBITVARS

#define DEFAULT_DISPLAYNORBITVARS   FALSE

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

Definition at line 156 of file prop_symmetry.c.

DEFAULT_USECOLUMNSPARSITY

#define DEFAULT_USECOLUMNSPARSITY   FALSE

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

Definition at line 157 of file prop_symmetry.c.

DEFAULT_DOUBLEEQUATIONS

#define DEFAULT_DOUBLEEQUATIONS   FALSE

Double equations to positive/negative version?

Definition at line 158 of file prop_symmetry.c.

DEFAULT_COMPRESSSYMMETRIES

#define DEFAULT_COMPRESSSYMMETRIES   TRUE

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

Definition at line 159 of file prop_symmetry.c.

DEFAULT_COMPRESSTHRESHOLD

#define DEFAULT_COMPRESSTHRESHOLD   0.5

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

Definition at line 160 of file prop_symmetry.c.

DEFAULT_SYMFIXNONBINARYVARS

#define DEFAULT_SYMFIXNONBINARYVARS   FALSE

Disabled parameter

Definition at line 161 of file prop_symmetry.c.

DEFAULT_ENFORCECOMPUTESYMMETRY

#define DEFAULT_ENFORCECOMPUTESYMMETRY   FALSE

always compute symmetries, even if they cannot be handled

Definition at line 162 of file prop_symmetry.c.

DEFAULT_SYMTYPE

#define DEFAULT_SYMTYPE   (int) SYM_SYMTYPE_PERM

type of symmetries to be computed

Definition at line 163 of file prop_symmetry.c.

DEFAULT_CONSSADDLP

#define DEFAULT_CONSSADDLP   TRUE

Should the symmetry breaking constraints be added to the LP?

Definition at line 166 of file prop_symmetry.c.

DEFAULT_ADDSYMRESACKS

#define DEFAULT_ADDSYMRESACKS   TRUE

Add inequalities for symresacks for each generator?

Definition at line 167 of file prop_symmetry.c.

DEFAULT_DETECTDOUBLELEX

#define DEFAULT_DETECTDOUBLELEX   TRUE

Should we check whether the components of the symmetry group can be handled by double lex matrices?

Definition at line 168 of file prop_symmetry.c.

DEFAULT_DETECTORBITOPES

#define DEFAULT_DETECTORBITOPES   TRUE

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

Definition at line 169 of file prop_symmetry.c.

DEFAULT_DETECTSUBGROUPS

#define DEFAULT_DETECTSUBGROUPS   TRUE

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

Definition at line 170 of file prop_symmetry.c.

DEFAULT_ADDWEAKSBCS

#define DEFAULT_ADDWEAKSBCS   TRUE

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

Definition at line 171 of file prop_symmetry.c.

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

DEFAULT_ADDCONSSTIMING

#define DEFAULT_ADDCONSSTIMING   2

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

Definition at line 173 of file prop_symmetry.c.

DEFAULT_MAXNCONSSSUBGROUP

#define DEFAULT_MAXNCONSSSUBGROUP   500000

Maximum number of constraints up to which subgroup structures are detected

Definition at line 174 of file prop_symmetry.c.

DEFAULT_USEDYNAMICPROP

#define DEFAULT_USEDYNAMICPROP   TRUE

whether dynamic propagation should be used for full orbitopes

Definition at line 175 of file prop_symmetry.c.

DEFAULT_PREFERLESSROWS

#define DEFAULT_PREFERLESSROWS   TRUE

Shall orbitopes with less rows be preferred in detection?

Definition at line 176 of file prop_symmetry.c.

DEFAULT_SYMCOMPTIMING

#define DEFAULT_SYMCOMPTIMING   2

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

Definition at line 179 of file prop_symmetry.c.

DEFAULT_PERFORMPRESOLVING

#define DEFAULT_PERFORMPRESOLVING   0

Run orbital fixing during presolving? (disabled parameter)

Definition at line 180 of file prop_symmetry.c.

DEFAULT_RECOMPUTERESTART

#define DEFAULT_RECOMPUTERESTART   0

Recompute symmetries after a restart has occurred? (0 = never)

Definition at line 181 of file prop_symmetry.c.

DEFAULT_SSTTIEBREAKRULE

#define DEFAULT_SSTTIEBREAKRULE   1

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

Definition at line 184 of file prop_symmetry.c.

DEFAULT_SSTLEADERRULE

#define DEFAULT_SSTLEADERRULE   0

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

Definition at line 185 of file prop_symmetry.c.

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

DEFAULT_ADDCONFLICTCUTS

#define DEFAULT_ADDCONFLICTCUTS   TRUE

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

Definition at line 188 of file prop_symmetry.c.

DEFAULT_SSTADDCUTS

#define DEFAULT_SSTADDCUTS   TRUE

Should Schreier Sims constraints be added?

Definition at line 189 of file prop_symmetry.c.

DEFAULT_SSTMIXEDCOMPONENTS

#define DEFAULT_SSTMIXEDCOMPONENTS   TRUE

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

Definition at line 190 of file prop_symmetry.c.

TABLE_NAME_SYMMETRY

#define TABLE_NAME_SYMMETRY   "symmetry"

Definition at line 193 of file prop_symmetry.c.

TABLE_DESC_SYMMETRY

#define TABLE_DESC_SYMMETRY   "symmetry handling statistics"

Definition at line 194 of file prop_symmetry.c.

TABLE_POSITION_SYMMETRY

#define TABLE_POSITION_SYMMETRY   7001

the position of the statistics table

Definition at line 195 of file prop_symmetry.c.

TABLE_EARLIEST_SYMMETRY

#define TABLE_EARLIEST_SYMMETRY   SCIP_STAGE_SOLVING

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

Definition at line 196 of file prop_symmetry.c.

MAXGENNUMERATOR

#define MAXGENNUMERATOR   64000000

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

Definition at line 200 of file prop_symmetry.c.

COMPRESSNVARSLB

#define COMPRESSNVARSLB   25000

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

Definition at line 201 of file prop_symmetry.c.

DEFAULT_NAUTYMAXNCELLS

#define DEFAULT_NAUTYMAXNCELLS   100000

terminate symmetry detection using Nauty when number of cells in color refinment is at least this number (avoids segfaults due to Nauty for large graphs)

Definition at line 203 of file prop_symmetry.c.

DEFAULT_NAUTYMAXNNODES

#define DEFAULT_NAUTYMAXNNODES   10000000

terminate symmetry detection using Nauty when its search tree has at least this number of nodes

Definition at line 204 of file prop_symmetry.c.

ISSYMRETOPESACTIVE

#define ISSYMRETOPESACTIVE

(

x

)

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

Definition at line 209 of file prop_symmetry.c.

ISORBITALREDUCTIONACTIVE

#define ISORBITALREDUCTIONACTIVE

(

x

)

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

Definition at line 210 of file prop_symmetry.c.

ISSSTACTIVE

#define ISSSTACTIVE

(

x

)

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

Definition at line 211 of file prop_symmetry.c.

ISSSTBINACTIVE

#define ISSSTBINACTIVE

(

x

)

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

Definition at line 213 of file prop_symmetry.c.

ISSSTINTACTIVE

#define ISSSTINTACTIVE

(

x

)

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

Definition at line 214 of file prop_symmetry.c.

ISSSTIMPLINTACTIVE

#define ISSSTIMPLINTACTIVE

(

x

)

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

Definition at line 215 of file prop_symmetry.c.

ISSSTCONTACTIVE

#define ISSSTCONTACTIVE

(

x

)

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

Definition at line 216 of file prop_symmetry.c.

SYMMETRY_STATISTICS

#define SYMMETRY_STATISTICS   1

Definition at line 219 of file prop_symmetry.c.

Typedef Documentation

SCIP_CONFLICTDATA

typedef struct SCIP_ConflictData SCIP_CONFLICTDATA

Definition at line 337 of file prop_symmetry.c.

SYM_SORTGRAPHCOMPVARS

typedef struct SYM_Sortgraphcompvars SYM_SORTGRAPHCOMPVARS

Definition at line 699 of file prop_symmetry.c.

Function Documentation

SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( sortByPointerValue  )

static

compare function for sorting an array by the addresses of its members

Definition at line 342 of file prop_symmetry.c.

checkSortedArraysHaveOverlappingEntry()

static SCIP_Bool checkSortedArraysHaveOverlappingEntry ( void **  arr1, int  narr1, void **  arr2, int  narr2, SCIP_DECL_SORTPTRCOMP((*compfunc))    )

static

checks whether two arrays that are sorted with the same comparator have a common element

Parameters

arr1	first array
narr1	number of elements in first array
arr2	second array
narr2	number of elements in second array

Definition at line 355 of file prop_symmetry.c.

References FALSE, NULL, and TRUE.

Referenced by componentPackingPartitioningOrbisackUpgrade(), selectOrbitLeaderSSTConss(), and updateSymInfoConflictGraphSST().

displayCycleOfSymmetry()

static SCIP_RETCODE displayCycleOfSymmetry ( SCIP *  scip, int *  perm, SYM_SYMTYPE  symtype, int  baseidx, SCIP_Bool *  covered, int  nvars, SCIP_VAR **  vars  )

static

displays the cycle of a symmetry

Parameters

scip	SCIP pointer
perm	symmetry
symtype	type of symmetry
baseidx	variable index for which cycle is computed
covered	allocated array to store covered variables
nvars	number of (non-negated) variables in symmetry
vars	variables on which symmetry acts

Definition at line 424 of file prop_symmetry.c.

References NULL, SCIP_OKAY, SCIPinfoMessage(), SCIPvarGetName(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, and TRUE.

Referenced by checkSymmetriesAreSymmetries(), displaySymmetriesWithComponents(), and displaySymmetriesWithoutComponents().

displaySymmetriesWithoutComponents()

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

static

displays symmetry information without taking components into account

Parameters

scip	SCIP pointer
propdata	propagator data

Definition at line 469 of file prop_symmetry.c.

References displayCycleOfSymmetry(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPinfoMessage(), SYM_SYMTYPE_PERM, and SYM_SYMTYPE_SIGNPERM.

Referenced by SCIP_DECL_DIALOGEXEC().

displaySymmetriesWithComponents()

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

static

displays symmetry information taking components into account

Parameters

scip	SCIP pointer
propdata	propagator data

Definition at line 518 of file prop_symmetry.c.

References displayCycleOfSymmetry(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPinfoMessage(), and SYM_SYMTYPE_PERM.

Referenced by SCIP_DECL_DIALOGEXEC().

SCIP_DECL_DIALOGEXEC()

static SCIP_DECL_DIALOGEXEC ( dialogExecDisplaySymmetry  )

static

dialog execution method for the display symmetry information command

Definition at line 580 of file prop_symmetry.c.

References displaySymmetriesWithComponents(), displaySymmetriesWithoutComponents(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdialogGetData(), SCIPdialoghdlrAddHistory(), SCIPdialoghdlrGetRoot(), and SCIPinfoMessage().

SCIP_DECL_TABLEOUTPUT()

static SCIP_DECL_TABLEOUTPUT ( tableOutputSymmetry  )

static

output method of symmetry propagator statistics table to output file stream 'file'

Definition at line 627 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPgetShadowTreeEventHandlerExecutionTime(), SCIPlexicographicReductionGetStatistics(), SCIPorbitalReductionGetStatistics(), SCIPorbitopalReductionGetStatistics(), SCIPtableGetData(), and SCIPverbMessage().

SCIP_DECL_TABLEFREE()

static SCIP_DECL_TABLEFREE ( tableFreeSymmetry  )

static

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

Definition at line 676 of file prop_symmetry.c.

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

SCIP_DECL_SORTINDCOMP() [1/2]

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

References SYM_Sortgraphcompvars::colors, and SYM_Sortgraphcompvars::components.

compareSymgraphs()

static int compareSymgraphs ( SCIP *  scip, SYM_GRAPH *  G1, SYM_GRAPH *  G2  )

static

compares two symmetry detection graphs

Graphs are compared by their number of consnodes, then their constypes, then by their lhs, then by their rhs, then by their total number of nodes, then by the number of operator nodes, then by their number of value nodes, and then by their number of edges.

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

‍0: ind2 comes after (is worse than) ind2

Parameters

scip	SCIP pointer (or NULL)
G1	first graph in comparison
G2	second graph in comparison

Definition at line 742 of file prop_symmetry.c.

References SYM_Graph::consnodeperm, SYM_Graph::conss, SYM_Graph::lhs, SYM_Graph::nconsnodes, SYM_Graph::nedges, SYM_Graph::nnodes, SYM_Graph::nopnodes, NULL, SYM_Graph::nvalnodes, SYM_Graph::rhs, SCIPconsGetHdlr(), SCIPisGT(), and SCIPisLT().

Referenced by checkSymmetriesAreSymmetries(), and SCIP_DECL_SORTINDCOMP().

SCIP_DECL_SORTINDCOMP() [2/2]

static SCIP_DECL_SORTINDCOMP ( SYMsortSymgraphs  )

static

sorts symmetry detection graphs

Graphs are sorted by their number of consnodes, then their constypes, then by their lhs, then by their rhs, then by their total number of nodes, then by the number of operator nodes, then by their number of value nodes, and then by their number of edges.

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

References compareSymgraphs(), and NULL.

checkSymmetryDataFree()

static SCIP_Bool checkSymmetryDataFree ( SCIP_PROPDATA *  propdata )

static

checks that symmetry data is all freed

Parameters

propdata

propagator data

Definition at line 852 of file prop_symmetry.c.

References FALSE, NULL, and TRUE.

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

resetDynamicSymmetryHandling()

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

static

resets symmetry handling propagators that depend on the branch-and-bound tree structure

Parameters

scip	SCIP pointer
propdata	propagator data

Definition at line 897 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPlexicographicReductionReset(), SCIPorbitalReductionReset(), and SCIPorbitopalReductionReset().

Referenced by freeSymmetryData(), and SCIP_DECL_PROPEXITSOL().

freeSymmetryData()

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

static

frees symmetry data

Parameters

scip	SCIP pointer
propdata	propagator data

Definition at line 925 of file prop_symmetry.c.

References checkSymmetryDataFree(), FALSE, NULL, resetDynamicSymmetryHandling(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPhashmapFree(), SCIPreleaseCons(), SCIPreleaseVar(), and SYM_SYMTYPE_SIGNPERM.

Referenced by SCIP_DECL_PROPEXIT().

ensureDynamicConsArrayAllocatedAndSufficientlyLarge()

static SCIP_RETCODE ensureDynamicConsArrayAllocatedAndSufficientlyLarge ( SCIP *  scip, SCIP_CONS ***  consarrptr, int *  consarrsizeptr, int  consarrsizereq  )

static

makes sure that the constraint array (potentially NULL) of given array size is sufficiently large

Parameters

scip	SCIP pointer
consarrptr	constraint array pointer
consarrsizeptr	constraint array size pointer
consarrsizereq	constraint array size required

Definition at line 1097 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by addOrbitopesDynamic(), addOrbitopeSubgroup(), addStrongSBCsSubgroup(), addSymresackConss(), addWeakSBCsSubgroup(), componentPackingPartitioningOrbisackUpgrade(), detectAndHandleSubgroups(), handleDoublelLexMatrix(), and handleOrbitope().

setSymmetryData()

static SCIP_RETCODE setSymmetryData ( SCIP *  scip, SYM_SYMTYPE  symtype, SCIP_VAR **  vars, int  nvars, int  nbinvars, SCIP_VAR ***  permvars, int *  npermvars, int *  nbinpermvars, SCIP_Real **  permvardomaincenter, 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
symtype	type of symmetries in perms
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
permvardomaincenter	pointer to store center points of variable domains
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 1138 of file prop_symmetry.c.

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

Referenced by computeSymmetryGroup().

conshdlrCanProvideSymInformation()

static SCIP_Bool conshdlrCanProvideSymInformation ( SCIP_CONSHDLR *  conshdlr, SYM_SYMTYPE  symtype  )

static

returns whether a constraint handler can provide required symmetry information

Parameters

conshdlr	constraint handler
symtype	type of symmetries for which information are needed

Definition at line 1301 of file prop_symmetry.c.

References NULL, SCIPconshdlrSupportsPermsymDetection(), SCIPconshdlrSupportsSignedPermsymDetection(), SYM_SYMTYPE_PERM, and SYM_SYMTYPE_SIGNPERM.

Referenced by conshdlrsCanProvideSymInformation().

conshdlrsCanProvideSymInformation()

static SCIP_Bool conshdlrsCanProvideSymInformation ( SCIP *  scip, SYM_SYMTYPE  symtype  )

static

returns whether all constraint handlers with constraints can provide symmetry information

Parameters

scip	SCIP pointer
symtype	type of symmetries for which information are needed

Definition at line 1320 of file prop_symmetry.c.

References conshdlrCanProvideSymInformation(), FALSE, NULL, SCIP_Bool, SCIP_MAXSTRLEN, SCIP_VERBLEVEL_HIGH, SCIPconshdlrGetName(), SCIPconshdlrGetNConss(), SCIPexprhdlrGetName(), SCIPexprhdlrHasGetSymData(), SCIPfindConshdlr(), SCIPgetConshdlrs(), SCIPgetExprhdlrs(), SCIPgetNConshdlrs(), SCIPgetNExprhdlrs(), SCIPsnprintf(), SCIPverbMessage(), SCIPwarningMessage(), SYM_SYMTYPE_PERM, and TRUE.

Referenced by computeSymmetryGroup().

estimateSymgraphSize()

static SCIP_RETCODE estimateSymgraphSize ( SCIP *  scip, int *  nopnodes, int *  nvalnodes, int *  nconsnodes, int *  nedges  )

static

provides estimates for the number of nodes and edges in a symmetry detection graph

Parameters

scip	SCIP pointer
nopnodes	pointer to store estimate for number of operator nodes
nvalnodes	pointer to store estimate for number of value nodes
nconsnodes	pointer to store estimate for number of constraint nodes
nedges	pointer to store estimate for number of edges

Definition at line 1403 of file prop_symmetry.c.

References MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPgetConsNVars(), SCIPgetConss(), SCIPgetNConss(), and SCIPgetNVars().

Referenced by computeSymmetryGroup().

checkSymmetriesAreSymmetries()

static SCIP_RETCODE checkSymmetriesAreSymmetries ( SCIP *  scip, SYM_SYMTYPE  symtype, int **  perms, int  nperms, int  npermvars, SYM_SPEC  fixedtype  )

static

checks whether computed symmetries are indeed symmetries

Parameters

scip	SCIP pointer
symtype	type of symmetries to be checked
perms	array of permutations
nperms	number of permutations
npermvars	number of variables permutations act on
fixedtype	variable types that must be fixed by symmetries

Definition at line 1505 of file prop_symmetry.c.

References compareSymgraphs(), displayCycleOfSymmetry(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcomputeSymgraphColors(), SCIPcopySymgraph(), SCIPcreateSymgraph(), SCIPcreateSymgraphConsnodeperm(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPfreeSymgraph(), SCIPfreeSymgraphConsnodeperm(), SCIPgetConsPermsymGraph(), SCIPgetConss(), SCIPgetConsSignedPermsymGraph(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetVars(), SCIPinfoMessage(), SCIPprintCons(), SCIPsort(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, SYMcheckGraphsAreIdentical(), and TRUE.

Referenced by computeSymmetryGroup().

computeSymmetryGroup()

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

static

computes symmetry group of a CIP

Parameters

scip	SCIP pointer
symtype	type of symmetries to be computed
compresssymmetries	Should non-affected variables be removed from permutation to save memory?
compressthreshold	if percentage of moved vars is at most threshold, compression is done
maxgenerators	maximal number of generators constructed (= 0 if unlimited)
fixedtype	variable types that must be fixed by symmetries
checksymmetries	Should all symmetries be checked after computation?
permvars	pointer to permvars array
npermvars	pointer to store number of permvars
nbinpermvars	pointer to store number of binary permvars
permvardomaincenter	pointer to store center points of variable domains
perms	pointer to store permutation matrix (nperms x nvars)
nperms	pointer to store number of permutations
nmaxperms	pointer to store maximal number of permutations (needed for freeing storage)
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
compressed	pointer to store whether compression has been performed
log10groupsize	pointer to store log10 of size of group
symcodetime	pointer to store the time for symmetry code
success	pointer to store whether symmetry computation was successful

Definition at line 1684 of file prop_symmetry.c.

References checkSymmetriesAreSymmetries(), conshdlrsCanProvideSymInformation(), estimateSymgraphSize(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcomputeSymgraphColors(), SCIPcreateSymgraph(), SCIPduplicateBlockMemoryArray, SCIPfreeSymgraph(), SCIPgetConsPermsymGraph(), SCIPgetConss(), SCIPgetConsSignedPermsymGraph(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetSymgraphNVarcolors(), SCIPgetVars(), setSymmetryData(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, SYMcomputeSymmetryGenerators(), and TRUE.

Referenced by determineSymmetry().

isNonstandardPerm()

static SCIP_Bool isNonstandardPerm ( SCIP *  scip, int *  symmetry, SCIP_VAR **  vars, int  nvars  )

static

returns whether a symmetry is a non-standard permutation

Parameters

scip	SCIP instance
symmetry	a symmetry encoded as a signed permutation
vars	array of variables the symmetry acts on
nvars	number of variables in vars

Definition at line 1835 of file prop_symmetry.c.

References FALSE, NULL, SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by checkComponentsForNonstandardPerms().

checkComponentsForNonstandardPerms()

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

static

checks whether component contains non-standard permutations

If all symmetries are standard permutations, stores them as such.

Parameters

scip	SCIP instance
propdata	propagator data

Definition at line 1872 of file prop_symmetry.c.

References SYM_Sortgraphcompvars::components, isNonstandardPerm(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocClearBlockMemoryArray, SYM_SYMTYPE_PERM, and TRUE.

Referenced by ensureSymmetryComponentsComputed().

ensureSymmetryComponentsComputed()

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

static

ensures that the symmetry components are already computed

Parameters

scip	SCIP instance
propdata	propagator data

Definition at line 1917 of file prop_symmetry.c.

References checkComponentsForNonstandardPerms(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPcomputeComponentsSym(), SCIPgetSolvingTime(), and SCIPverbMessage().

Referenced by SCIPgetSymmetry(), and tryAddSymmetryHandlingMethods().

ensureSymmetryPermvarmapComputed()

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

static

ensures that permvarmap is initialized

Parameters

scip	SCIP instance
propdata	propagator data

Definition at line 1964 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashmapCreate(), and SCIPhashmapInsertInt().

Referenced by addSSTConss(), componentPackingPartitioningOrbisackUpgrade(), and SCIPgetSymmetry().

ensureSymmetryPermstransComputed()

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

static

ensures that permstrans is initialized

Parameters

scip	SCIP instance
propdata	propagator data

Definition at line 1996 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemoryArray.

Referenced by addSSTConss(), addWeakSBCsSubgroup(), and SCIPgetSymmetry().

ensureSymmetryMovedpermvarscountsComputed()

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

static

ensures that movedpermvarscounts is initialized

Parameters

scip	SCIP instance
propdata	propagator data

Definition at line 2030 of file prop_symmetry.c.

References NULL, SCIP_ERROR, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPerrorMessage, and SCIPvarGetType().

Referenced by addSSTConss(), and tryAddOrbitalRedLexRed().

testSymmetryComputationRequired()

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

static

returns whether any allowed symmetry handling method is effective for the problem instance

Parameters

scip	SCIP instance
propdata	propagator data

Definition at line 2091 of file prop_symmetry.c.

References FALSE, ISORBITALREDUCTIONACTIVE, ISSSTACTIVE, ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, ISSYMRETOPESACTIVE, SCIPconshdlrGetNActiveConss(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), and TRUE.

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

References checkSymmetryDataFree(), computeSymmetryGroup(), MAXGENNUMERATOR, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_HIGH, SCIPcaptureVar(), SCIPdetermineNVarsAffectedSym(), SCIPgetNActiveBenders(), SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNRuns(), SCIPgetNVars(), SCIPgetSolvingTime(), SCIPisReoptEnabled(), SCIPverbMessage(), SCIPwarningMessage(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, SYMcanComputeSymmetry(), testSymmetryComputationRequired(), and TRUE.

Referenced by tryAddSymmetryHandlingMethods().

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 generated 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 symmetry 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 number 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 2330 of file prop_symmetry.c.

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

Referenced by addOrbitopeSubgroup().

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

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

Referenced by 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 2593 of file prop_symmetry.c.

References 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 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 orbitope could be added

Definition at line 2860 of file prop_symmetry.c.

References checkTwoCyclePermsAreOrbitope(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), 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 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 3081 of file prop_symmetry.c.

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

Referenced by 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 3165 of file prop_symmetry.c.

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

Referenced by 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 3407 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

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

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

Referenced by detectAndHandleSubgroups().

detectAndHandleSubgroups()

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

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
cidx	index of component which shall be handled

Definition at line 3572 of file prop_symmetry.c.

References adaptSymmetryDataSST(), addOrbitopeSubgroup(), addStrongSBCsSubgroup(), addWeakSBCsSubgroup(), buildSubgroupGraph(), chooseOrderOfGenerators(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), 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(), SCIPvarGetName(), SCIPvarIsBinary(), SCIPvarIsIntegral(), SCIPverbMessage(), SYM_HANDLETYPE_SYMBREAK, and TRUE.

Referenced by tryHandleSubgroups().

updateSymInfoConflictGraphSST()

static SCIP_RETCODE updateSymInfoConflictGraphSST ( SCIP *  scip, SCIP_CONFLICTDATA *  varconflicts, SCIP_VAR **  conflictvars, int  nconflictvars, int *  orbits, int *  orbitbegins, int  norbits  )

static

update symmetry information of conflict graph

Parameters

scip	SCIP instance
varconflicts	conflict structure
conflictvars	variables encoded in conflict structure
nconflictvars	number of nodes/vars in conflict structure
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 4100 of file prop_symmetry.c.

References active, checkSortedArraysHaveOverlappingEntry(), NULL, r, and SCIP_OKAY.

Referenced by addSSTConss().

createConflictGraphSST()

static SCIP_RETCODE createConflictGraphSST ( SCIP *  scip, SCIP_CONFLICTDATA **  varconflicts, SCIP_VAR **  conflictvars, int  nconflictvars, SCIP_HASHMAP *  conflictvarmap  )

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().

The function returns with varconflicts as NULL when we do not create it.

Parameters

scip	SCIP instance
varconflicts	pointer to store the variable conflict data
conflictvars	array of variables to encode in conflict graph
nconflictvars	number of vars to encode in conflict graph
conflictvarmap	map of variables to indices in conflictvars array

Definition at line 4213 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocClearBufferArray, SCIPcliqueGetId(), SCIPcliqueGetIndex(), SCIPcliqueGetNVars(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCliques(), SCIPgetNCliques(), SCIPhashmapGetImageInt(), SCIPsortPtr(), and TRUE.

Referenced by addSSTConss().

freeConflictGraphSST()

static SCIP_RETCODE freeConflictGraphSST ( SCIP *  scip, SCIP_CONFLICTDATA **  varconflicts, int  nvars  )

static

frees conflict graph

Parameters

scip	SCIP instance
varconflicts	conflict graph
nvars	number of nodes in conflict graph

Definition at line 4381 of file prop_symmetry.c.

References NULL, SCIP_OKAY, and SCIPfreeBlockMemoryArray.

Referenced by addSSTConss().

addSymresackConss()

static SCIP_RETCODE addSymresackConss ( SCIP *  scip, SCIP_PROPDATA *  propdata, int  cidx  )

static

adds symresack constraints

Parameters

scip	SCIP instance
propdata	data of symmetry propagator
cidx	index of component to be handled

Definition at line 4408 of file prop_symmetry.c.

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

Referenced by tryAddSymmetryHandlingMethodsComponent().

addSSTConssOrbitAndUpdateSST()

static SCIP_RETCODE addSSTConssOrbitAndUpdateSST ( SCIP *  scip, SCIP_CONFLICTDATA *  varconflicts, SCIP_PROPDATA *  propdata, SCIP_VAR **  permvars, int *  orbits, int *  orbitbegins, int  orbitidx, int  orbitleaderidx, SCIP_Shortbool *  orbitvarinconflict, int  norbitvarinconflict, int *  nchgbds  )

static

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

Parameters

scip	SCIP instance
varconflicts	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)

Definition at line 4545 of file prop_symmetry.c.

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

Referenced by addSSTConss().

selectOrbitLeaderSSTConss()

static SCIP_RETCODE selectOrbitLeaderSSTConss ( SCIP *  scip, SCIP_CONFLICTDATA *  varconflicts, SCIP_VAR **  conflictvars, int  nconflictvars, int *  orbits, int *  orbitbegins, int  norbits, int  leaderrule, int  tiebreakrule, SCIP_VARTYPE  leadervartype, int *  orbitidx, int *  leaderidx, SCIP_Shortbool *  orbitvarinconflict, int *  norbitvarinconflict, SCIP_Bool *  success  )

static

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

Parameters

scip	SCIP instance
varconflicts	variable conflicts structure, or NULL if we do not use it
conflictvars	variables encoded in conflict graph
nconflictvars	number of variables encoded in conflict graph
orbits	orbits of stabilizer subgroup, expressed in terms of conflictvars
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
success	pointer to store whether orbit cut be selected successfully

Definition at line 4697 of file prop_symmetry.c.

References active, checkSortedArraysHaveOverlappingEntry(), FALSE, NULL, SCIP_LEADERRULE_FIRSTINORBIT, SCIP_LEADERRULE_LASTINORBIT, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXORBIT, SCIP_LEADERTIEBREAKRULE_MINORBIT, SCIP_OKAY, SCIPvarGetProbindex(), SCIPvarGetType(), and TRUE.

Referenced by addSSTConss().

addSSTConss()

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

static

add Schreier Sims constraints to the problem

Parameters

scip	SCIP instance
propdata	data of symmetry propagator
onlywithcontvars	only handle components that contain continuous variables with SST
nchgbds	pointer to store number of bound changes (or NULL)
cidx	index of component which shall be handled

Definition at line 4940 of file prop_symmetry.c.

References addSSTConssOrbitAndUpdateSST(), SYM_Sortgraphcompvars::components, createConflictGraphSST(), ensureSymmetryMovedpermvarscountsComputed(), ensureSymmetryPermstransComputed(), ensureSymmetryPermvarmapComputed(), FALSE, freeConflictGraphSST(), ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LEADERRULE_FIRSTINORBIT, 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, SCIPcomputeOrbitsFilterSym(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPvarGetType(), selectOrbitLeaderSSTConss(), SYM_HANDLETYPE_SST, TRUE, and updateSymInfoConflictGraphSST().

Referenced by tryAddSymmetryHandlingMethodsComponent().

addOrbitopesDynamic()

static SCIP_RETCODE addOrbitopesDynamic ( SCIP *  scip, SCIP_PROPDATA *  propdata, int  id, int **  varidxmatrix, int  nrows, int  ncols, SCIP_Bool *  success  )

static

orbitopal reduction

Parameters

scip	SCIP instance
propdata	propdata
id	ID for orbitope constraint (needed for name)
varidxmatrix	matrix containing variable indices in orbitope matrix
nrows	number of rows of orbitope
ncols	number of columns of orbitope
success	pointer to store whether orbitope could be added successfully

Definition at line 5240 of file prop_symmetry.c.

References ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_PACKING, SCIP_Real, SCIP_ROWORDERING_BRANCHING, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPcreateConsOrbitope(), SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPinfinity(), SCIPisPackingPartitioningOrbitope(), SCIPlexicographicReductionAddPermutation(), SCIPorbitopalReductionAddOrbitope(), SCIPorbitopalReductionGetDefaultColumnOrdering(), SCIPsnprintf(), and TRUE.

Referenced by handleOrbitope().

componentPackingPartitioningOrbisackUpgrade()

static SCIP_RETCODE componentPackingPartitioningOrbisackUpgrade ( SCIP *  scip, SCIP_PROPDATA *  propdata, int **  componentperms, int  componentsize, SCIP_Bool  hassignedperm, SCIP_Bool *  success  )

static

applies pp-orbitope upgrade if at least 50% of the permutations in a component correspond to pp-orbisacks

Parameters

scip	SCIP instance
propdata	propdata
componentperms	permutations in the component
componentsize	number of permutations in the component
hassignedperm	whether the component has a signed permutation
success	whether the packing partitioning upgrade succeeded

Definition at line 5412 of file prop_symmetry.c.

References checkSortedArraysHaveOverlappingEntry(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), ensureSymmetryPermvarmapComputed(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_PACKING, SCIP_SETPPCTYPE_COVERING, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateConsOrbitope(), SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPhashmapGetImageInt(), SCIPsnprintf(), SCIPsortPtr(), SCIPvarGetType(), and TRUE.

Referenced by tryAddOrbitalRedLexRed().

tryAddOrbitalRedLexRed()

static SCIP_RETCODE tryAddOrbitalRedLexRed ( SCIP *  scip, SCIP_PROPDATA *  propdata, int  cidx  )

static

dynamic permutation lexicographic reduction

Parameters

scip	SCIP instance
propdata	propdata
cidx	index of component

Definition at line 5664 of file prop_symmetry.c.

References componentPackingPartitioningOrbisackUpgrade(), ensureSymmetryMovedpermvarscountsComputed(), ISORBITALREDUCTIONACTIVE, ISSYMRETOPESACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetParam(), SCIPlexicographicReductionAddPermutation(), SCIPorbitalReductionAddComponent(), SCIPparamGetBool(), SYM_HANDLETYPE_ORBITALREDUCTION, SYM_HANDLETYPE_SYMBREAK, and TRUE.

Referenced by tryAddSymmetryHandlingMethodsComponent().

SCIPdisplaySymmetryStatistics()

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

static

displays statistics on the used symmetry handling methods

Parameters

scip	SCIP instance
propdata	data of symmetry propagator

Definition at line 5766 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPlexicographicReductionPrintStatistics(), SCIPorbitalReductionPrintStatistics(), SCIPorbitopalReductionPrintStatistics(), and SCIPverbMessage().

Referenced by tryAddSymmetryHandlingMethods().

handleOrbitope()

static SCIP_RETCODE handleOrbitope ( SCIP *  scip, SCIP_PROPDATA *  propdata, int  id, int **  varidxmatrix, int  nrows, int  ncols, SCIP_Bool *  success  )

static

handles orbitope action by static or dynamic symmetry handling methods

Parameters

scip	SCIP instance
propdata	data of symmetry propagator
id	ID of orbitope (used for constraint name)
varidxmatrix	matrix containing variable indices of orbitope
nrows	number of rows of matrix
ncols	number of columns of matrix
success	pointer to store whether orbitope could be added successfully

Definition at line 5814 of file prop_symmetry.c.

References addOrbitopesDynamic(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsOrbitope(), SCIPfreeBufferArray, SCIPsnprintf(), SCIPvarIsBinary(), and TRUE.

Referenced by tryHandleSingleOrDoubleLexMatricesComponent().

handleDoublelLexMatrix()

static SCIP_RETCODE handleDoublelLexMatrix ( SCIP *  scip, SCIP_PROPDATA *  propdata, int  id, int **  varidxmatrix, int  nrows, int  ncols, int *  rowsbegin, int *  colsbegin, int  nrowblocks, int  ncolblocks, SCIP_Bool *  success  )

static

handles binary double lex matrix by adding static orbitope constraints

Parameters

scip	SCIP instance
propdata	data of symmetry propagator
id	ID of double lex matrix (used for constraint names)
varidxmatrix	matrix containing variable indices of double lex matrix
nrows	number of rows of matrix
ncols	number of columns of matrix
rowsbegin	array indicating where a new row block begins
colsbegin	array indicating where a new column block begins
nrowblocks	number of row blocks
ncolblocks	number of column blocks
success	pointer to store whether orbitope could be added successfully

Definition at line 5898 of file prop_symmetry.c.

References ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, MAX, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsOrbitope(), SCIPfreeBufferArray, SCIPsnprintf(), SCIPvarIsBinary(), and TRUE.

Referenced by tryHandleSingleOrDoubleLexMatricesComponent().

tryHandleSingleOrDoubleLexMatricesComponent()

static SCIP_RETCODE tryHandleSingleOrDoubleLexMatricesComponent ( SCIP *  scip, SCIP_PROPDATA *  propdata, SCIP_Bool  detectsinglelex, int  cidx  )

static

tries to handle symmetries of single lex matrices (orbitopes) or double lex matrices

Parameters

scip	SCIP instance
propdata	data of symmetry propagator
detectsinglelex	whether single lex matrices shall be detected
cidx	index of component

Definition at line 6015 of file prop_symmetry.c.

References FALSE, handleDoublelLexMatrix(), handleOrbitope(), ISSYMRETOPESACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdetectSingleOrDoubleLexMatrices(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPvarIsBinary(), SYM_HANDLETYPE_SYMBREAK, and TRUE.

Referenced by tryAddSymmetryHandlingMethodsComponent().

tryHandleSubgroups()

static SCIP_RETCODE tryHandleSubgroups ( SCIP *  scip, SCIP_PROPDATA *  propdata, int  cidx  )

static

tries to handle subgroups of component

Parameters

scip	SCIP instance
propdata	data of symmetry propagator
cidx	index of component

Definition at line 6128 of file prop_symmetry.c.

References detectAndHandleSubgroups(), ISSYMRETOPESACTIVE, NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by tryAddSymmetryHandlingMethodsComponent().

tryAddSymmetryHandlingMethodsComponent()

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

static

tries to add symmetry handling methods to component of symmetry group

For a component, we handle the symmetries as follows:

1. If orbitope detection is enabled and the component is an orbitope: Apply one of the following: 1.1. If dynamic symmetry handling methods are used: 1.1.1. If the orbitope has a single row, add linear constraints x_1 >= x_2 ... >= x_n. 1.1.2. If it has only two columns only, use lexicographic reduction; cf. symmetry_lexred.c 1.1.3. If there are at least 3 binary rows with packing-partitioning constraints, use a static packing-partitioning orbitopal fixing; cf. cons_orbitope.c

Parameters

scip	SCIP instance
propdata	data of symmetry propagator
cidx	index of component
nchgbds	pointer to store number of bound changes (or NULL)

Definition at line 6181 of file prop_symmetry.c.

References addSSTConss(), addSymresackConss(), FALSE, ISORBITALREDUCTIONACTIVE, ISSSTACTIVE, ISSYMRETOPESACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, TRUE, tryAddOrbitalRedLexRed(), tryHandleSingleOrDoubleLexMatricesComponent(), and tryHandleSubgroups().

Referenced by tryAddSymmetryHandlingMethods().

tryAddSymmetryHandlingMethods()

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

static

determines problem symmetries and activates symmetry handling methods

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

References checkSymmetryDataFree(), determineSymmetry(), ensureSymmetryComponentsComputed(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallowStrongDualReds(), SCIPallowWeakDualReds(), SCIPdisplaySymmetryStatistics(), SCIPisStopped(), SCIPpropGetData(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, TRUE, and tryAddSymmetryHandlingMethodsComponent().

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

propagateSymmetry()

static SCIP_RETCODE propagateSymmetry ( SCIP *  scip, SCIP_PROPDATA *  propdata, SCIP_Bool *  infeasible, int *  nred, SCIP_Bool *  didrun  )

static

apply propagation methods for various symmetry handling constraints

Parameters

scip	SCIP pointer
propdata	propagator data
infeasible	pointer for storing feasibility state
nred	pointer for number of reductions
didrun	pointer for storing whether a propagator actually ran

Definition at line 6322 of file prop_symmetry.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPlexicographicReductionPropagate(), SCIPorbitalReductionPropagate(), and SCIPorbitopalReductionPropagate().

Referenced by SCIP_DECL_PROPEXEC().

SCIP_DECL_PROPINITPRE()

static SCIP_DECL_PROPINITPRE ( propInitpreSymmetry  )

static

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

Definition at line 6370 of file prop_symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPfindConshdlr(), SCIPgetIntParam(), SCIPpropGetData(), SCIPverbMessage(), SYM_TIMING_BEFOREPRESOL, and tryAddSymmetryHandlingMethods().

SCIP_DECL_PROPEXITPRE()

static SCIP_DECL_PROPEXITPRE ( propExitpreSymmetry  )

static

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

Definition at line 6408 of file prop_symmetry.c.

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

SCIP_DECL_PROPEXITSOL()

static SCIP_DECL_PROPEXITSOL ( propExitsolSymmetry  )

static

solving process deinitialization method of propagator (called before branch and bound process data is freed)

Definition at line 6439 of file prop_symmetry.c.

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

SCIP_DECL_PROPPRESOL()

static SCIP_DECL_PROPPRESOL ( propPresolSymmetry  )

static

presolving method of propagator

Definition at line 6461 of file prop_symmetry.c.

References NULL, 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_TIMING_AFTERPRESOL, SYM_TIMING_DURINGPRESOL, and tryAddSymmetryHandlingMethods().

SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecSymmetry  )

static

execution method of propagator

Definition at line 6577 of file prop_symmetry.c.

References NULL, propagateSymmetry(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPgetDepth(), SCIPgetStage(), SCIPpropGetData(), and TRUE.

SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitSymmetry  )

static

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

Definition at line 6624 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 6660 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 6672 of file prop_symmetry.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPhashmapFree(), SCIPlexicographicReductionFree(), SCIPorbitalReductionFree(), SCIPorbitopalReductionFree(), SCIPpropGetData(), and SCIPpropGetName().

SCIPincludePropSymmetry()

SCIP_RETCODE SCIPincludePropSymmetry

(

SCIP *

scip

)

include symmetry propagator

Parameters

scip	SCIP data structure

Definition at line 6708 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_DETECTDOUBLELEX, DEFAULT_DETECTORBITOPES, DEFAULT_DETECTSUBGROUPS, DEFAULT_DISPLAYNORBITVARS, DEFAULT_DOUBLEEQUATIONS, DEFAULT_ENFORCECOMPUTESYMMETRY, DEFAULT_MAXGENERATORS, DEFAULT_MAXNCONSSSUBGROUP, DEFAULT_NAUTYMAXNCELLS, DEFAULT_NAUTYMAXNNODES, DEFAULT_PERFORMPRESOLVING, DEFAULT_PREFERLESSROWS, DEFAULT_RECOMPUTERESTART, DEFAULT_SSTADDCUTS, DEFAULT_SSTLEADERRULE, DEFAULT_SSTLEADERVARTYPE, DEFAULT_SSTMIXEDCOMPONENTS, DEFAULT_SSTTIEBREAKRULE, DEFAULT_SYMCOMPTIMING, DEFAULT_SYMFIXNONBINARYVARS, DEFAULT_SYMTYPE, DEFAULT_USECOLUMNSPARSITY, DEFAULT_USEDYNAMICPROP, 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, SCIP_PLUGINNOTFOUND, SCIPaddBoolParam(), SCIPaddDialogEntry(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPblkmem(), SCIPdialogFindEntry(), SCIPdialogHasEntry(), SCIPerrorMessage, SCIPgetRootDialog(), SCIPhashmapCreate(), SCIPincludeDialog(), SCIPincludeEventHdlrShadowTree(), SCIPincludeExternalCodeInformation(), SCIPincludeLexicographicReduction(), SCIPincludeOrbitalReduction(), SCIPincludeOrbitopalReduction(), SCIPincludePropBasic(), SCIPincludeTable(), SCIPreleaseDialog(), SCIPsetPropExit(), SCIPsetPropExitpre(), SCIPsetPropExitsol(), SCIPsetPropFree(), SCIPsetPropInitpre(), SCIPsetPropPresol(), SCIPsetPropResprop(), SYM_CONSOPTYPE_LAST, SYMcanComputeSymmetry(), SYMsymmetryGetAddDesc(), SYMsymmetryGetAddName(), SYMsymmetryGetDesc(), SYMsymmetryGetName(), TABLE_DESC_SYMMETRY, TABLE_EARLIEST_SYMMETRY, TABLE_NAME_SYMMETRY, TABLE_POSITION_SYMMETRY, 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 (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 7014 of file prop_symmetry.c.

References SYM_Sortgraphcompvars::components, ensureSymmetryComponentsComputed(), ensureSymmetryPermstransComputed(), ensureSymmetryPermvarmapComputed(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPerrorMessage, SCIPfindProp(), SCIPpropGetData(), and SCIPpropGetName().

Referenced by initOrbits().

SCIPgetSymmetryNGenerators()

int SCIPgetSymmetryNGenerators

(

SCIP *

scip

)

return number of the symmetry group's generators

Parameters

scip	SCIP data structure

Definition at line 7113 of file prop_symmetry.c.

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

SCIPcreateSymOpNodeType()

SCIP_RETCODE SCIPcreateSymOpNodeType	(	SCIP *	scip,
		const char *	opnodename,
		int *	nodetype
	)

creates new operator node type (used for symmetry detection) and returns its representation

If the operator node already exists, the function terminates with SCIP_INVALIDDATA.

Parameters

scip	SCIP pointer
opnodename	name of new operator node type
nodetype	pointer to store the node type

Definition at line 7139 of file prop_symmetry.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPerrorMessage, SCIPfindProp(), SCIPhashmapExists(), SCIPhashmapInsertInt(), and SCIPpropGetData().

Referenced by SCIPgetSymOpNodeType().

SCIPgetSymOpNodeType()

SCIP_RETCODE SCIPgetSymOpNodeType	(	SCIP *	scip,
		const char *	opnodename,
		int *	nodetype
	)

returns representation of an operator node type.

If the node type does not already exist, a new node type will be created.

Parameters

scip	SCIP pointer
opnodename	name of new operator node type
nodetype	pointer to store the node type

Definition at line 7178 of file prop_symmetry.c.

References NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPcreateSymOpNodeType(), SCIPerrorMessage, SCIPfindProp(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), and SCIPpropGetData().

Referenced by addSymmetryInformation(), tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperatorSum(), and tryAddGadgetEvenOperatorVariable().