Scippy

SCIP

Solving Constraint Integer Programs

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

◆ ISSYMRETOPESACTIVE

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

Definition at line 204 of file prop_symmetry.c.

◆ ISORBITALREDUCTIONACTIVE

#define ISORBITALREDUCTIONACTIVE (   x)    (((unsigned) x & SYM_HANDLETYPE_ORBITALREDUCTION) != 0)

Definition at line 205 of file prop_symmetry.c.

◆ ISSSTACTIVE

#define ISSSTACTIVE (   x)    (((unsigned) x & SYM_HANDLETYPE_SST) != 0)

Definition at line 206 of file prop_symmetry.c.

◆ ISSSTBINACTIVE

#define ISSSTBINACTIVE (   x)    (((unsigned) x & SCIP_SSTTYPE_BINARY) != 0)

Definition at line 208 of file prop_symmetry.c.

◆ ISSSTINTACTIVE

#define ISSSTINTACTIVE (   x)    (((unsigned) x & SCIP_SSTTYPE_INTEGER) != 0)

Definition at line 209 of file prop_symmetry.c.

◆ ISSSTIMPLINTACTIVE

#define ISSSTIMPLINTACTIVE (   x)    (((unsigned) x & SCIP_SSTTYPE_IMPLINT) != 0)

Definition at line 210 of file prop_symmetry.c.

◆ ISSSTCONTACTIVE

#define ISSSTCONTACTIVE (   x)    (((unsigned) x & SCIP_SSTTYPE_CONTINUOUS) != 0)

Definition at line 211 of file prop_symmetry.c.

◆ SYMMETRY_STATISTICS

#define SYMMETRY_STATISTICS   1

Definition at line 214 of file prop_symmetry.c.

Typedef Documentation

◆ SCIP_CONFLICTDATA

typedef struct SCIP_ConflictData SCIP_CONFLICTDATA

Definition at line 332 of file prop_symmetry.c.

◆ SYM_SORTGRAPHCOMPVARS

Definition at line 694 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 337 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
arr1first array
narr1number of elements in first array
arr2second array
narr2number of elements in second array

Definition at line 350 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
scipSCIP pointer
permsymmetry
symtypetype of symmetry
baseidxvariable index for which cycle is computed
coveredallocated array to store covered variables
nvarsnumber of (non-negated) variables in symmetry
varsvariables on which symmetry acts

Definition at line 419 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
scipSCIP pointer
propdatapropagator data

Definition at line 464 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
scipSCIP pointer
propdatapropagator data

Definition at line 513 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 575 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

◆ 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 671 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 706 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
scipSCIP pointer (or NULL)
G1first graph in comparison
G2second graph in comparison

Definition at line 737 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 827 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
propdatapropagator data

Definition at line 847 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
scipSCIP pointer
propdatapropagator data

Definition at line 892 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

◆ 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
scipSCIP pointer
consarrptrconstraint array pointer
consarrsizeptrconstraint array size pointer
consarrsizereqconstraint array size required

Definition at line 1092 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
scipSCIP pointer
symtypetype of symmetries in perms
varsvars present at time of symmetry computation
nvarsnumber of vars present at time of symmetry computation
nbinvarsnumber of binary vars present at time of symmetry computation
permvarspointer to permvars array
npermvarspointer to store number of permvars
nbinpermvarspointer to store number of binary permvars
permvardomaincenterpointer to store center points of variable domains
permspermutations matrix (nperms x nvars)
npermsnumber of permutations
nmovedvarspointer to store number of vars affected by symmetry (if usecompression) or NULL
binvaraffectedpointer to store whether a binary variable is affected by symmetry
usecompressionwhether symmetry data shall be compressed
compressthresholdif percentage of moved vars is at most threshold, compression is done
compressedpointer to store whether compression has been performed

Definition at line 1133 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
conshdlrconstraint handler
symtypetype of symmetries for which information are needed

Definition at line 1296 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
scipSCIP pointer
symtypetype of symmetries for which information are needed

Definition at line 1315 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
scipSCIP pointer
nopnodespointer to store estimate for number of operator nodes
nvalnodespointer to store estimate for number of value nodes
nconsnodespointer to store estimate for number of constraint nodes
nedgespointer to store estimate for number of edges

