propagator for handling symmetries
This propagator combines the following symmetry handling functionalities:
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!
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.
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 |
Functions | |
static | SCIP_DECL_SORTPTRCOMP (sortByPointerValue) |
static SCIP_Bool | checkSortedArraysHaveOverlappingEntry (void **arr1, int narr1, void **arr2, int narr2,) |
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) |
#define PROP_NAME "symmetry" |
Definition at line 141 of file prop_symmetry.c.
#define PROP_DESC "propagator for handling symmetry" |
Definition at line 142 of file prop_symmetry.c.
#define PROP_TIMING SCIP_PROPTIMING_BEFORELP |
propagation timing mask
Definition at line 143 of file prop_symmetry.c.
#define PROP_PRIORITY -1000000 |
propagator priority
Definition at line 144 of file prop_symmetry.c.
#define PROP_FREQ 1 |
propagator frequency
Definition at line 145 of file prop_symmetry.c.
#define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 146 of file prop_symmetry.c.
#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.
#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */ |
Definition at line 149 of file prop_symmetry.c.
#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.
#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.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_CHECKSYMMETRIES FALSE |
Should all symmetries be checked after computation?
Definition at line 155 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_DISPLAYNORBITVARS FALSE |
Should the number of variables affected by some symmetry be displayed?
Definition at line 156 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_DOUBLEEQUATIONS FALSE |
Double equations to positive/negative version?
Definition at line 158 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_COMPRESSSYMMETRIES TRUE |
Should non-affected variables be removed from permutation to save memory?
Definition at line 159 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_SYMFIXNONBINARYVARS FALSE |
Disabled parameter
Definition at line 161 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_ENFORCECOMPUTESYMMETRY FALSE |
always compute symmetries, even if they cannot be handled
Definition at line 162 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_SYMTYPE (int) SYM_SYMTYPE_PERM |
type of symmetries to be computed
Definition at line 163 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_CONSSADDLP TRUE |
Should the symmetry breaking constraints be added to the LP?
Definition at line 166 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_ADDSYMRESACKS TRUE |
Add inequalities for symresacks for each generator?
Definition at line 167 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_ADDWEAKSBCS TRUE |
Should we add weak SBCs for enclosing orbit of symmetric subgroups?
Definition at line 171 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_MAXNCONSSSUBGROUP 500000 |
Maximum number of constraints up to which subgroup structures are detected
Definition at line 174 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_USEDYNAMICPROP TRUE |
whether dynamic propagation should be used for full orbitopes
Definition at line 175 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_PREFERLESSROWS TRUE |
Shall orbitopes with less rows be preferred in detection?
Definition at line 176 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_PERFORMPRESOLVING 0 |
Run orbital fixing during presolving? (disabled parameter)
Definition at line 180 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_RECOMPUTERESTART 0 |
Recompute symmetries after a restart has occurred? (0 = never)
Definition at line 181 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_SSTLEADERRULE 0 |
index of rule for selecting leader variables for Schreier Sims constraints?
Definition at line 185 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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 186 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_SSTADDCUTS TRUE |
Should Schreier Sims constraints be added?
Definition at line 189 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#define TABLE_NAME_SYMMETRY "symmetry" |
Definition at line 193 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define TABLE_DESC_SYMMETRY "symmetry handling statistics" |
Definition at line 194 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define TABLE_POSITION_SYMMETRY 7001 |
the position of the statistics table
Definition at line 195 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by SCIPincludePropSymmetry().
#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.
Referenced by determineSymmetry().
#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.
Referenced by setSymmetryData().
#define DEFAULT_NAUTYMAXNCELLS 100000 |
terminate symmetry detection using Nauty when number of cells in color refinment is at least this number (avoids segfaults due to Nauty for large graphs)
Definition at line 202 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define DEFAULT_NAUTYMAXNNODES 10000000 |
terminate symmetry detection using Nauty when its search tree has at least this number of nodes
Definition at line 204 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
#define ISSYMRETOPESACTIVE | ( | x | ) |
Definition at line 209 of file prop_symmetry.c.
Referenced by testSymmetryComputationRequired(), tryAddOrbitalRedLexRed(), tryAddSymmetryHandlingMethodsComponent(), tryHandleSingleOrDoubleLexMatricesComponent(), and tryHandleSubgroups().
#define ISORBITALREDUCTIONACTIVE | ( | x | ) |
Definition at line 210 of file prop_symmetry.c.
Referenced by testSymmetryComputationRequired(), tryAddOrbitalRedLexRed(), and tryAddSymmetryHandlingMethodsComponent().
#define ISSSTACTIVE | ( | x | ) |
Definition at line 211 of file prop_symmetry.c.
Referenced by testSymmetryComputationRequired(), and tryAddSymmetryHandlingMethodsComponent().
#define ISSSTBINACTIVE | ( | x | ) |
Definition at line 213 of file prop_symmetry.c.
Referenced by addSSTConss(), addSymresackConss(), and testSymmetryComputationRequired().
#define ISSSTINTACTIVE | ( | x | ) |
Definition at line 214 of file prop_symmetry.c.
Referenced by addSSTConss(), addSymresackConss(), and testSymmetryComputationRequired().
#define ISSSTIMPLINTACTIVE | ( | x | ) |
Definition at line 215 of file prop_symmetry.c.
Referenced by addSSTConss(), addSymresackConss(), and testSymmetryComputationRequired().
#define ISSSTCONTACTIVE | ( | x | ) |
Definition at line 216 of file prop_symmetry.c.
Referenced by addSSTConss(), addSymresackConss(), and testSymmetryComputationRequired().
#define SYMMETRY_STATISTICS 1 |
Definition at line 219 of file prop_symmetry.c.
typedef struct SCIP_ConflictData SCIP_CONFLICTDATA |
Definition at line 337 of file prop_symmetry.c.
typedef struct SYM_Sortgraphcompvars SYM_SORTGRAPHCOMPVARS |
Definition at line 699 of file prop_symmetry.c.
|
static |
compare function for sorting an array by the addresses of its members
Definition at line 342 of file prop_symmetry.c.
|
static |
checks whether two arrays that are sorted with the same comparator have a common element
arr1 | first array |
narr1 | number of elements in first array |
arr2 | second array |
narr2 | number of elements in second array comparator function that was used to sort arr1 and arr2; must define a total ordering |
Definition at line 355 of file prop_symmetry.c.
References assert(), FALSE, NULL, SCIP_Bool, and TRUE.
Referenced by componentPackingPartitioningOrbisackUpgrade(), selectOrbitLeaderSSTConss(), and updateSymInfoConflictGraphSST().
|
static |
displays the cycle of a symmetry
scip | SCIP pointer |
perm | symmetry |
symtype | type of symmetry |
baseidx | variable index for which cycle is computed |
covered | allocated array to store covered variables |
nvars | number of (non-negated) variables in symmetry |
vars | variables on which symmetry acts |
Definition at line 424 of file prop_symmetry.c.
References assert(), NULL, nvars, SCIP_Bool, SCIP_OKAY, SCIPinfoMessage(), SCIPvarGetName(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, TRUE, varidx, and vars.
Referenced by checkSymmetriesAreSymmetries(), displaySymmetriesWithComponents(), and displaySymmetriesWithoutComponents().
|
static |
displays symmetry information without taking components into account
scip | SCIP pointer |
propdata | propagator data |
Definition at line 469 of file prop_symmetry.c.
References assert(), displayCycleOfSymmetry(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPinfoMessage(), SYM_SYMTYPE_PERM, and SYM_SYMTYPE_SIGNPERM.
Referenced by SCIP_DECL_DIALOGEXEC().
|
static |
displays symmetry information taking components into account
scip | SCIP pointer |
propdata | propagator data |
Definition at line 518 of file prop_symmetry.c.
References assert(), c, displayCycleOfSymmetry(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPfreeBufferArray, SCIPinfoMessage(), and SYM_SYMTYPE_PERM.
Referenced by SCIP_DECL_DIALOGEXEC().
|
static |
dialog execution method for the display symmetry information command
Definition at line 580 of file prop_symmetry.c.
References assert(), displaySymmetriesWithComponents(), displaySymmetriesWithoutComponents(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdialogGetData(), SCIPdialoghdlrAddHistory(), SCIPdialoghdlrGetRoot(), and SCIPinfoMessage().
|
static |
output method of symmetry propagator statistics table to output file stream 'file'
Definition at line 627 of file prop_symmetry.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPgetShadowTreeEventHandlerExecutionTime(), SCIPlexicographicReductionGetStatistics(), SCIPorbitalReductionGetStatistics(), SCIPorbitopalReductionGetStatistics(), SCIPtableGetData(), and SCIPverbMessage().
|
static |
destructor of statistics table to free user data (called when SCIP is exiting)
Definition at line 676 of file prop_symmetry.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPtableGetData().
|
static |
sorts variable indices according to their corresponding component in the graph
Variables are sorted first by the color of their component and then by the component index.
result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value
0: ind2 comes after (is worse than) ind2
Definition at line 711 of file prop_symmetry.c.
References SYM_Sortgraphcompvars::colors, and SYM_Sortgraphcompvars::components.
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
scip | SCIP pointer (or NULL) |
G1 | first graph in comparison |
G2 | second graph in comparison |
Definition at line 742 of file prop_symmetry.c.
References c, 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().
|
static |
sorts symmetry detection graphs
Graphs are sorted by their number of consnodes, then their constypes, then by their lhs, then by their rhs, then by their total number of nodes, then by the number of operator nodes, then by their number of value nodes, and then by their number of edges.
result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value
0: ind2 comes after (is worse than) ind2
Definition at line 832 of file prop_symmetry.c.
References compareSymgraphs(), and NULL.
|
static |
checks that symmetry data is all freed
propdata | propagator data |
Definition at line 852 of file prop_symmetry.c.
References assert(), FALSE, NULL, SCIP_Bool, and TRUE.
Referenced by determineSymmetry(), freeSymmetryData(), and tryAddSymmetryHandlingMethods().
|
static |
resets symmetry handling propagators that depend on the branch-and-bound tree structure
scip | SCIP pointer |
propdata | propagator data |
Definition at line 897 of file prop_symmetry.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPlexicographicReductionReset(), SCIPorbitalReductionReset(), and SCIPorbitopalReductionReset().
Referenced by freeSymmetryData(), and SCIP_DECL_PROPEXITSOL().
|
static |
frees symmetry data
scip | SCIP pointer |
propdata | propagator data |
Definition at line 925 of file prop_symmetry.c.
References assert(), checkSymmetryDataFree(), FALSE, i, NULL, resetDynamicSymmetryHandling(), SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPhashmapFree(), SCIPreleaseCons(), SCIPreleaseVar(), and SYM_SYMTYPE_SIGNPERM.
Referenced by SCIP_DECL_PROPEXIT().
|
static |
makes sure that the constraint array (potentially NULL) of given array size is sufficiently large
scip | SCIP pointer |
consarrptr | constraint array pointer |
consarrsizeptr | constraint array size pointer |
consarrsizereq | constraint array size required |
Definition at line 1097 of file prop_symmetry.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by addOrbitopesDynamic(), addOrbitopeSubgroup(), addStrongSBCsSubgroup(), addSymresackConss(), addWeakSBCsSubgroup(), componentPackingPartitioningOrbisackUpgrade(), detectAndHandleSubgroups(), handleDoublelLexMatrix(), and handleOrbitope().
|
static |
set symmetry data
scip | SCIP pointer |
symtype | type of symmetries in perms |
vars | vars present at time of symmetry computation |
nvars | number of vars present at time of symmetry computation |
nbinvars | number of binary vars present at time of symmetry computation |
permvars | pointer to permvars array |
npermvars | pointer to store number of permvars |
nbinpermvars | pointer to store number of binary permvars |
permvardomaincenter | pointer to store center points of variable domains |
perms | permutations matrix (nperms x nvars) |
nperms | number of permutations |
nmovedvars | pointer to store number of vars affected by symmetry (if usecompression) or NULL |
binvaraffected | pointer to store whether a binary variable is affected by symmetry |
usecompression | whether symmetry data shall be compressed |
compressthreshold | if percentage of moved vars is at most threshold, compression is done |
compressed | pointer to store whether compression has been performed |
Definition at line 1138 of file prop_symmetry.c.
References assert(), COMPRESSNVARSLB, FALSE, i, nbinvars, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPisGE(), SCIPisLE(), SCIPreallocBlockMemoryArray, SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SYM_SYMTYPE_SIGNPERM, TRUE, and vars.
Referenced by computeSymmetryGroup().
|
static |
returns whether a constraint handler can provide required symmetry information
conshdlr | constraint handler |
symtype | type of symmetries for which information are needed |
Definition at line 1301 of file prop_symmetry.c.
References assert(), NULL, SCIP_Bool, SCIPconshdlrSupportsPermsymDetection(), SCIPconshdlrSupportsSignedPermsymDetection(), SYM_SYMTYPE_PERM, and SYM_SYMTYPE_SIGNPERM.
Referenced by conshdlrsCanProvideSymInformation().
|
static |
returns whether all constraint handlers with constraints can provide symmetry information
scip | SCIP pointer |
symtype | type of symmetries for which information are needed |
Definition at line 1320 of file prop_symmetry.c.
References assert(), c, 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().
|
static |
provides estimates for the number of nodes and edges in a symmetry detection graph
scip | SCIP pointer |
nopnodes | pointer to store estimate for number of operator nodes |
nvalnodes | pointer to store estimate for number of value nodes |
nconsnodes | pointer to store estimate for number of constraint nodes |
nedges | pointer to store estimate for number of edges |
Definition at line 1403 of file prop_symmetry.c.
References assert(), c, depth, MAX, MIN, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetHdlr(), SCIPconshdlrGetName(), SCIPgetConsNVars(), SCIPgetConss(), SCIPgetNConss(), and SCIPgetNVars().
Referenced by computeSymmetryGroup().
|
static |
checks whether computed symmetries are indeed symmetries
scip | SCIP pointer |
symtype | type of symmetries to be checked |
perms | array of permutations |
nperms | number of permutations |
npermvars | number of variables permutations act on |
fixedtype | variable types that must be fixed by symmetries |
Definition at line 1505 of file prop_symmetry.c.
References assert(), c, compareSymgraphs(), displayCycleOfSymmetry(), FALSE, i, 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().
|
static |
computes symmetry group of a CIP
scip | SCIP pointer |
symtype | type of symmetries to be computed |
compresssymmetries | Should non-affected variables be removed from permutation to save memory? |
compressthreshold | if percentage of moved vars is at most threshold, compression is done |
maxgenerators | maximal number of generators constructed (= 0 if unlimited) |
fixedtype | variable types that must be fixed by symmetries |
checksymmetries | Should all symmetries be checked after computation? |
permvars | pointer to permvars array |
npermvars | pointer to store number of permvars |
nbinpermvars | pointer to store number of binary permvars |
permvardomaincenter | pointer to store center points of variable domains |
perms | pointer to store permutation matrix (nperms x nvars) |
nperms | pointer to store number of permutations |
nmaxperms | pointer to store maximal number of permutations (needed for freeing storage) |
nmovedvars | pointer to store number of vars affected by symmetry (if usecompression) or NULL |
binvaraffected | pointer to store whether a binary variable is affected by symmetry |
compressed | pointer to store whether compression has been performed |
log10groupsize | pointer to store log10 of size of group |
symcodetime | pointer to store the time for symmetry code |
success | pointer to store whether symmetry computation was successful |
Definition at line 1684 of file prop_symmetry.c.
References assert(), c, checkSymmetriesAreSymmetries(), conshdlrsCanProvideSymInformation(), estimateSymgraphSize(), FALSE, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcomputeSymgraphColors(), SCIPcreateSymgraph(), SCIPduplicateBlockMemoryArray, SCIPfreeSymgraph(), SCIPgetConsPermsymGraph(), SCIPgetConss(), SCIPgetConsSignedPermsymGraph(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNVars(), SCIPgetSymgraphNVarcolors(), SCIPgetVars(), setSymmetryData(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, SYMcomputeSymmetryGenerators(), TRUE, and vars.
Referenced by determineSymmetry().
returns whether a symmetry is a non-standard permutation
scip | SCIP instance |
symmetry | a symmetry encoded as a signed permutation |
vars | array of variables the symmetry acts on |
nvars | number of variables in vars |
Definition at line 1835 of file prop_symmetry.c.
References assert(), FALSE, NULL, nvars, SCIP_Bool, SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and vars.
Referenced by checkComponentsForNonstandardPerms().
|
static |
checks whether component contains non-standard permutations
If all symmetries are standard permutations, stores them as such.
scip | SCIP instance |
propdata | propagator data |
Definition at line 1872 of file prop_symmetry.c.
References assert(), c, SYM_Sortgraphcompvars::components, i, isNonstandardPerm(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocClearBlockMemoryArray, SYM_SYMTYPE_PERM, and TRUE.
Referenced by ensureSymmetryComponentsComputed().
|
static |
ensures that the symmetry components are already computed
scip | SCIP instance |
propdata | propagator data |
Definition at line 1917 of file prop_symmetry.c.
References assert(), checkComponentsForNonstandardPerms(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPcomputeComponentsSym(), SCIPgetSolvingTime(), and SCIPverbMessage().
Referenced by SCIPgetSymmetry(), and tryAddSymmetryHandlingMethods().
|
static |
ensures that permvarmap is initialized
scip | SCIP instance |
propdata | propagator data |
Definition at line 1964 of file prop_symmetry.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPhashmapCreate(), and SCIPhashmapInsertInt().
Referenced by addSSTConss(), componentPackingPartitioningOrbisackUpgrade(), and SCIPgetSymmetry().
|
static |
ensures that permstrans is initialized
scip | SCIP instance |
propdata | propagator data |
Definition at line 1996 of file prop_symmetry.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemoryArray.
Referenced by addSSTConss(), addWeakSBCsSubgroup(), and SCIPgetSymmetry().
|
static |
ensures that movedpermvarscounts is initialized
scip | SCIP instance |
propdata | propagator data |
Definition at line 2030 of file prop_symmetry.c.
References assert(), 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().
|
static |
returns whether any allowed symmetry handling method is effective for the problem instance
scip | SCIP instance |
propdata | propagator data |
Definition at line 2091 of file prop_symmetry.c.
References FALSE, ISORBITALREDUCTIONACTIVE, ISSSTACTIVE, ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, ISSYMRETOPESACTIVE, SCIP_Bool, SCIPconshdlrGetNActiveConss(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), and TRUE.
Referenced by determineSymmetry().
|
static |
determines symmetry
scip | SCIP instance |
propdata | propagator data |
symspecrequire | symmetry specification for which we need to compute symmetries |
symspecrequirefixed | symmetry specification of variables which must be fixed by symmetries |
Definition at line 2140 of file prop_symmetry.c.
References assert(), checkSymmetryDataFree(), computeSymmetryGroup(), i, MAXGENNUMERATOR, MIN, NULL, nvars, 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().
|
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).
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 scip | SCIP instance |
permvars | array of all permutation variables |
npermvars | number of permutation variables |
perms | array of all permutations of the symmetry group |
activeperms | indices of the relevant permutations in perms |
ntwocycles | number of 2-cycles in the permutations |
nactiveperms | number of active permutations |
orbitopevaridx | pointer to store variable index matrix |
columnorder | pointer to store column order |
nusedelems | pointer to store how often each element was used |
nusedcols | pointer to store number of columns used in orbitope (or NULL) |
rowisbinary | pointer to store which rows are binary (or NULL) |
isorbitope | buffer to store result |
activevars | bitset to store whether a variable is active (or NULL) |
Definition at line 2330 of file prop_symmetry.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocClearBufferArray, SCIPextendSubOrbitope(), SCIPfreeBufferArray, SCIPvarIsBinary(), and TRUE.
Referenced by addOrbitopeSubgroup().
|
static |
choose an order in which the generators should be added for subgroup detection
scip | SCIP instance |
propdata | pointer to data of symmetry propagator |
compidx | index of component |
genorder | (initialized) buffer to store the resulting order of generator |
ntwocycleperms | pointer to store the number of 2-cycle permutations in component compidx |
Definition at line 2515 of file prop_symmetry.c.
References assert(), SYM_Sortgraphcompvars::components, FALSE, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInvolutionPerm(), and SCIPsortIntInt().
Referenced by detectAndHandleSubgroups().
|
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.
scip | SCIP instance |
propdata | pointer to data of symmetry propagator |
genorder | order in which the generators should be considered |
ntwocycleperms | number of 2-cycle permutations in this component |
compidx | index of the component |
graphcomponents | buffer to store the components of the graph (ordered var indices) |
graphcompbegins | buffer to store the indices of each new graph component |
compcolorbegins | buffer to store at which indices a new color begins |
ngraphcomponents | pointer to store the number of graph components |
ncompcolors | pointer to store the number of different colors |
usedperms | buffer to store the indices of permutations that were used |
nusedperms | pointer to store the number of used permutations in the graph |
usedpermssize | initial size of usedperms |
permused | initialized buffer to store which permutations have been used (identified by index in component) |
Definition at line 2593 of file prop_symmetry.c.
References assert(), SYM_Sortgraphcompvars::colors, SYM_Sortgraphcompvars::components, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetGetComponentCount(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPfreeDisjointset(), SCIPreallocBufferArray, SCIPsort(), and TRUE.
Referenced by detectAndHandleSubgroups().
|
static |
adds an orbitope constraint for a suitable color of the subgroup graph
scip | SCIP instance |
propdata | pointer to data of symmetry propagator |
usedperms | array of the permutations that build the orbitope |
nusedperms | number of permutations in usedperms |
compcolorbegins | array indicating where a new graphcolor begins |
graphcompbegins | array indicating where a new graphcomponent begins |
graphcomponents | array of all variable indices sorted by color and comp |
graphcoloridx | index of the graph color |
nrows | number of rows in the orbitope |
ncols | number of columns in the orbitope |
firstvaridx | buffer to store the index of the largest variable (or NULL) |
compidxfirstrow | buffer to store the comp index for the first row (or NULL) |
lexorder | pointer to array storing lexicographic order defined by sub orbitopes |
nvarslexorder | number of variables in lexicographic order |
maxnvarslexorder | maximum number of variables in lexicographic order |
mayinteract | whether orbitope's symmetries might interact with other symmetries |
success | whether the orbitope could be added |
Definition at line 2860 of file prop_symmetry.c.
References assert(), 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(), TRUE, and varidx.
Referenced by detectAndHandleSubgroups().
|
static |
adds strong SBCs for a suitable color of the subgroup graph
scip | SCIP instance |
propdata | pointer to data of symmetry propagator |
graphcompbegins | array indicating where a new graphcomponent begins |
graphcomponents | array of all variable indices sorted by color and comp |
graphcompidx | index of the graph component |
storelexorder | whether the lexicographic order induced by the orbitope shall be stored |
lexorder | pointer to array storing lexicographic order defined by sub orbitopes |
nvarsorder | number of variables in lexicographic order |
maxnvarsorder | maximum number of variables in lexicographic order |
Definition at line 3081 of file prop_symmetry.c.
References assert(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcreateConsLinear(), SCIPinfinity(), SCIPinfoMessage(), SCIPprintCons(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPvarGetName(), TRUE, and vars.
Referenced by detectAndHandleSubgroups().
|
static |
adds weak SBCs for a suitable color of the subgroup graph
scip | SCIP instance |
propdata | pointer to data of symmetry propagator |
compcolorbegins | array indicating where a new graphcolor begins |
graphcompbegins | array indicating where a new graphcomponent begins |
graphcomponents | array of all variable indices sorted by color and comp |
ncompcolors | number of colors in the graph |
chosencomppercolor | array indicating which comp was handled per color |
firstvaridxpercolor | array indicating the largest variable per color |
symgrpcompidx | index of the component of the symmetry group |
naddedconss | buffer to store the number of added constraints |
storelexorder | whether the lexicographic order induced by the orbitope shall be stored |
lexorder | pointer to array storing lexicographic order defined by sub orbitopes |
nvarsorder | number of variables in lexicographic order |
maxnvarsorder | maximum number of variables in lexicographic order |
Definition at line 3165 of file prop_symmetry.c.
References assert(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), ensureSymmetryPermstransComputed(), FALSE, NULL, SCIP_Bool, 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(), TRUE, varidx, and vars.
Referenced by detectAndHandleSubgroups().
|
static |
temporarily adapt symmetry data to new variable order given by Schreier Sims
scip | SCIP instance |
origperms | permutation matrix w.r.t. original variable ordering |
modifiedperms | memory for permutation matrix w.r.t. new variable ordering |
nperms | number of permutations |
origpermvars | array of permutation vars w.r.t. original variable ordering |
modifiedpermvars | memory for array of permutation vars w.r.t. new variable ordering |
npermvars | length or modifiedpermvars array |
leaders | leaders of Schreier Sims constraints |
nleaders | number of leaders |
Definition at line 3407 of file prop_symmetry.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and varidx.
Referenced by addSymresackConss(), and detectAndHandleSubgroups().
|
static |
permvars | array of variables affected by symmetry |
graphcomponents | array of graph components |
graphcompbegins | array indicating starting position of graph components |
compcolorbegins | array indicating starting positions of potential orbitopes |
ncompcolors | number of components encoded in compcolorbegins |
symcompsize | size of symmetry component for that we detect suborbitopes |
Definition at line 3489 of file prop_symmetry.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPvarIsBinary(), and TRUE.
Referenced by detectAndHandleSubgroups().
|
static |
checks whether subgroups of the components are symmetric groups and adds SBCs for them
scip | SCIP instance |
propdata | pointer to data of symmetry propagator |
cidx | index of component which shall be handled |
Definition at line 3572 of file prop_symmetry.c.
References adaptSymmetryDataSST(), addOrbitopeSubgroup(), addStrongSBCsSubgroup(), addWeakSBCsSubgroup(), assert(), buildSubgroupGraph(), chooseOrderOfGenerators(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, getNOrbitopesInComp(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Shortbool, SCIP_VERBLEVEL_HIGH, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNConss(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarIsBinary(), SCIPvarIsIntegral(), SCIPverbMessage(), SYM_HANDLETYPE_SYMBREAK, and TRUE.
Referenced by tryHandleSubgroups().
|
static |
update symmetry information of conflict graph
scip | SCIP instance |
varconflicts | conflict structure |
conflictvars | variables encoded in conflict structure |
nconflictvars | number of nodes/vars in conflict structure |
orbits | array of non-trivial orbits |
orbitbegins | array containing begin positions of new orbits in orbits array |
norbits | number of non-trivial orbits |
Definition at line 4100 of file prop_symmetry.c.
References active, assert(), checkSortedArraysHaveOverlappingEntry(), i, NULL, r, SCIP_OKAY, and var.
Referenced by addSSTConss().
|
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.
scip | SCIP instance |
varconflicts | pointer to store the variable conflict data |
conflictvars | array of variables to encode in conflict graph |
nconflictvars | number of vars to encode in conflict graph |
conflictvarmap | map of variables to indices in conflictvars array |
Definition at line 4213 of file prop_symmetry.c.
References assert(), c, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocClearBufferArray, SCIPcliqueGetId(), SCIPcliqueGetIndex(), SCIPcliqueGetNVars(), SCIPcliqueGetVars(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCliques(), SCIPgetNCliques(), SCIPhashmapGetImageInt(), SCIPsortPtr(), TRUE, and var.
Referenced by addSSTConss().
|
static |
frees conflict graph
scip | SCIP instance |
varconflicts | conflict graph |
nvars | number of nodes in conflict graph |
Definition at line 4381 of file prop_symmetry.c.
References assert(), i, NULL, nvars, SCIP_OKAY, and SCIPfreeBlockMemoryArray.
Referenced by addSSTConss().
|
static |
adds symresack constraints
scip | SCIP instance |
propdata | data of symmetry propagator |
cidx | index of component to be handled |
Definition at line 4408 of file prop_symmetry.c.
References adaptSymmetryDataSST(), assert(), SYM_Sortgraphcompvars::components, ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, i, ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPsnprintf(), SYM_HANDLETYPE_SST, SYM_HANDLETYPE_SYMBREAK, and TRUE.
Referenced by tryAddSymmetryHandlingMethodsComponent().
|
static |
add Schreier Sims constraints for a specific orbit and update Schreier Sims table
scip | SCIP instance |
varconflicts | conflict graph or NULL if useconflictgraph == FALSE |
propdata | data of symmetry propagator |
permvars | permvars array |
orbits | symmetry orbits |
orbitbegins | array storing begin position for each orbit |
orbitidx | index of orbit for Schreier Sims constraints |
orbitleaderidx | index of leader variable for Schreier Sims constraints |
orbitvarinconflict | indicator whether orbitvar is in conflict with orbit leader |
norbitvarinconflict | number of variables in conflict with orbit leader |
nchgbds | pointer to store number of bound changes (or NULL) |
Definition at line 4545 of file prop_symmetry.c.
References active, assert(), FALSE, i, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPchgVarUb(), SCIPcreateConsLinear(), SCIPinfinity(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), TRUE, and vars.
Referenced by addSSTConss().
|
static |
selection rule of next orbit/leader in orbit for Schreier Sims constraints
scip | SCIP instance |
varconflicts | variable conflicts structure, or NULL if we do not use it |
conflictvars | variables encoded in conflict graph |
nconflictvars | number of variables encoded in conflict graph |
orbits | orbits of stabilizer subgroup, expressed in terms of conflictvars |
orbitbegins | array storing the begin position of each orbit in orbits |
norbits | number of orbits |
leaderrule | rule to select leader |
tiebreakrule | tie break rule to select leader |
leadervartype | variable type of leader |
orbitidx | pointer to index of selected orbit |
leaderidx | pointer to leader in orbit |
orbitvarinconflict | array to store whether a var in the orbit is conflicting with leader |
norbitvarinconflict | pointer to store number of vars in the orbit in conflict with leader |
success | pointer to store whether orbit cut be selected successfully |
Definition at line 4697 of file prop_symmetry.c.
References active, assert(), checkSortedArraysHaveOverlappingEntry(), FALSE, i, NULL, SCIP_Bool, SCIP_LEADERRULE_FIRSTINORBIT, SCIP_LEADERRULE_LASTINORBIT, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXORBIT, SCIP_LEADERTIEBREAKRULE_MINORBIT, SCIP_OKAY, SCIP_Shortbool, SCIPvarGetProbindex(), SCIPvarGetType(), TRUE, and varidx.
Referenced by addSSTConss().
|
static |
add Schreier Sims constraints to the problem
scip | SCIP instance |
propdata | data of symmetry propagator |
onlywithcontvars | only handle components that contain continuous variables with SST |
nchgbds | pointer to store number of bound changes (or NULL) |
cidx | index of component which shall be handled |
Definition at line 4940 of file prop_symmetry.c.
References addSSTConssOrbitAndUpdateSST(), assert(), c, SYM_Sortgraphcompvars::components, createConflictGraphSST(), ensureSymmetryMovedpermvarscountsComputed(), ensureSymmetryPermstransComputed(), ensureSymmetryPermvarmapComputed(), FALSE, freeConflictGraphSST(), i, ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LEADERRULE_FIRSTINORBIT, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXORBIT, SCIP_OKAY, SCIP_Shortbool, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcomputeOrbitsFilterSym(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPvarGetType(), selectOrbitLeaderSSTConss(), SYM_HANDLETYPE_SST, TRUE, and updateSymInfoConflictGraphSST().
Referenced by tryAddSymmetryHandlingMethodsComponent().
|
static |
orbitopal reduction
scip | SCIP instance |
propdata | propdata |
id | ID for orbitope constraint (needed for name) |
varidxmatrix | matrix containing variable indices in orbitope matrix |
nrows | number of rows of orbitope |
ncols | number of columns of orbitope |
success | pointer to store whether orbitope could be added successfully |
Definition at line 5240 of file prop_symmetry.c.
References assert(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, i, 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().
|
static |
applies pp-orbitope upgrade if at least 50% of the permutations in a component correspond to pp-orbisacks
scip | SCIP instance |
propdata | propdata |
componentperms | permutations in the component |
componentsize | number of permutations in the component |
hassignedperm | whether the component has a signed permutation |
success | whether the packing partitioning upgrade succeeded |
Definition at line 5412 of file prop_symmetry.c.
References assert(), c, checkSortedArraysHaveOverlappingEntry(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), ensureSymmetryPermvarmapComputed(), FALSE, i, NULL, SCIP_Bool, 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(), TRUE, and var.
Referenced by tryAddOrbitalRedLexRed().
|
static |
dynamic permutation lexicographic reduction
scip | SCIP instance |
propdata | propdata |
cidx | index of component |
Definition at line 5664 of file prop_symmetry.c.
References assert(), componentPackingPartitioningOrbisackUpgrade(), ensureSymmetryMovedpermvarscountsComputed(), ISORBITALREDUCTIONACTIVE, ISSYMRETOPESACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetParam(), SCIPlexicographicReductionAddPermutation(), SCIPorbitalReductionAddComponent(), SCIPparamGetBool(), SYM_HANDLETYPE_ORBITALREDUCTION, SYM_HANDLETYPE_SYMBREAK, and TRUE.
Referenced by tryAddSymmetryHandlingMethodsComponent().
|
static |
displays statistics on the used symmetry handling methods
scip | SCIP instance |
propdata | data of symmetry propagator |
Definition at line 5766 of file prop_symmetry.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPlexicographicReductionPrintStatistics(), SCIPorbitalReductionPrintStatistics(), SCIPorbitopalReductionPrintStatistics(), and SCIPverbMessage().
Referenced by tryAddSymmetryHandlingMethods().
|
static |
handles orbitope action by static or dynamic symmetry handling methods
scip | SCIP instance |
propdata | data of symmetry propagator |
id | ID of orbitope (used for constraint name) |
varidxmatrix | matrix containing variable indices of orbitope |
nrows | number of rows of matrix |
ncols | number of columns of matrix |
success | pointer to store whether orbitope could be added successfully |
Definition at line 5814 of file prop_symmetry.c.
References addOrbitopesDynamic(), assert(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsOrbitope(), SCIPfreeBufferArray, SCIPsnprintf(), SCIPvarIsBinary(), and TRUE.
Referenced by tryHandleSingleOrDoubleLexMatricesComponent().
|
static |
handles binary double lex matrix by adding static orbitope constraints
scip | SCIP instance |
propdata | data of symmetry propagator |
id | ID of double lex matrix (used for constraint names) |
varidxmatrix | matrix containing variable indices of double lex matrix |
nrows | number of rows of matrix |
ncols | number of columns of matrix |
rowsbegin | array indicating where a new row block begins |
colsbegin | array indicating where a new column block begins |
nrowblocks | number of row blocks |
ncolblocks | number of column blocks |
success | pointer to store whether orbitope could be added successfully |
Definition at line 5898 of file prop_symmetry.c.
References assert(), ensureDynamicConsArrayAllocatedAndSufficientlyLarge(), FALSE, i, MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsOrbitope(), SCIPfreeBufferArray, SCIPsnprintf(), SCIPvarIsBinary(), and TRUE.
Referenced by tryHandleSingleOrDoubleLexMatricesComponent().
|
static |
tries to handle symmetries of single lex matrices (orbitopes) or double lex matrices
scip | SCIP instance |
propdata | data of symmetry propagator |
detectsinglelex | whether single lex matrices shall be detected |
cidx | index of component |
Definition at line 6015 of file prop_symmetry.c.
References assert(), FALSE, handleDoublelLexMatrix(), handleOrbitope(), i, ISSYMRETOPESACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdetectSingleOrDoubleLexMatrices(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPvarIsBinary(), SYM_HANDLETYPE_SYMBREAK, and TRUE.
Referenced by tryAddSymmetryHandlingMethodsComponent().
|
static |
tries to handle subgroups of component
scip | SCIP instance |
propdata | data of symmetry propagator |
cidx | index of component |
Definition at line 6128 of file prop_symmetry.c.
References assert(), detectAndHandleSubgroups(), ISSYMRETOPESACTIVE, NULL, SCIP_CALL, and SCIP_OKAY.
Referenced by tryAddSymmetryHandlingMethodsComponent().
|
static |
tries to add symmetry handling methods to component of symmetry group
For a component, we handle the symmetries as follows:
scip | SCIP instance |
propdata | data of symmetry propagator |
cidx | index of component |
nchgbds | pointer to store number of bound changes (or NULL) |
Definition at line 6181 of file prop_symmetry.c.
References addSSTConss(), addSymresackConss(), assert(), FALSE, ISORBITALREDUCTIONACTIVE, ISSSTACTIVE, ISSYMRETOPESACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, TRUE, tryAddOrbitalRedLexRed(), tryHandleSingleOrDoubleLexMatricesComponent(), and tryHandleSubgroups().
Referenced by tryAddSymmetryHandlingMethods().
|
static |
determines problem symmetries and activates symmetry handling methods
scip | SCIP instance |
prop | symmetry breaking propagator |
nchgbds | pointer to store number of bound changes (or NULL) |
earlyterm | pointer to store whether we terminated early (or NULL) |
Definition at line 6229 of file prop_symmetry.c.
References assert(), c, checkSymmetryDataFree(), determineSymmetry(), ensureSymmetryComponentsComputed(), FALSE, NULL, SCIP_Bool, 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().
|
static |
apply propagation methods for various symmetry handling constraints
scip | SCIP pointer |
propdata | propagator data |
infeasible | pointer for storing feasibility state |
nred | pointer for number of reductions |
didrun | pointer for storing whether a propagator actually ran |
Definition at line 6322 of file prop_symmetry.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPlexicographicReductionPropagate(), SCIPorbitalReductionPropagate(), and SCIPorbitopalReductionPropagate().
Referenced by SCIP_DECL_PROPEXEC().
|
static |
presolving initialization method of propagator (called when presolving is about to begin)
Definition at line 6370 of file prop_symmetry.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPfindConshdlr(), SCIPgetIntParam(), SCIPpropGetData(), SCIPverbMessage(), SYM_TIMING_BEFOREPRESOL, and tryAddSymmetryHandlingMethods().
|
static |
presolving deinitialization method of propagator (called after presolving has been finished)
Definition at line 6408 of file prop_symmetry.c.
References assert(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPdebugMsg, SCIPgetStatus(), SCIPpropGetData(), SCIPpropGetName(), and tryAddSymmetryHandlingMethods().
|
static |
solving process deinitialization method of propagator (called before branch and bound process data is freed)
Definition at line 6439 of file prop_symmetry.c.
References assert(), NULL, PROP_NAME, resetDynamicSymmetryHandling(), SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPpropGetData(), and SCIPpropGetName().
|
static |
presolving method of propagator
Definition at line 6461 of file prop_symmetry.c.
References assert(), i, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PROPTIMING_ALWAYS, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIPconsGetName(), SCIPdebugMsg, SCIPgetStage(), SCIPisPresolveFinished(), SCIPisStopped(), SCIPpresolCons(), SCIPpropGetData(), SYM_TIMING_AFTERPRESOL, SYM_TIMING_DURINGPRESOL, and tryAddSymmetryHandlingMethods().
|
static |
execution method of propagator
Definition at line 6577 of file prop_symmetry.c.
References assert(), NULL, propagateSymmetry(), result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPgetDepth(), SCIPgetStage(), SCIPpropGetData(), and TRUE.
|
static |
deinitialization method of propagator (called before transformed problem is freed)
Definition at line 6624 of file prop_symmetry.c.
References assert(), FALSE, freeSymmetryData(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPpropGetData(), and SCIPpropGetName().
|
static |
propagation conflict resolving method of propagator
Note that this is relatively difficult to obtain: One needs to include all bounds of variables that are responsible for creating the orbit in which the variables that was propagated lies. This includes all variables that are moved by the permutations which are involved in creating the orbit.
Definition at line 6660 of file prop_symmetry.c.
References assert(), NULL, result, SCIP_DIDNOTFIND, and SCIP_OKAY.
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 6672 of file prop_symmetry.c.
References assert(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPhashmapFree(), SCIPlexicographicReductionFree(), SCIPorbitalReductionFree(), SCIPorbitopalReductionFree(), SCIPpropGetData(), and SCIPpropGetName().
SCIP_RETCODE SCIPincludePropSymmetry | ( | SCIP * | scip | ) |
include symmetry propagator
scip | SCIP data structure |
Definition at line 6708 of file prop_symmetry.c.
References assert(), DEFAULT_ADDCONFLICTCUTS, DEFAULT_ADDCONSSTIMING, DEFAULT_ADDSTRONGSBCS, DEFAULT_ADDSYMRESACKS, DEFAULT_ADDWEAKSBCS, DEFAULT_CHECKSYMMETRIES, DEFAULT_COMPRESSSYMMETRIES, DEFAULT_COMPRESSTHRESHOLD, DEFAULT_CONSSADDLP, DEFAULT_DETECTDOUBLELEX, DEFAULT_DETECTORBITOPES, DEFAULT_DETECTSUBGROUPS, DEFAULT_DISPLAYNORBITVARS, DEFAULT_DOUBLEEQUATIONS, DEFAULT_ENFORCECOMPUTESYMMETRY, DEFAULT_MAXGENERATORS, DEFAULT_MAXNCONSSSUBGROUP, DEFAULT_NAUTYMAXNCELLS, DEFAULT_NAUTYMAXNNODES, DEFAULT_PERFORMPRESOLVING, DEFAULT_PREFERLESSROWS, DEFAULT_RECOMPUTERESTART, DEFAULT_SSTADDCUTS, DEFAULT_SSTLEADERRULE, DEFAULT_SSTLEADERVARTYPE, DEFAULT_SSTMIXEDCOMPONENTS, DEFAULT_SSTTIEBREAKRULE, DEFAULT_SYMCOMPTIMING, DEFAULT_SYMFIXNONBINARYVARS, DEFAULT_SYMTYPE, DEFAULT_USECOLUMNSPARSITY, DEFAULT_USEDYNAMICPROP, FALSE, NULL, PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRESOL_MAXROUNDS, PROP_PRESOL_PRIORITY, PROP_PRESOLTIMING, PROP_PRIORITY, PROP_TIMING, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPaddBoolParam(), SCIPaddDialogEntry(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPblkmem(), SCIPdialogFindEntry(), SCIPdialogHasEntry(), SCIPerrorMessage, SCIPgetRootDialog(), SCIPhashmapCreate(), SCIPincludeDialog(), SCIPincludeEventHdlrShadowTree(), SCIPincludeExternalCodeInformation(), SCIPincludeLexicographicReduction(), SCIPincludeOrbitalReduction(), SCIPincludeOrbitopalReduction(), SCIPincludePropBasic(), SCIPincludeTable(), SCIPreleaseDialog(), SCIPsetPropExit(), SCIPsetPropExitpre(), SCIPsetPropExitsol(), SCIPsetPropFree(), SCIPsetPropInitpre(), SCIPsetPropPresol(), SCIPsetPropResprop(), SYM_CONSOPTYPE_LAST, SYMcanComputeSymmetry(), SYMsymmetryGetAddDesc(), SYMsymmetryGetAddName(), SYMsymmetryGetDesc(), SYMsymmetryGetName(), TABLE_DESC_SYMMETRY, TABLE_EARLIEST_SYMMETRY, TABLE_NAME_SYMMETRY, TABLE_POSITION_SYMMETRY, and TRUE.
Referenced by SCIPincludeDefaultPlugins().
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
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 7015 of file prop_symmetry.c.
References assert(), SYM_Sortgraphcompvars::components, ensureSymmetryComponentsComputed(), ensureSymmetryPermstransComputed(), ensureSymmetryPermvarmapComputed(), NULL, PROP_NAME, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIPerrorMessage, SCIPfindProp(), SCIPpropGetData(), and SCIPpropGetName().
Referenced by initOrbits().
int SCIPgetSymmetryNGenerators | ( | SCIP * | scip | ) |
return number of the symmetry group's generators
scip | SCIP data structure |
Definition at line 7114 of file prop_symmetry.c.
References assert(), NULL, PROP_NAME, SCIPfindProp(), and SCIPpropGetData().
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.
scip | SCIP pointer |
opnodename | name of new operator node type |
nodetype | pointer to store the node type |
Definition at line 7140 of file prop_symmetry.c.
References assert(), NULL, PROP_NAME, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPerrorMessage, SCIPfindProp(), SCIPhashmapExists(), SCIPhashmapInsertInt(), and SCIPpropGetData().
Referenced by 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.
scip | SCIP pointer |
opnodename | name of new operator node type |
nodetype | pointer to store the node type |
Definition at line 7179 of file prop_symmetry.c.
References assert(), NULL, PROP_NAME, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPcreateSymOpNodeType(), SCIPerrorMessage, SCIPfindProp(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), and SCIPpropGetData().
Referenced by addSymmetryInformation(), tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperatorSum(), and tryAddGadgetEvenOperatorVariable().