SCIP
Solving Constraint Integer Programs
prop_symmetry.c File Reference
Detailed Description
propagator for handling symmetries
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 |
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_RETCODE | printSyminfoHeader (SCIP *scip) |
| static SCIP_RETCODE | printSyminfoFooter (SCIP *scip) |
| static SCIP_RETCODE | printSyminfoComponentHeader (SCIP *scip, SCIP_PROPDATA *propdata, int cidx) |
| static SCIP_RETCODE | printSyminfoGroupAction (SCIP *scip, SCIP_Bool isorbitope, SCIP_Bool isdoublelex, int nrows, int ncols, int nrowmatrices, int ncolmatrices, int *rowsbegin, int *colsbegin) |
| static SCIP_RETCODE | ensureSymmetryMovedPermvarsCountsComputed (SCIP *scip, SCIP_PROPDATA *propdata) |
| static | SCIP_DECL_TABLEOUTPUT (tableOutputSymmetry) |
| static | SCIP_DECL_TABLECOLLECT (tableCollectSymmetry) |
| 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, SCIP_Bool **isproperperm, 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, SCIP_Bool **isproperperm, 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_Bool | hasInferredBinVar (SCIP *scip) |
| static SCIP_Bool | hasInferredIntVar (SCIP *scip) |
| 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 *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 componentid, char *partialname, 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, int *naddedconss) |
| static SCIP_RETCODE | tryAddOrbitalRedLexRed (SCIP *scip, SCIP_PROPDATA *propdata, int cidx) |
| static SCIP_RETCODE | SCIPdisplaySymmetryStatistics (SCIP *scip, SCIP_PROPDATA *propdata) |
| static SCIP_RETCODE | hasOrbitopeColumnFlip (int **varidxmatrix, int startrow, int endrow, int startcol, int endcol, int *signedperm, int npermvars, SCIP_Bool transposed, int *flipablerows, int *nflipablerows) |
| static SCIP_Bool | isEquallyCenteredOrbitope (SCIP *scip, SCIP_Real *vardomaincenter, int **varidxmatrix, int startrow, int endrow, int startcol, int endcol, SCIP_Bool equalrowcenters) |
| static SCIP_RETCODE | handleOrbitope (SCIP *scip, SCIP_PROPDATA *propdata, int componentid, int **varidxmatrix, int nrows, int ncols, char *partialname, SCIP_Bool issigned, SCIP_Bool handlestatically, SCIP_Bool *success, SCIP_Bool allowchgbds, int *nchgbds) |
| static SCIP_RETCODE | handleDoubleLexOrbitope (SCIP *scip, SCIP_PROPDATA *propdata, int **varidxmatrix, int nrows, int ncols, char *partialname, int nsignedrows, SCIP_Bool *success, SCIP_Bool allowchgbds, int *nchgbds) |
| 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, int **signedperms, int nsignedperms, SCIP_Bool *success, SCIP_Bool allowchgbds, int *nchgbds) |
| static SCIP_RETCODE | tryHandleSingleOrDoubleLexMatricesComponent (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool detectsinglelex, int cidx, SCIP_Bool allowchgbds, int *nchgbds) |
| static SCIP_RETCODE | tryHandleSubgroups (SCIP *scip, SCIP_PROPDATA *propdata, int cidx) |
| static SCIP_Bool | isPermKnown (int *perm, int permlen, int **knownperms, int nknownperms, int *permmap) |
| static SCIP_Bool | isInvolution (int *perm, int lenperm, SCIP_Bool *istransposition) |
| static SCIP_RETCODE | tryGenerateInvolutions (SCIP *scip, SCIP_PROPDATA *propdata, int cidx) |
| static SCIP_RETCODE | tryAddSymmetryHandlingMethodsComponent (SCIP *scip, SCIP_PROPDATA *propdata, int cidx, SCIP_Bool allowchgbds, int *nchgbds) |
| static SCIP_RETCODE | tryAddSymmetryHandlingMethods (SCIP *scip, SCIP_PROP *prop, SCIP_Bool allowchgbds, 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 | SCIPdisplaySymmetryGenerators (SCIP *scip, SCIP_PROP *prop) |
| 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_DISPSYMINFO
| #define DEFAULT_DISPSYMINFO FALSE |
Shall symmetry information be printed to the terminal?
Definition at line 164 of file prop_symmetry.c.
◆ DEFAULT_CONSSADDLP
| #define DEFAULT_CONSSADDLP TRUE |
Should the symmetry breaking constraints be added to the LP?
Definition at line 167 of file prop_symmetry.c.
◆ DEFAULT_ADDSYMRESACKS
| #define DEFAULT_ADDSYMRESACKS TRUE |
Add inequalities for symresacks for each generator?
Definition at line 168 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 169 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 170 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 171 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 172 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 173 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 174 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 175 of file prop_symmetry.c.
◆ DEFAULT_USEDYNAMICPROP
| #define DEFAULT_USEDYNAMICPROP TRUE |
whether dynamic propagation should be used for full orbitopes
Definition at line 176 of file prop_symmetry.c.
◆ DEFAULT_PREFERLESSROWS
| #define DEFAULT_PREFERLESSROWS TRUE |
Shall orbitopes with less rows be preferred in detection?
Definition at line 177 of file prop_symmetry.c.
◆ DEFAULT_HANDLESIGNEDORBITOPES
| #define DEFAULT_HANDLESIGNEDORBITOPES TRUE |
Should orbitopes on which proper signed permutations act be handled?"
Definition at line 178 of file prop_symmetry.c.
◆ DEFAULT_USESIMPLESGNCOMP
| #define DEFAULT_USESIMPLESGNCOMP TRUE |
Should components consisting of a single full reflection be handled?
Definition at line 179 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 182 of file prop_symmetry.c.
◆ DEFAULT_PERFORMPRESOLVING
| #define DEFAULT_PERFORMPRESOLVING 0 |
Run orbital fixing during presolving? (disabled parameter)
Definition at line 183 of file prop_symmetry.c.
◆ DEFAULT_RECOMPUTERESTART
| #define DEFAULT_RECOMPUTERESTART 0 |
Recompute symmetries after a restart has occurred? (0 = never)
Definition at line 184 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 187 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 188 of file prop_symmetry.c.
◆ DEFAULT_SSTLEADERVARTYPE
| #define DEFAULT_SSTLEADERVARTYPE 6 |
bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: continuous); if multiple types are allowed, take the one with most affected vars
Definition at line 190 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 191 of file prop_symmetry.c.
◆ DEFAULT_SSTADDCUTS
| #define DEFAULT_SSTADDCUTS TRUE |
Should Schreier Sims constraints be added?
Definition at line 192 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 193 of file prop_symmetry.c.
◆ DEFAULT_MAXNNEWINVOLUS
| #define DEFAULT_MAXNNEWINVOLUS 100 |
maximum number of newly generated involutions per symmetry component
Definition at line 194 of file prop_symmetry.c.
◆ TABLE_NAME_SYMMETRY
| #define TABLE_NAME_SYMMETRY "symmetry" |
Definition at line 197 of file prop_symmetry.c.
◆ TABLE_DESC_SYMMETRY
| #define TABLE_DESC_SYMMETRY "symmetry handling statistics" |
Definition at line 198 of file prop_symmetry.c.
◆ TABLE_POSITION_SYMMETRY
| #define TABLE_POSITION_SYMMETRY 7001 |
the position of the statistics table
Definition at line 199 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 200 of file prop_symmetry.c.
◆ MAXGENNUMERATOR
| #define MAXGENNUMERATOR INT_MAX |
determine maximal number of generators by dividing this number by the number of variables
Definition at line 204 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 205 of file prop_symmetry.c.
◆ DEFAULT_NAUTYMAXLEVEL
| #define DEFAULT_NAUTYMAXLEVEL 10000 |
terminate symmetry detection using Nauty when depth level of Nauty's search tree exceeds this number (avoids call stack overflows in Nauty for deep graphs)
Definition at line 207 of file prop_symmetry.c.
◆ ISSYMRETOPESACTIVE
| #define ISSYMRETOPESACTIVE | ( | x | ) | (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0) |
Definition at line 210 of file prop_symmetry.c.
◆ ISORBITALREDUCTIONACTIVE
| #define ISORBITALREDUCTIONACTIVE | ( | x | ) | (((unsigned) x & SYM_HANDLETYPE_ORBITALREDUCTION) != 0) |
Definition at line 211 of file prop_symmetry.c.
◆ ISSSTACTIVE
| #define ISSSTACTIVE | ( | x | ) | (((unsigned) x & SYM_HANDLETYPE_SST) != 0) |
Definition at line 212 of file prop_symmetry.c.
◆ ISSSTBINACTIVE
| #define ISSSTBINACTIVE | ( | x | ) | (((unsigned) x & SCIP_SSTTYPE_BINARY) != 0) |
Definition at line 214 of file prop_symmetry.c.
◆ ISSSTINTACTIVE
| #define ISSSTINTACTIVE | ( | x | ) | (((unsigned) x & SCIP_SSTTYPE_INTEGER) != 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 341 of file prop_symmetry.c.
◆ SYM_SORTGRAPHCOMPVARS
| typedef struct SYM_Sortgraphcompvars SYM_SORTGRAPHCOMPVARS |
Definition at line 885 of file prop_symmetry.c.
Function Documentation
◆ SCIP_DECL_SORTPTRCOMP()
|
static |
compare function for sorting an array by the addresses of its members
Definition at line 346 of file prop_symmetry.c.
◆ checkSortedArraysHaveOverlappingEntry()
|
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 359 of file prop_symmetry.c.
References FALSE, NULL, and TRUE.
Referenced by componentPackingPartitioningOrbisackUpgrade(), selectOrbitLeaderSSTConss(), and updateSymInfoConflictGraphSST().
◆ displayCycleOfSymmetry()
|
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 428 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 |
displays symmetry information without taking components into account
- Parameters
-
scip SCIP pointer propdata propagator data
Definition at line 473 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 SCIPdisplaySymmetryGenerators().
◆ displaySymmetriesWithComponents()
|
static |
displays symmetry information taking components into account
- Parameters
-
scip SCIP pointer propdata propagator data
Definition at line 522 of file prop_symmetry.c.
References displayCycleOfSymmetry(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPinfoMessage(), and SYM_SYMTYPE_PERM.
Referenced by SCIPdisplaySymmetryGenerators().
◆ printSyminfoHeader()
|
static |
prints header of symmetry information to terminal
- Parameters
-
scip SCIP pointer
Definition at line 590 of file prop_symmetry.c.
References NULL, SCIP_OKAY, and SCIPinfoMessage().
Referenced by tryAddSymmetryHandlingMethods().
◆ printSyminfoFooter()
|
static |
prints footer of symmetry information to terminal
- Parameters
-
scip SCIP pointer
Definition at line 603 of file prop_symmetry.c.
References NULL, SCIP_OKAY, and SCIPinfoMessage().
Referenced by tryAddSymmetryHandlingMethods().
◆ printSyminfoComponentHeader()
|
static |
prints general information about symmetry component to terminal
- Parameters
-
scip SCIP pointer propdata data of symmetry propagator cidx index of component
Definition at line 616 of file prop_symmetry.c.
References NULL, SCIP_OKAY, and SCIPinfoMessage().
Referenced by tryAddSymmetryHandlingMethodsComponent().
◆ printSyminfoGroupAction()
|
static |
prints general information about symmetry component to terminal
- Parameters
-
scip SCIP pointer isorbitope whether group action is orbitopal isdoublelex whether group action id doublelex nrows number of rows for matrix actions ncols number of columns for matrix actions nrowmatrices number of row matrices (for doublelex) ncolmatrices number of column matrices (for doublelex) rowsbegin array to indicate length of row matrices (for doublelex) colsbegin array to indicate length of column matrices (for doublelex)
Definition at line 635 of file prop_symmetry.c.
References NULL, SCIP_OKAY, and SCIPinfoMessage().
Referenced by tryHandleSingleOrDoubleLexMatricesComponent().
◆ ensureSymmetryMovedPermvarsCountsComputed()
|
static |
ensures that movedpermvarscounts is initialized
- Parameters
-
scip SCIP instance propdata propagator data
Definition at line 679 of file prop_symmetry.c.
References NULL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIPerrorMessage, and SCIPgetSymInferredVarType().
Referenced by addSSTConss(), SCIP_DECL_TABLEOUTPUT(), and tryAddOrbitalRedLexRed().
◆ SCIP_DECL_TABLEOUTPUT()
|
static |
output method of symmetry propagator statistics table to output file stream 'file'
Definition at line 748 of file prop_symmetry.c.
References ensureSymmetryMovedPermvarsCountsComputed(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPgetShadowTreeEventHandlerExecutionTime(), SCIPlexicographicReductionGetStatistics(), SCIPorbitalReductionGetStatistics(), SCIPorbitopalReductionGetStatistics(), SCIPtableGetData(), and SCIPverbMessage().
◆ SCIP_DECL_TABLECOLLECT()
|
static |
Definition at line 800 of file prop_symmetry.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcreateDatatreeInTree(), SCIPgetShadowTreeEventHandlerExecutionTime(), SCIPinsertDatatreeInt(), SCIPinsertDatatreeReal(), SCIPlexicographicReductionGetStatistics(), SCIPorbitalReductionGetStatistics(), SCIPorbitopalReductionGetStatistics(), and SCIPtableGetData().
◆ SCIP_DECL_TABLEFREE()
|
static |
destructor of statistics table to free user data (called when SCIP is exiting)
Definition at line 862 of file prop_symmetry.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPtableGetData().
◆ SCIP_DECL_SORTINDCOMP() [1/2]
|
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 897 of file prop_symmetry.c.
References SYM_Sortgraphcompvars::colors, and SYM_Sortgraphcompvars::components.
◆ compareSymgraphs()
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 928 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 |
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 1018 of file prop_symmetry.c.
References compareSymgraphs(), and NULL.
◆ checkSymmetryDataFree()
|
static |
checks that symmetry data is all freed
- Parameters
-
propdata propagator data
Definition at line 1038 of file prop_symmetry.c.
References FALSE, NULL, and TRUE.
Referenced by determineSymmetry(), freeSymmetryData(), and tryAddSymmetryHandlingMethods().
◆ resetDynamicSymmetryHandling()
|
static |
resets symmetry handling propagators that depend on the branch-and-bound tree structure
- Parameters
-
scip SCIP pointer propdata propagator data
Definition at line 1083 of file prop_symmetry.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPlexicographicReductionReset(), SCIPorbitalReductionReset(), and SCIPorbitopalReductionReset().
Referenced by freeSymmetryData(), and SCIP_DECL_PROPEXITSOL().
◆ freeSymmetryData()
|
static |
frees symmetry data
- Parameters
-
scip SCIP pointer propdata propagator data
Definition at line 1111 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 |
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 1280 of file prop_symmetry.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by addOrbitopesDynamic(), addOrbitopeSubgroup(), addStrongSBCsSubgroup(), addSymresackConss(), addWeakSBCsSubgroup(), componentPackingPartitioningOrbisackUpgrade(), detectAndHandleSubgroups(), handleDoubleLexOrbitope(), handleDoublelLexMatrix(), handleOrbitope(), and tryAddOrbitalRedLexRed().
◆ setSymmetryData()
|
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 isproperperm pointer to store whether generators are proper permutations 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 1321 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 |
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 1504 of file prop_symmetry.c.
References NULL, SCIPconshdlrSupportsPermsymDetection(), SCIPconshdlrSupportsSignedPermsymDetection(), SYM_SYMTYPE_PERM, and SYM_SYMTYPE_SIGNPERM.
Referenced by conshdlrsCanProvideSymInformation().
◆ conshdlrsCanProvideSymInformation()
|
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 1523 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 |
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 1606 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 |
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 1708 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 |
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 isproperperm pointer to store whether generators are proper permutations 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 1887 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 |
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 2039 of file prop_symmetry.c.
References FALSE, NULL, SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by checkComponentsForNonstandardPerms().
◆ checkComponentsForNonstandardPerms()
|
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 2076 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 |
ensures that the symmetry components are already computed
- Parameters
-
scip SCIP instance propdata propagator data
Definition at line 2121 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 |
ensures that permvarmap is initialized
- Parameters
-
scip SCIP instance propdata propagator data
Definition at line 2168 of file prop_symmetry.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashmapCreate(), and SCIPhashmapInsertInt().
Referenced by addSSTConss(), componentPackingPartitioningOrbisackUpgrade(), and SCIPgetSymmetry().
◆ ensureSymmetryPermstransComputed()
|
static |
ensures that permstrans is initialized
- Parameters
-
scip SCIP instance propdata propagator data
Definition at line 2200 of file prop_symmetry.c.
References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemoryArray.
Referenced by addSSTConss(), addWeakSBCsSubgroup(), and SCIPgetSymmetry().
◆ hasInferredBinVar()
returns whether a SCIP instance has an active inferred binary variable
- Parameters
-
scip SCIP instance
Definition at line 2234 of file prop_symmetry.c.
References FALSE, NULL, SCIPgetNBinImplVars(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPvarIsBinary(), and TRUE.
Referenced by testSymmetryComputationRequired().
◆ hasInferredIntVar()
returns whether a SCIP instance has an active inferred integer variable
- Parameters
-
scip SCIP instance
Definition at line 2268 of file prop_symmetry.c.
References FALSE, NULL, SCIPgetNBinImplVars(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetVars(), SCIPvarIsBinary(), and TRUE.
Referenced by testSymmetryComputationRequired().
◆ testSymmetryComputationRequired()
|
static |
returns whether any allowed symmetry handling method is effective for the problem instance
- Parameters
-
scip SCIP instance propdata propagator data
Definition at line 2307 of file prop_symmetry.c.
References FALSE, hasInferredBinVar(), hasInferredIntVar(), ISORBITALREDUCTIONACTIVE, ISSSTACTIVE, ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTINTACTIVE, ISSYMRETOPESACTIVE, SCIPconshdlrGetNActiveConss(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNIntVars(), SCIPgetNVars(), and TRUE.
Referenced by determineSymmetry().
◆ determineSymmetry()
|
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 2357 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 |
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
orbitopevaridxhas to be an initialized 2D array of sizentwocyclesxnperms-
columnorderhas to be an initialized array of size nperms -
nusedelemshas 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 2547 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 |
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 2732 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 |
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 2810 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 |
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 success whether the orbitope could be added
Definition at line 3077 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(), SCIPinfoMessage(), SCIPsnprintf(), SCIPvarIsBinary(), and TRUE.
Referenced by detectAndHandleSubgroups().
◆ addStrongSBCsSubgroup()
|
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 3304 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 |
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 3392 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 |
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 3636 of file prop_symmetry.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.
Referenced by addSymresackConss(), and detectAndHandleSubgroups().
◆ getNOrbitopesInComp()
|
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 3718 of file prop_symmetry.c.
References FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPvarIsBinary(), and TRUE.
Referenced by detectAndHandleSubgroups().
◆ detectAndHandleSubgroups()
|
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 3801 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(), SCIPinfoMessage(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarIsBinary(), SCIPvarIsIntegral(), SCIPverbMessage(), SYM_HANDLETYPE_SYMBREAK, and TRUE.
Referenced by tryHandleSubgroups().
◆ updateSymInfoConflictGraphSST()
|
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 4338 of file prop_symmetry.c.
References active, checkSortedArraysHaveOverlappingEntry(), NULL, r, and SCIP_OKAY.
Referenced by addSSTConss().
◆ createConflictGraphSST()
|
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 4451 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 |
frees conflict graph
- Parameters
-
scip SCIP instance varconflicts conflict graph nvars number of nodes in conflict graph
Definition at line 4619 of file prop_symmetry.c.
References NULL, SCIP_OKAY, and SCIPfreeBlockMemoryArray.
Referenced by addSSTConss().
◆ addSymresackConss()
|
static |
adds symresack constraints
- Parameters
-
scip SCIP instance propdata data of symmetry propagator cidx index of component to be handled
Definition at line 4646 of file prop_symmetry.c.
References adaptSymmetryDataSST(), SYM_Sortgraphcompvars::components, ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTINTACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPinfoMessage(), SCIPsnprintf(), SYM_HANDLETYPE_SST, SYM_HANDLETYPE_SYMBREAK, and TRUE.
Referenced by tryAddSymmetryHandlingMethodsComponent().
◆ addSSTConssOrbitAndUpdateSST()
|
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 4785 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, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPchgVarUb(), SCIPcreateConsLinear(), SCIPgetSymInferredVarType(), SCIPinfinity(), SCIPinfoMessage(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), SYM_SYMTYPE_SIGNPERM, and TRUE.
Referenced by addSSTConss().
◆ selectOrbitLeaderSSTConss()
|
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 4962 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, SCIPgetSymInferredVarType(), SCIPvarGetProbindex(), and TRUE.
Referenced by addSSTConss().
◆ addSSTConss()
|
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 5205 of file prop_symmetry.c.
References addSSTConssOrbitAndUpdateSST(), SYM_Sortgraphcompvars::components, createConflictGraphSST(), ensureSymmetryMovedPermvarsCountsComputed(), ensureSymmetryPermstransComputed(), ensureSymmetryPermvarmapComputed(), FALSE, freeConflictGraphSST(), ISSSTBINACTIVE, ISSSTCONTACTIVE, 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_INTEGER, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcomputeOrbitsFilterSym(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSymInferredVarType(), selectOrbitLeaderSSTConss(), SYM_HANDLETYPE_SST, TRUE, and updateSymInfoConflictGraphSST().
Referenced by tryAddSymmetryHandlingMethodsComponent().
◆ addOrbitopesDynamic()
|
static |
orbitopal reduction
- Parameters
-
scip SCIP instance propdata propdata componentid ID of component for which orbitope is added partialname partial name for orbitope constraint 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 5506 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(), SCIPinfoMessage(), SCIPisPackingPartitioningOrbitope(), SCIPlexicographicReductionAddPermutation(), SCIPorbitopalReductionAddOrbitope(), SCIPorbitopalReductionGetDefaultColumnOrdering(), SCIPsnprintf(), and TRUE.
Referenced by handleOrbitope().
◆ componentPackingPartitioningOrbisackUpgrade()
|
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 naddedconss pointer to store number of added constraints
Definition at line 5699 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(), SCIPgetSymInferredVarType(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPhashmapGetImageInt(), SCIPsnprintf(), SCIPsortPtr(), and TRUE.
Referenced by tryAddOrbitalRedLexRed().
◆ tryAddOrbitalRedLexRed()
|
static |
dynamic permutation lexicographic reduction
- Parameters
-
scip SCIP instance propdata propdata cidx index of component
Definition at line 5954 of file prop_symmetry.c.
References componentPackingPartitioningOrbisackUpgrade(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), ensureSymmetryMovedPermvarsCountsComputed(), FALSE, ISORBITALREDUCTIONACTIVE, ISSYMRETOPESACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetParam(), SCIPinfinity(), SCIPinfoMessage(), SCIPlexicographicReductionAddPermutation(), SCIPorbitalReductionAddComponent(), SCIPparamGetBool(), SCIPsnprintf(), SYM_HANDLETYPE_ORBITALREDUCTION, SYM_HANDLETYPE_SYMBREAK, and TRUE.
Referenced by tryAddSymmetryHandlingMethodsComponent().
◆ SCIPdisplaySymmetryStatistics()
|
static |
displays statistics on the used symmetry handling methods
- Parameters
-
scip SCIP instance propdata data of symmetry propagator
Definition at line 6152 of file prop_symmetry.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPlexicographicReductionPrintStatistics(), SCIPorbitalReductionPrintStatistics(), SCIPorbitopalReductionPrintStatistics(), and SCIPverbMessage().
Referenced by tryAddSymmetryHandlingMethods().
◆ hasOrbitopeColumnFlip()
|
static |
checks whether a proper signed permutation flips a (partial) orbitope column
- Parameters
-
varidxmatrix matrix containing variable indices of orbitope startrow row of varidxmatrix in which orbitope starts endrow row of varidxmatrix after which orbitope ends startcol column of varidxmatrix in which orbitope starts endcol column of varidxmatrix after which orbitope ends signedperm signed permutation to be checked npermvars number of variables symmetries act on transposed whether the orbitope is transposed in varidxmatrix flipablerows allocated array to store rows admitting a flip nflipablerows pointer to store number of flipable rows
Definition at line 6200 of file prop_symmetry.c.
References NULL, and SCIP_OKAY.
Referenced by handleDoublelLexMatrix(), and tryHandleSingleOrDoubleLexMatricesComponent().
◆ isEquallyCenteredOrbitope()
|
static |
returns whether every variable in each row of an orbitope matrix has same center
- Parameters
-
scip SCIP instance vardomaincenter array containing domain centers of each variable varidxmatrix matrix containing variable indices of orbitope startrow row of varidxmatrix in which orbitope begins endrow row of varidxmatrix after which orbitope ends startcol column of varidxmatrix in which orbitope begins endcol column of varidxmatrix after which orbitope ends equalrowcenters whether rows are centered equally (otherwise, columns)
Definition at line 6262 of file prop_symmetry.c.
References FALSE, NULL, SCIPisEQ(), and TRUE.
Referenced by handleDoublelLexMatrix(), and tryHandleSingleOrDoubleLexMatricesComponent().
◆ handleOrbitope()
|
static |
handles orbitope action by static or dynamic symmetry handling methods
- Parameters
-
scip SCIP instance propdata data of symmetry propagator componentid ID of component to which orbitope is added varidxmatrix matrix containing variable indices of orbitope nrows number of rows of matrix ncols number of columns of matrix partialname partial name to be extended by constraints issigned whether the first row of the orbitope can be sign-flipped handlestatically whether the orbitope shall be handled statically success pointer to store whether orbitope could be added successfully allowchgbds whether the method is allowed to change variable bounds nchgbds pointer to store number of bound changes (or NULL)
Definition at line 6314 of file prop_symmetry.c.
References addOrbitopesDynamic(), bound, ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, NULL, SCIP_CALL, SCIP_COLUMNORDERING_NONE, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_Real, SCIP_ROWORDERING_NONE, SCIPaddCons(), SCIPallocBufferArray, SCIPchgVarLb(), SCIPcreateConsLinear(), SCIPcreateConsOrbitope(), SCIPfreeBufferArray, SCIPinfinity(), SCIPinfoMessage(), SCIPisLT(), SCIPorbitopalReductionAddOrbitope(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarIsBinary(), and TRUE.
Referenced by handleDoublelLexMatrix(), and tryHandleSingleOrDoubleLexMatricesComponent().
◆ handleDoubleLexOrbitope()
|
static |
handles double lex orbitope action by static symmetry handling methods
- Parameters
-
scip SCIP instance propdata data of symmetry propagator varidxmatrix matrix containing variable indices of orbitope nrows number of rows of matrix ncols number of columns of matrix partialname partial name to be extended by constraints nsignedrows the first number of rows that can be sign-flipped success pointer to store whether orbitope could be added successfully allowchgbds whether the method is allowed to change variable bounds nchgbds pointer to store number of bound changes (or NULL)
Definition at line 6504 of file prop_symmetry.c.
References bound, ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, MAX, NULL, SCIP_CALL, SCIP_COLUMNORDERING_NONE, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_ROWORDERING_NONE, SCIPaddCons(), SCIPallocBufferArray, SCIPchgVarLb(), SCIPcreateConsLinear(), SCIPfreeBufferArray, SCIPinfinity(), SCIPinfoMessage(), SCIPisLT(), SCIPorbitopalReductionAddOrbitope(), SCIPsnprintf(), SCIPvarGetLbLocal(), and TRUE.
Referenced by handleDoublelLexMatrix().
◆ handleDoublelLexMatrix()
|
static |
handles double lex matrix
- Parameters
-
scip SCIP instance propdata data of symmetry propagator id ID of component that is handled 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 signedperms array of proper signed permutations nsignedperms number of proper signed permutations success pointer to store whether orbitope could be added successfully allowchgbds whether the method is allowed to change variable bounds nchgbds pointer to store number of bound changes (or NULL)
Definition at line 6741 of file prop_symmetry.c.
References ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, handleDoubleLexOrbitope(), handleOrbitope(), hasOrbitopeColumnFlip(), isEquallyCenteredOrbitope(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsnprintf(), and TRUE.
Referenced by tryHandleSingleOrDoubleLexMatricesComponent().
◆ tryHandleSingleOrDoubleLexMatricesComponent()
|
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 allowchgbds whether the method is allowed to change variable bounds nchgbds pointer to store number of bound changes (or NULL)
Definition at line 6991 of file prop_symmetry.c.
References FALSE, handleDoublelLexMatrix(), handleOrbitope(), hasOrbitopeColumnFlip(), isEquallyCenteredOrbitope(), NULL, printSyminfoGroupAction(), SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdetectSingleOrDoubleLexMatrices(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPsnprintf(), SYM_HANDLETYPE_SYMBREAK, SYM_SYMTYPE_PERM, and TRUE.
Referenced by tryAddSymmetryHandlingMethodsComponent().
◆ tryHandleSubgroups()
|
static |
tries to handle subgroups of component
- Parameters
-
scip SCIP instance propdata data of symmetry propagator cidx index of component
Definition at line 7210 of file prop_symmetry.c.
References detectAndHandleSubgroups(), ISSYMRETOPESACTIVE, NULL, SCIP_CALL, and SCIP_OKAY.
Referenced by tryAddSymmetryHandlingMethodsComponent().
◆ isPermKnown()
|
static |
returns whether a permutation is already contained in a list of permutations
- Parameters
-
perm permutation to be checked permlen length of permutation knownperms list of known permutations (possibly longer than nknownperms) nknownperms number of known permutations to be checked permmap indices in knownperms to be checked (or NULL for full list)
Definition at line 7242 of file prop_symmetry.c.
References FALSE, NULL, and TRUE.
Referenced by tryGenerateInvolutions().
◆ isInvolution()
returns whether a permutation is an involution
- Parameters
-
perm permutation lenperm length of permutation istransposition pointer to store whether permutation is a transposition
Definition at line 7280 of file prop_symmetry.c.
References FALSE, NULL, and TRUE.
Referenced by tryGenerateInvolutions().
◆ tryGenerateInvolutions()
|
static |
tries to generate involutions based on permutations in component
An involution is a permutation whose 2-fold application is the identity. Involutions are of particular interest, because their support is (in practice) often very small. Propagations based on involutions thus can be executed rather quickly. Moreover, when computing stabilizer subgroups by a filtering mechanism, it is more likely that a (sparse) involution is not filtered in contrast to dense non-involutions.
To create new involutions, we are given a list of involutions that have been found during symmetry detection. We then iterate through all pairs (p,q) of involutions in this list and generate the new involutions p * q (if p and q commute) and p * q * p (if p and q do not commute).
- Parameters
-
scip SCIP instance propdata data of symmetry propagator cidx index of component
Definition at line 7322 of file prop_symmetry.c.
References FALSE, isInvolution(), isPermKnown(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPreallocBlockMemoryArray, SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, and TRUE.
Referenced by tryAddSymmetryHandlingMethodsComponent().
◆ tryAddSymmetryHandlingMethodsComponent()
|
static |
tries to add symmetry handling methods to component of symmetry group
For a component, we handle the symmetries as follows:
- 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 allowchgbds whether the method is allowed to change variable bounds nchgbds pointer to store number of bound changes (or NULL)
Definition at line 7566 of file prop_symmetry.c.
References addSSTConss(), addSymresackConss(), FALSE, ISORBITALREDUCTIONACTIVE, ISSSTACTIVE, ISSYMRETOPESACTIVE, NULL, printSyminfoComponentHeader(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, TRUE, tryAddOrbitalRedLexRed(), tryGenerateInvolutions(), tryHandleSingleOrDoubleLexMatricesComponent(), and tryHandleSubgroups().
Referenced by tryAddSymmetryHandlingMethods().
◆ tryAddSymmetryHandlingMethods()
|
static |
determines problem symmetries and activates symmetry handling methods
- Parameters
-
scip SCIP instance prop symmetry breaking propagator allowchgbds whether the method is allowed to change variable bounds nchgbds pointer to store number of bound changes (or NULL) earlyterm pointer to store whether we terminated early (or NULL)
Definition at line 7636 of file prop_symmetry.c.
References checkSymmetryDataFree(), determineSymmetry(), ensureSymmetryComponentsComputed(), FALSE, NULL, printSyminfoFooter(), printSyminfoHeader(), 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 |
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 7740 of file prop_symmetry.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPlexicographicReductionPropagate(), SCIPorbitalReductionPropagate(), and SCIPorbitopalReductionPropagate().
Referenced by SCIP_DECL_PROPEXEC().
◆ SCIP_DECL_PROPINITPRE()
|
static |
presolving initialization method of propagator (called when presolving is about to begin)
Definition at line 7790 of file prop_symmetry.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPfindConshdlr(), SCIPgetIntParam(), SCIPpropGetData(), SCIPverbMessage(), SYM_TIMING_BEFOREPRESOL, and tryAddSymmetryHandlingMethods().
◆ SCIP_DECL_PROPEXITPRE()
|
static |
presolving deinitialization method of propagator (called after presolving has been finished)
Definition at line 7828 of file prop_symmetry.c.
References FALSE, NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPdebugMsg, SCIPgetStatus(), SCIPpropGetData(), SCIPpropGetName(), and tryAddSymmetryHandlingMethods().
◆ SCIP_DECL_PROPEXITSOL()
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 7859 of file prop_symmetry.c.
References NULL, PROP_NAME, resetDynamicSymmetryHandling(), SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPpropGetData(), and SCIPpropGetName().
◆ SCIP_DECL_PROPPRESOL()
|
static |
presolving method of propagator
Definition at line 7881 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, TRUE, and tryAddSymmetryHandlingMethods().
◆ SCIP_DECL_PROPEXEC()
|
static |
execution method of propagator
Definition at line 7997 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 |
deinitialization method of propagator (called before transformed problem is freed)
Definition at line 8045 of file prop_symmetry.c.
References FALSE, freeSymmetryData(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPpropGetData(), and SCIPpropGetName().
◆ SCIP_DECL_PROPRESPROP()
|
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 8081 of file prop_symmetry.c.
References NULL, SCIP_DIDNOTFIND, and SCIP_OKAY.
◆ SCIP_DECL_PROPFREE()
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 8093 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 8129 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_DISPSYMINFO, DEFAULT_DOUBLEEQUATIONS, DEFAULT_ENFORCECOMPUTESYMMETRY, DEFAULT_HANDLESIGNEDORBITOPES, DEFAULT_MAXGENERATORS, DEFAULT_MAXNCONSSSUBGROUP, DEFAULT_MAXNNEWINVOLUS, DEFAULT_NAUTYMAXLEVEL, 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, DEFAULT_USESIMPLESGNCOMP, FALSE, NULL, PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRESOL_MAXROUNDS, PROP_PRESOL_PRIORITY, PROP_PRESOLTIMING, PROP_PRIORITY, PROP_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPblkmem(), SCIPhashmapCreate(), SCIPincludeEventHdlrShadowTree(), SCIPincludeExternalCodeInformation(), SCIPincludeLexicographicReduction(), SCIPincludeOrbitalReduction(), SCIPincludeOrbitopalReduction(), SCIPincludePropBasic(), SCIPincludeTable(), 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 8430 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 8529 of file prop_symmetry.c.
References NULL, PROP_NAME, SCIPfindProp(), and SCIPpropGetData().
◆ SCIPdisplaySymmetryGenerators()
| SCIP_RETCODE SCIPdisplaySymmetryGenerators | ( | SCIP * | scip, |
| SCIP_PROP * | prop | ||
| ) |
displays generators of symmetry group, if available
- Parameters
-
scip SCIP data structure prop symmetry propagator or NULL
Definition at line 8552 of file prop_symmetry.c.
References displaySymmetriesWithComponents(), displaySymmetriesWithoutComponents(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPfindProp(), SCIPinfoMessage(), and SCIPpropGetData().
Referenced by SCIP_DECL_DIALOGEXEC().
◆ 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 8590 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 8629 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().