Definition at line 1398 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
scipSCIP pointer
symtypetype of symmetries to be checked
permsarray of permutations
npermsnumber of permutations
npermvarsnumber of variables permutations act on
fixedtypevariable types that must be fixed by symmetries

Definition at line 1500 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
scipSCIP pointer
symtypetype of symmetries to be computed
compresssymmetriesShould non-affected variables be removed from permutation to save memory?
compressthresholdif percentage of moved vars is at most threshold, compression is done
maxgeneratorsmaximal number of generators constructed (= 0 if unlimited)
fixedtypevariable types that must be fixed by symmetries
checksymmetriesShould all symmetries be checked after computation?
permvarspointer to permvars array
npermvarspointer to store number of permvars
nbinpermvarspointer to store number of binary permvars
permvardomaincenterpointer to store center points of variable domains
permspointer to store permutation matrix (nperms x nvars)
npermspointer to store number of permutations
nmaxpermspointer to store maximal number of permutations (needed for freeing storage)
nmovedvarspointer to store number of vars affected by symmetry (if usecompression) or NULL
binvaraffectedpointer to store whether a binary variable is affected by symmetry
compressedpointer to store whether compression has been performed
log10groupsizepointer to store log10 of size of group
symcodetimepointer to store the time for symmetry code
successpointer to store whether symmetry computation was successful

Definition at line 1679 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
scipSCIP instance
symmetrya symmetry encoded as a signed permutation
varsarray of variables the symmetry acts on
nvarsnumber of variables in vars

Definition at line 1830 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
scipSCIP instance
propdatapropagator data

Definition at line 1867 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
scipSCIP instance
propdatapropagator data

Definition at line 1912 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
scipSCIP instance
propdatapropagator data

Definition at line 1959 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
scipSCIP instance
propdatapropagator data

Definition at line 1991 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
scipSCIP instance
propdatapropagator data

Definition at line 2025 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
scipSCIP instance
propdatapropagator data

Definition at line 2086 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

◆ 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
scipSCIP instance
permvarsarray of all permutation variables
npermvarsnumber of permutation variables
permsarray of all permutations of the symmetry group
activepermsindices of the relevant permutations in perms
ntwocyclesnumber of 2-cycles in the permutations
nactivepermsnumber of active permutations
orbitopevaridxpointer to store variable index matrix
columnorderpointer to store column order
nusedelemspointer to store how often each element was used
nusedcolspointer to store number of columns used in orbitope (or NULL)
rowisbinarypointer to store which rows are binary (or NULL)
isorbitopebuffer to store result
activevarsbitset to store whether a variable is active (or NULL)

Definition at line 2325 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
scipSCIP instance
propdatapointer to data of symmetry propagator
compidxindex of component
genorder(initialized) buffer to store the resulting order of generator
ntwocyclepermspointer to store the number of 2-cycle permutations in component compidx

Definition at line 2510 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
scipSCIP instance
propdatapointer to data of symmetry propagator
genorderorder in which the generators should be considered
ntwocyclepermsnumber of 2-cycle permutations in this component
compidxindex of the component
graphcomponentsbuffer to store the components of the graph (ordered var indices)
graphcompbeginsbuffer to store the indices of each new graph component
compcolorbeginsbuffer to store at which indices a new color begins
ngraphcomponentspointer to store the number of graph components
ncompcolorspointer to store the number of different colors
usedpermsbuffer to store the indices of permutations that were used
nusedpermspointer to store the number of used permutations in the graph
usedpermssizeinitial size of usedperms
permusedinitialized buffer to store which permutations have been used (identified by index in component)

Definition at line 2588 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
scipSCIP instance
propdatapointer to data of symmetry propagator
usedpermsarray of the permutations that build the orbitope
nusedpermsnumber of permutations in usedperms
compcolorbeginsarray indicating where a new graphcolor begins
graphcompbeginsarray indicating where a new graphcomponent begins
graphcomponentsarray of all variable indices sorted by color and comp
graphcoloridxindex of the graph color
nrowsnumber of rows in the orbitope
ncolsnumber of columns in the orbitope
firstvaridxbuffer to store the index of the largest variable (or NULL)
compidxfirstrowbuffer to store the comp index for the first row (or NULL)
lexorderpointer to array storing lexicographic order defined by sub orbitopes
nvarslexordernumber of variables in lexicographic order
maxnvarslexordermaximum number of variables in lexicographic order
mayinteractwhether orbitope's symmetries might interact with other symmetries
successwhether the orbitope could be added

Definition at line 2855 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
scipSCIP instance
propdatapointer to data of symmetry propagator
graphcompbeginsarray indicating where a new graphcomponent begins
graphcomponentsarray of all variable indices sorted by color and comp
graphcompidxindex of the graph component
storelexorderwhether the lexicographic order induced by the orbitope shall be stored
lexorderpointer to array storing lexicographic order defined by sub orbitopes
nvarsordernumber of variables in lexicographic order
maxnvarsordermaximum number of variables in lexicographic order

Definition at line 3076 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
scipSCIP instance
propdatapointer to data of symmetry propagator
compcolorbeginsarray indicating where a new graphcolor begins
graphcompbeginsarray indicating where a new graphcomponent begins
graphcomponentsarray of all variable indices sorted by color and comp
ncompcolorsnumber of colors in the graph
chosencomppercolorarray indicating which comp was handled per color
firstvaridxpercolorarray indicating the largest variable per color
symgrpcompidxindex of the component of the symmetry group
naddedconssbuffer to store the number of added constraints
storelexorderwhether the lexicographic order induced by the orbitope shall be stored
lexorderpointer to array storing lexicographic order defined by sub orbitopes
nvarsordernumber of variables in lexicographic order
maxnvarsordermaximum number of variables in lexicographic order

Definition at line 3160 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
scipSCIP instance
origpermspermutation matrix w.r.t. original variable ordering
modifiedpermsmemory for permutation matrix w.r.t. new variable ordering
npermsnumber of permutations
origpermvarsarray of permutation vars w.r.t. original variable ordering
modifiedpermvarsmemory for array of permutation vars w.r.t. new variable ordering
npermvarslength or modifiedpermvars array
leadersleaders of Schreier Sims constraints
nleadersnumber of leaders

Definition at line 3402 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
permvarsarray of variables affected by symmetry
graphcomponentsarray of graph components
graphcompbeginsarray indicating starting position of graph components
compcolorbeginsarray indicating starting positions of potential orbitopes
ncompcolorsnumber of components encoded in compcolorbegins
symcompsizesize of symmetry component for that we detect suborbitopes

Definition at line 3484 of file prop_symmetry.c.

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

Referenced by detectAndHandleSubgroups().

◆ detectAndHandleSubgroups()

◆ 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
scipSCIP instance
varconflictsconflict structure
conflictvarsvariables encoded in conflict structure
nconflictvarsnumber of nodes/vars in conflict structure
orbitsarray of non-trivial orbits
orbitbeginsarray containing begin positions of new orbits in orbits array
norbitsnumber of non-trivial orbits

Definition at line 4095 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
scipSCIP instance
varconflictspointer to store the variable conflict data
conflictvarsarray of variables to encode in conflict graph
nconflictvarsnumber of vars to encode in conflict graph
conflictvarmapmap of variables to indices in conflictvars array

Definition at line 4208 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
scipSCIP instance
varconflictsconflict graph
nvarsnumber of nodes in conflict graph

Definition at line 4376 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

◆ 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
scipSCIP instance
varconflictsconflict graph or NULL if useconflictgraph == FALSE
propdatadata of symmetry propagator
permvarspermvars array
orbitssymmetry orbits
orbitbeginsarray storing begin position for each orbit
orbitidxindex of orbit for Schreier Sims constraints
orbitleaderidxindex of leader variable for Schreier Sims constraints
orbitvarinconflictindicator whether orbitvar is in conflict with orbit leader
norbitvarinconflictnumber of variables in conflict with orbit leader
nchgbdspointer to store number of bound changes (or NULL)

Definition at line 4540 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
scipSCIP instance
varconflictsvariable conflicts structure, or NULL if we do not use it
conflictvarsvariables encoded in conflict graph
nconflictvarsnumber of variables encoded in conflict graph
orbitsorbits of stabilizer subgroup, expressed in terms of conflictvars
orbitbeginsarray storing the begin position of each orbit in orbits
norbitsnumber of orbits
leaderrulerule to select leader
tiebreakruletie break rule to select leader
leadervartypevariable type of leader
orbitidxpointer to index of selected orbit
leaderidxpointer to leader in orbit
orbitvarinconflictarray to store whether a var in the orbit is conflicting with leader
norbitvarinconflictpointer to store number of vars in the orbit in conflict with leader
successpointer to store whether orbit cut be selected successfully

Definition at line 4692 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()

◆ 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
scipSCIP instance
propdatapropdata
idID for orbitope constraint (needed for name)
varidxmatrixmatrix containing variable indices in orbitope matrix
nrowsnumber of rows of orbitope
ncolsnumber of columns of orbitope
successpointer to store whether orbitope could be added successfully

Definition at line 5235 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
scipSCIP instance
propdatapropdata
componentpermspermutations in the component
componentsizenumber of permutations in the component
hassignedpermwhether the component has a signed permutation
successwhether the packing partitioning upgrade succeeded

Definition at line 5407 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()

◆ SCIPdisplaySymmetryStatistics()

static SCIP_RETCODE SCIPdisplaySymmetryStatistics ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

displays statistics on the used symmetry handling methods

Parameters
scipSCIP instance
propdatadata of symmetry propagator

Definition at line 5761 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
scipSCIP instance
propdatadata of symmetry propagator
idID of orbitope (used for constraint name)
varidxmatrixmatrix containing variable indices of orbitope
nrowsnumber of rows of matrix
ncolsnumber of columns of matrix
successpointer to store whether orbitope could be added successfully

Definition at line 5809 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
scipSCIP instance
propdatadata of symmetry propagator
idID of double lex matrix (used for constraint names)
varidxmatrixmatrix containing variable indices of double lex matrix
nrowsnumber of rows of matrix
ncolsnumber of columns of matrix
rowsbeginarray indicating where a new row block begins
colsbeginarray indicating where a new column block begins
nrowblocksnumber of row blocks
ncolblocksnumber of column blocks
successpointer to store whether orbitope could be added successfully

Definition at line 5893 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
scipSCIP instance
propdatadata of symmetry propagator
detectsinglelexwhether single lex matrices shall be detected
cidxindex of component

Definition at line 6010 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
scipSCIP instance
propdatadata of symmetry propagator
cidxindex of component

Definition at line 6123 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
scipSCIP instance
propdatadata of symmetry propagator
cidxindex of component
nchgbdspointer to store number of bound changes (or NULL)

Definition at line 6176 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
scipSCIP instance
propsymmetry breaking propagator
nchgbdspointer to store number of bound changes (or NULL)
earlytermpointer to store whether we terminated early (or NULL)

Definition at line 6224 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
scipSCIP pointer
propdatapropagator data
infeasiblepointer for storing feasibility state
nredpointer for number of reductions
didrunpointer for storing whether a propagator actually ran

Definition at line 6317 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 6365 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 6403 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 6434 of file prop_symmetry.c.

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

◆ SCIP_DECL_PROPPRESOL()

◆ SCIP_DECL_PROPEXEC()

static SCIP_DECL_PROPEXEC ( propExecSymmetry  )
static

◆ SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitSymmetry  )
static

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

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

References NULL, SCIP_DIDNOTFIND, and SCIP_OKAY.

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeSymmetry  )
static

◆ SCIPincludePropSymmetry()

SCIP_RETCODE SCIPincludePropSymmetry ( SCIP scip)

include symmetry propagator

Parameters
scipSCIP data structure

Definition at line 6703 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_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
scipSCIP data structure
npermvarspointer to store number of variables for permutations
permvarspointer to store variables on which permutations act
permvarmappointer to store hash map of permvars (or NULL)
npermspointer to store number of permutations
permspointer to store permutation generators as (nperms x npermvars) matrix (or NULL)
permstranspointer to store permutation generators as (npermvars x nperms) matrix (or NULL)
log10groupsizepointer to store log10 of group size (or NULL)
binvaraffectedpointer to store whether binary variables are affected (or NULL)
componentspointer to store components of symmetry group (or NULL)
componentbeginspointer to store begin positions of components in components array (or NULL)
vartocomponentpointer to store assignment from variable to its component (or NULL)
ncomponentspointer to store number of components (or NULL)

Definition at line 6994 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
scipSCIP data structure

Definition at line 7093 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
scipSCIP pointer
opnodenamename of new operator node type
nodetypepointer to store the node type

Definition at line 7119 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
scipSCIP pointer
opnodenamename of new operator node type
nodetypepointer to store the node type

Definition at line 7158 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().