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 allows to add the following symmetry breaking constraints:
- symresack constraints, which separate minimal cover inequalities
- orbitope constraints, if special symmetry group structures are detected
- It allows to apply orbital fixing.
Symmetry Computation
The following comments apply to symmetry computation.
- The generic functionality of the compute_symmetry.h interface is used.
- We treat implicit integer variables as if they were continuous/real variables. The reason is that there is currently no distinction between implicit integer and implicit binary. Moreover, currently implicit integer variables hurt our code more than continuous/real variables (we basically do not handle integral variables at all).
- We do not copy symmetry information, since it is not clear how this information transfers. Moreover, copying symmetry might inhibit heuristics. But note that solving a sub-SCIP might then happen without symmetry information!
Symmetry Handling Constraints
The following comments apply to adding symmetry handling constraints.
- The code automatically detects whether symmetry substructures like symresacks or orbitopes are present and possibly adds the corresponding constraints.
- If orbital fixing is active, only orbitopes are added (if present) and no symresacks.
- We try to compute symmetry as late as possible and then add constraints based on this information.
- Currently, we only allocate memory for pointers to symresack constraints for group generators. If further constraints are considered, we have to reallocate memory.
Orbital Fixing
Orbital fixing is implemented as introduced by
F. Margot: Exploiting orbits in symmetric ILP. Math. Program., 98(1-3):3–21, 2003.
The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the variables globally fixed or branched to 1. Then one can fix all variables in an orbit to 0 or 1 if one of the other variables in the orbit is fixed to 0 or 1, respectively. Different from Margot, the subgroup is obtained by filtering out generators that do not individually stabilize the variables branched to 1.
- Precondition
- All variable fixings applied by other components are required to be strict, i.e., if one variable is fixed to a certain value v, all other variables in the same variable orbit can be fixed to v as well, c.f.
F. Margot: Symmetry in integer linear programming. 50 Years of Integer Programming, 647-686, Springer 2010.
To illustrate this, consider the example \(\max\{x_1 + x_2 : x_1 + x_2 \leq 1, Ay \leq b, (x,y) \in \{0,1\}^{2 + n}\} \). Since \(x_1\) and \(x_2\) are independent from the remaining problem, the setppc constraint handler may fix \((x_1,x_2) = (1,0)\). However, since both variables are symmetric, this setting is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different values). To avoid this situation, we have to assume that all non-strict settings fix variables globally, i.e., we can take care of it by taking variables into account that have been globally fixed to 1. In fact, it suffices to consider one kind of global fixings since stabilizing one kind prevents an orbit to contain variables that have been fixed globally to different values.
- Precondition
- All non-strict settings are global settings, since otherwise, we cannot (efficiently) take care of them.
- No non-strict setting algorithm is interrupted early (e.g., by a time or iteration limit), since this may lead to wrong decisions by orbital fixing as well. For example, if cons_setppc in the above toy example starts by fixing \(x_2 = 0\) and is interrupted afterwards, orbital fixing detects that the orbit \(\{x_1, x_2\}\) contains one variable that is fixed to 0, and thus, it fixes \(x_1\) to 0 as well. Thus, after these reductions, every feasible solution has objective 0 which is not optimal. This situation would not occur if the non-strict setting is complete, because then \(x_1\) is globally fixed to 1, and thus, is stabilized in orbital fixing.
Note that orbital fixing might lead to wrong results if it is called in repropagation of a node, because the path from the node to the root might have been changed. Thus, the stabilizers of global 1-fixing and 1-branchings of the initial propagation and repropagation might differ, which may cause conflicts. For this reason, orbital fixing cannot be called in repropagation.
- Note
- If, besides orbital fixing, also symmetry handling constraints shall be added, orbital fixing is only applied to symmetry components that are not handled by orbitope constraints.
Cuts derived from the Schreier Sims table
SST cuts have been introduced by
D. Salvagnin: Symmetry Breaking Inequalities from the Schreier-Sims table. CPAIOR 2018 Proceedings, 521-529, 2018.
These inequalities are computed as follows. Throughout these procedure a set of so-called leaders is maintained. Initially the set of leaders is empty. In a first step, select a variable \(x_i\) and compute its orbit w.r.t. the symmetry group of the mixed-integer program. For each variable \(x_j\) in the orbit of \(x_i\), the inequality \(x_i \geq x_j\) is a valid symmetry handling inequality, which can be added to the mixed-integer program. We call \(x_i\) the leader of this inequality. Add the leader \(x_i\) to the set of leaders and compute the pointwise stabilizer of the leader set. In the next step, select a new variable, compute its orbit w.r.t. the stabilizer group of the leaders, add the inequalities based on this orbit, and add the new leader to the set of leaders. This procedure is iterated until the pointwise stabilizer group of the leaders has become trivial.
Definition in file prop_symmetry.c.
#include <scip/cons_linear.h>
#include <scip/cons_knapsack.h>
#include <scip/cons_varbound.h>
#include <scip/cons_setppc.h>
#include <scip/cons_and.h>
#include <scip/cons_logicor.h>
#include <scip/cons_or.h>
#include <scip/cons_orbitope.h>
#include <scip/cons_symresack.h>
#include <scip/cons_xor.h>
#include <scip/cons_linking.h>
#include <scip/cons_bounddisjunction.h>
#include <scip/cons_nonlinear.h>
#include <scip/pub_expr.h>
#include <scip/misc.h>
#include <scip/scip_datastructures.h>
#include <scip/prop_symmetry.h>
#include <symmetry/compute_symmetry.h>
#include <scip/symmetry.h>
#include <string.h>
Go to the source code of this file.
Data Structures | |
struct | SYM_Sortrhstype |
struct | SYM_Sortgraphcompvars |
Typedefs | |
typedef struct SCIP_NodeData | SCIP_NODEDATA |
typedef struct SYM_Sortrhstype | SYM_SORTRHSTYPE |
typedef struct SYM_Sortgraphcompvars | SYM_SORTGRAPHCOMPVARS |
Functions | |
static | SCIP_DECL_EVENTEXEC (eventExecSymmetry) |
static | SCIP_DECL_TABLEOUTPUT (tableOutputOrbitalfixing) |
static | SCIP_DECL_TABLEFREE (tableFreeOrbitalfixing) |
static | SCIP_DECL_HASHGETKEY (SYMhashGetKeyVartype) |
static | SCIP_DECL_HASHKEYEQ (SYMhashKeyEQVartype) |
static | SCIP_DECL_HASHKEYVAL (SYMhashKeyValVartype) |
static | SCIP_DECL_SORTINDCOMP (SYMsortRhsTypes) |
static | SCIP_DECL_SORTINDCOMP (SYMsortMatCoef) |
static | SCIP_DECL_SORTINDCOMP (SYMsortGraphCompVars) |
static SCIP_Bool | checkSymmetryDataFree (SCIP_PROPDATA *propdata) |
static SCIP_Bool | isLeadervartypeCompatible (SCIP_VAR *var, int leadervartype) |
static SCIP_RETCODE | setSymmetryMethodEnabledValues (SCIP_PROPDATA *propdata) |
static SCIP_RETCODE | freeSymmetryData (SCIP *scip, SCIP_PROPDATA *propdata) |
static SCIP_Bool | SymmetryFixVar (SYM_SPEC fixedtype, SCIP_VAR *var) |
static SCIP_RETCODE | getActiveVariables (SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed) |
static SCIP_RETCODE | collectCoefficients (SCIP *scip, SCIP_Bool doubleequations, SCIP_VAR **linvars, SCIP_Real *linvals, int nlinvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool istransformed, SYM_RHSSENSE rhssense, SYM_MATRIXDATA *matrixdata, int *nconssforvar) |
static SCIP_RETCODE | checkSymmetriesAreSymmetries (SCIP *scip, SYM_SPEC fixedtype, SYM_MATRIXDATA *matrixdata, int nperms, int **perms) |
static int | getNSymhandableConss (SCIP *scip, SCIP_CONSHDLR *conshdlr_nonlinear) |
static SCIP_Bool | hasNonlinearConstraints (SCIP_PROPDATA *propdata) |
static SCIP_RETCODE | setSymmetryData (SCIP *scip, SCIP_VAR **vars, int nvars, int nbinvars, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, int **perms, int nperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool *compressed) |
static SCIP_RETCODE | computeSymmetryGroup (SCIP *scip, SCIP_Bool doubleequations, SCIP_Bool compresssymmetries, SCIP_Real compressthreshold, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool local, SCIP_Bool checksymmetries, SCIP_Bool usecolumnsparsity, SCIP_CONSHDLR *conshdlr_nonlinear, int *npermvars, int *nbinpermvars, SCIP_VAR ***permvars, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, int *nmovedvars, SCIP_Bool **isnonlinvar, SCIP_Bool *binvaraffected, SCIP_Bool *compressed, SCIP_Bool *success) |
static SCIP_RETCODE | determineSymmetry (SCIP *scip, SCIP_PROPDATA *propdata, SYM_SPEC symspecrequire, SYM_SPEC symspecrequirefixed) |
static SCIP_RETCODE | checkTwoCyclePermsAreOrbitope (SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int *activeperms, int ntwocycles, int nactiveperms, int **orbitopevaridx, int *columnorder, int *nusedelems, int *nusedcols, SCIP_Shortbool *rowisbinary, SCIP_Bool *isorbitope, SCIP_Shortbool *activevars) |
static SCIP_RETCODE | chooseOrderOfGenerators (SCIP *scip, SCIP_PROPDATA *propdata, int compidx, int **genorder, int *ntwocycleperms) |
static SCIP_RETCODE | buildSubgroupGraph (SCIP *scip, SCIP_PROPDATA *propdata, int *genorder, int ntwocycleperms, int compidx, int **graphcomponents, int **graphcompbegins, int **compcolorbegins, int *ngraphcomponents, int *ncompcolors, int **usedperms, int *nusedperms, int usedpermssize, SCIP_Shortbool *permused) |
static SCIP_RETCODE | addOrbitopeSubgroup (SCIP *scip, SCIP_PROPDATA *propdata, int *usedperms, int nusedperms, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int graphcoloridx, int nrows, int ncols, int *firstvaridx, int *compidxfirstrow, int **lexorder, int *nvarslexorder, int *maxnvarslexorder, SCIP_Bool mayinteract, SCIP_Bool *success) |
static SCIP_RETCODE | addStrongSBCsSubgroup (SCIP *scip, SCIP_PROPDATA *propdata, int *graphcompbegins, int *graphcomponents, int graphcompidx, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder) |
static SCIP_RETCODE | addWeakSBCsSubgroup (SCIP *scip, SCIP_PROPDATA *propdata, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int ncompcolors, int *chosencomppercolor, int *firstvaridxpercolor, int symgrpcompidx, int *naddedconss, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder) |
static SCIP_RETCODE | adaptSymmetryDataSST (SCIP *scip, int **origperms, int **modifiedperms, int nperms, SCIP_VAR **origpermvars, SCIP_VAR **modifiedpermvars, int npermvars, int *leaders, int nleaders) |
static int | getNOrbitopesInComp (SCIP_VAR **permvars, int *graphcomponents, int *graphcompbegins, int *compcolorbegins, int ncompcolors, int symcompsize) |
static SCIP_RETCODE | detectAndHandleSubgroups (SCIP *scip, SCIP_PROPDATA *propdata) |
static SCIP_RETCODE | SCIPsortOrbitope (SCIP *scip, int **orbitopevaridx, SCIP_VAR ***vars, int nrows, int ncols) |
static SCIP_RETCODE | detectOrbitopes (SCIP *scip, SCIP_PROPDATA *propdata, int *components, int *componentbegins, int ncomponents) |
static SCIP_RETCODE | updateSymInfoConflictGraphSST (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_VAR **permvars, int npermvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *varmap, int *orbits, int *orbitbegins, int norbits) |
static SCIP_RETCODE | createConflictGraphSST (SCIP *scip, SCIP_DIGRAPH **conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *permvarmap, SCIP_Bool *success) |
static SCIP_RETCODE | freeConflictGraphSST (SCIP *scip, SCIP_DIGRAPH **conflictgraph, int nnodes) |
static SCIP_RETCODE | addSymresackConss (SCIP *scip, SCIP_PROP *prop, int *components, int *componentbegins, int ncomponents) |
static SCIP_RETCODE | addSSTConssOrbitAndUpdateSST (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_PROPDATA *propdata, SCIP_VAR **permvars, int *orbits, int *orbitbegins, int orbitidx, int orbitleaderidx, SCIP_Shortbool *orbitvarinconflict, int norbitvarinconflict, int *nchgbds, SCIP_Bool useconflictgraph) |
static SCIP_RETCODE | selectOrbitLeaderSSTConss (SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_HASHMAP *varmap, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, int leaderrule, int tiebreakrule, SCIP_VARTYPE leadervartype, int *orbitidx, int *leaderidx, SCIP_Shortbool *orbitvarinconflict, int *norbitvarinconflict, SCIP_Bool useconflictgraph, SCIP_Bool *success) |
static SCIP_RETCODE | addSSTConss (SCIP *scip, SCIP_PROPDATA *propdata, int *nchgbds) |
static SCIP_RETCODE | tryAddSymmetryHandlingConss (SCIP *scip, SCIP_PROP *prop, int *nchgbds, SCIP_Bool *earlyterm) |
static SCIP_RETCODE | performOrbitalFixing (SCIP *scip, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, SCIP_Bool *infeasible, int *nfixedzero, int *nfixedone) |
static SCIP_RETCODE | computeBranchingVariables (SCIP *scip, int nvars, SCIP_HASHMAP *varmap, SCIP_Shortbool *bg1, int *bg1list, int *nbg1) |
static SCIP_RETCODE | propagateOrbitalFixing (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nprop) |
static | SCIP_DECL_PROPINITPRE (propInitpreSymmetry) |
static | SCIP_DECL_PROPEXITPRE (propExitpreSymmetry) |
static | SCIP_DECL_PROPPRESOL (propPresolSymmetry) |
static | SCIP_DECL_PROPEXEC (propExecSymmetry) |
static | SCIP_DECL_PROPEXIT (propExitSymmetry) |
static | SCIP_DECL_PROPRESPROP (propRespropSymmetry) |
static | SCIP_DECL_PROPFREE (propFreeSymmetry) |
SCIP_RETCODE | SCIPincludePropSymmetry (SCIP *scip) |
SCIP_RETCODE | SCIPgetSymmetry (SCIP *scip, int *npermvars, SCIP_VAR ***permvars, SCIP_HASHMAP **permvarmap, int *nperms, int ***perms, int ***permstrans, SCIP_Real *log10groupsize, SCIP_Bool *binvaraffected, int **components, int **componentbegins, int **vartocomponent, int *ncomponents) |
SCIP_Bool | SCIPisOrbitalfixingEnabled (SCIP *scip) |
int | SCIPgetSymmetryNGenerators (SCIP *scip) |
Macro Definition Documentation
◆ PROP_NAME
#define PROP_NAME "symmetry" |
Definition at line 162 of file prop_symmetry.c.
Referenced by SCIP_DECL_PROPEXIT(), SCIP_DECL_PROPEXITPRE(), SCIP_DECL_PROPFREE(), SCIP_DECL_PROPPRESOL(), SCIPgetSymmetry(), SCIPgetSymmetryNGenerators(), SCIPincludePropSymmetry(), and SCIPisOrbitalfixingEnabled().
◆ PROP_DESC
#define PROP_DESC "propagator for handling symmetry" |
Definition at line 163 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ PROP_TIMING
#define PROP_TIMING SCIP_PROPTIMING_BEFORELP |
propagation timing mask
Definition at line 164 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ PROP_PRIORITY
#define PROP_PRIORITY -1000000 |
propagator priority
Definition at line 165 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ PROP_FREQ
#define PROP_FREQ 1 |
propagator frequency
Definition at line 166 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ PROP_DELAY
#define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 167 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ PROP_PRESOL_PRIORITY
#define PROP_PRESOL_PRIORITY -10000000 |
priority of the presolving method (>= 0: before, < 0: after constraint handlers)
Definition at line 169 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ PROP_PRESOLTIMING
#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */ |
Definition at line 170 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ PROP_PRESOL_MAXROUNDS
#define PROP_PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 171 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_MAXGENERATORS
#define DEFAULT_MAXGENERATORS 1500 |
limit on the number of generators that should be produced within symmetry detection (0 = no limit)
Definition at line 175 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_CHECKSYMMETRIES
#define DEFAULT_CHECKSYMMETRIES FALSE |
Should all symmetries be checked after computation?
Definition at line 176 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_DISPLAYNORBITVARS
#define DEFAULT_DISPLAYNORBITVARS FALSE |
Should the number of variables affected by some symmetry be displayed?
Definition at line 177 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_USECOLUMNSPARSITY
#define DEFAULT_USECOLUMNSPARSITY FALSE |
Should the number of conss a variable is contained in be exploited in symmetry detection?
Definition at line 178 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_DOUBLEEQUATIONS
#define DEFAULT_DOUBLEEQUATIONS FALSE |
Double equations to positive/negative version?
Definition at line 179 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_COMPRESSSYMMETRIES
#define DEFAULT_COMPRESSSYMMETRIES TRUE |
Should non-affected variables be removed from permutation to save memory?
Definition at line 180 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_COMPRESSTHRESHOLD
#define DEFAULT_COMPRESSTHRESHOLD 0.5 |
Compression is used if percentage of moved vars is at most the threshold.
Definition at line 181 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_SYMFIXNONBINARYVARS
#define DEFAULT_SYMFIXNONBINARYVARS FALSE |
Whether all non-binary variables shall be not affected by symmetries if OF is active?
Definition at line 182 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_ONLYBINARYSYMMETRY
#define DEFAULT_ONLYBINARYSYMMETRY TRUE |
Is only symmetry on binary variables used?
Definition at line 183 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_CONSSADDLP
#define DEFAULT_CONSSADDLP TRUE |
Should the symmetry breaking constraints be added to the LP?
Definition at line 186 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_ADDSYMRESACKS
#define DEFAULT_ADDSYMRESACKS FALSE |
Add inequalities for symresacks for each generator?
Definition at line 187 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_DETECTORBITOPES
#define DEFAULT_DETECTORBITOPES TRUE |
Should we check whether the components of the symmetry group can be handled by orbitopes?
Definition at line 188 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_DETECTSUBGROUPS
#define DEFAULT_DETECTSUBGROUPS TRUE |
Should we try to detect orbitopes in subgroups of the symmetry group?
Definition at line 189 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_ADDWEAKSBCS
#define DEFAULT_ADDWEAKSBCS TRUE |
Should we add weak SBCs for enclosing orbit of symmetric subgroups?
Definition at line 190 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_ADDSTRONGSBCS
#define DEFAULT_ADDSTRONGSBCS FALSE |
Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used?
Definition at line 191 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_ADDCONSSTIMING
#define DEFAULT_ADDCONSSTIMING 2 |
timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)
Definition at line 192 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_MAXNCONSSSUBGROUP
#define DEFAULT_MAXNCONSSSUBGROUP 500000 |
Maximum number of constraints up to which subgroup structures are detected
Definition at line 193 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_USEDYNAMICPROP
#define DEFAULT_USEDYNAMICPROP TRUE |
whether dynamic propagation should be used for full orbitopes
Definition at line 194 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_PREFERLESSROWS
#define DEFAULT_PREFERLESSROWS TRUE |
Shall orbitopes with less rows be preferred in detection?
Definition at line 195 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_OFSYMCOMPTIMING
#define DEFAULT_OFSYMCOMPTIMING 2 |
timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)
Definition at line 198 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_PERFORMPRESOLVING
#define DEFAULT_PERFORMPRESOLVING FALSE |
Run orbital fixing during presolving?
Definition at line 199 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_RECOMPUTERESTART
#define DEFAULT_RECOMPUTERESTART 0 |
Recompute symmetries after a restart has occurred? (0 = never)
Definition at line 200 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_SSTTIEBREAKRULE
#define DEFAULT_SSTTIEBREAKRULE 1 |
index of tie break rule for selecting orbit for Schreier Sims constraints?
Definition at line 203 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_SSTLEADERRULE
#define DEFAULT_SSTLEADERRULE 0 |
index of rule for selecting leader variables for Schreier Sims constraints?
Definition at line 204 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_SSTLEADERVARTYPE
#define DEFAULT_SSTLEADERVARTYPE 14 |
bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous); if multiple types are allowed, take the one with most affected vars
Definition at line 205 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_ADDCONFLICTCUTS
#define DEFAULT_ADDCONFLICTCUTS TRUE |
Should Schreier Sims constraints be added if we use a conflict based rule?
Definition at line 208 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_SSTADDCUTS
#define DEFAULT_SSTADDCUTS TRUE |
Should Schreier Sims constraints be added?
Definition at line 209 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ DEFAULT_SSTMIXEDCOMPONENTS
#define DEFAULT_SSTMIXEDCOMPONENTS TRUE |
Should Schreier Sims constraints be added if a symmetry component contains variables of different types?
Definition at line 210 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ EVENTHDLR_SYMMETRY_NAME
#define EVENTHDLR_SYMMETRY_NAME "symmetry" |
Definition at line 213 of file prop_symmetry.c.
Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludePropSymmetry().
◆ EVENTHDLR_SYMMETRY_DESC
#define EVENTHDLR_SYMMETRY_DESC "filter global variable fixing event handler for orbital fixing" |
Definition at line 214 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ TABLE_NAME_ORBITALFIXING
#define TABLE_NAME_ORBITALFIXING "orbitalfixing" |
Definition at line 217 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ TABLE_DESC_ORBITALFIXING
#define TABLE_DESC_ORBITALFIXING "orbital fixing statistics" |
Definition at line 218 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ TABLE_POSITION_ORBITALFIXING
#define TABLE_POSITION_ORBITALFIXING 7001 |
the position of the statistics table
Definition at line 219 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ TABLE_EARLIEST_ORBITALFIXING
#define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING |
output of the statistics table is only printed from this stage onwards
Definition at line 220 of file prop_symmetry.c.
Referenced by SCIPincludePropSymmetry().
◆ MAXGENNUMERATOR
#define MAXGENNUMERATOR 64000000 |
determine maximal number of generators by dividing this number by the number of variables
Definition at line 224 of file prop_symmetry.c.
Referenced by determineSymmetry().
◆ SCIP_SPECIALVAL
#define SCIP_SPECIALVAL 1.12345678912345e+19 |
special floating point value for handling zeros in bound disjunctions
Definition at line 225 of file prop_symmetry.c.
Referenced by computeSymmetryGroup().
◆ COMPRESSNVARSLB
#define COMPRESSNVARSLB 25000 |
lower bound on the number of variables above which compression could be performed
Definition at line 226 of file prop_symmetry.c.
Referenced by setSymmetryData().
◆ ISSYMRETOPESACTIVE
#define ISSYMRETOPESACTIVE | ( | x | ) | (((unsigned) x & SYM_HANDLETYPE_SYMBREAK) != 0) |
Definition at line 229 of file prop_symmetry.c.
Referenced by setSymmetryMethodEnabledValues().
◆ ISORBITALFIXINGACTIVE
#define ISORBITALFIXINGACTIVE | ( | x | ) | (((unsigned) x & SYM_HANDLETYPE_ORBITALFIXING) != 0) |
Definition at line 230 of file prop_symmetry.c.
Referenced by freeSymmetryData(), and setSymmetryMethodEnabledValues().
◆ ISSSTACTIVE
#define ISSSTACTIVE | ( | x | ) | (((unsigned) x & SYM_HANDLETYPE_SST) != 0) |
Definition at line 231 of file prop_symmetry.c.
Referenced by setSymmetryMethodEnabledValues().
◆ ISSSTBINACTIVE
#define ISSSTBINACTIVE | ( | x | ) | (((unsigned) x & SCIP_SSTTYPE_BINARY) != 0) |
Definition at line 233 of file prop_symmetry.c.
Referenced by addSSTConss(), and addSymresackConss().
◆ ISSSTINTACTIVE
#define ISSSTINTACTIVE | ( | x | ) | (((unsigned) x & SCIP_SSTTYPE_INTEGER) != 0) |
Definition at line 234 of file prop_symmetry.c.
Referenced by addSSTConss(), addSymresackConss(), and determineSymmetry().
◆ ISSSTIMPLINTACTIVE
#define ISSSTIMPLINTACTIVE | ( | x | ) | (((unsigned) x & SCIP_SSTTYPE_IMPLINT) != 0) |
Definition at line 235 of file prop_symmetry.c.
Referenced by addSSTConss(), addSymresackConss(), and determineSymmetry().
◆ ISSSTCONTACTIVE
#define ISSSTCONTACTIVE | ( | x | ) | (((unsigned) x & SCIP_SSTTYPE_CONTINUOUS) != 0) |
Definition at line 236 of file prop_symmetry.c.
Referenced by addSSTConss(), addSymresackConss(), and determineSymmetry().
Typedef Documentation
◆ SCIP_NODEDATA
typedef struct SCIP_NodeData SCIP_NODEDATA |
Definition at line 363 of file prop_symmetry.c.
◆ SYM_SORTRHSTYPE
typedef struct SYM_Sortrhstype SYM_SORTRHSTYPE |
Definition at line 559 of file prop_symmetry.c.
◆ SYM_SORTGRAPHCOMPVARS
typedef struct SYM_Sortgraphcompvars SYM_SORTGRAPHCOMPVARS |
Definition at line 567 of file prop_symmetry.c.
Function Documentation
◆ SCIP_DECL_EVENTEXEC()
|
static |
exec the event handler for handling global variable bound changes (necessary for orbital fixing)
Global variable fixings during the solving process might arise because parts of the tree are pruned or if certain preprocessing steps are performed that do not correspond to strict setting algorithms. Since these fixings might be caused by or be in conflict with orbital fixing, they can be in conflict with the symmetry handling decisions of orbital fixing in the part of the tree that is not pruned. Thus, we have to take global fixings into account when filtering out symmetries.
Definition at line 379 of file prop_symmetry.c.
References EVENTHDLR_SYMMETRY_NAME, NULL, SCIP_DECL_TABLEOUTPUT(), SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPABORT, SCIPdebugMsg, SCIPerrorMessage, SCIPeventGetNewbound(), SCIPeventGetOldbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetName(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPisEQ(), SCIPvarGetName(), SCIPvarGetType(), and TRUE.
◆ SCIP_DECL_TABLEOUTPUT()
|
static |
output method of orbital fixing propagator statistics table to output file stream 'file'
Definition at line 455 of file prop_symmetry.c.
References NULL, SCIP_DECL_TABLEFREE(), SCIP_OKAY, SCIP_VERBLEVEL_MINIMAL, SCIPtableGetData(), and SCIPverbMessage().
Referenced by SCIP_DECL_EVENTEXEC().
◆ SCIP_DECL_TABLEFREE()
|
static |
destructor of statistics table to free user data (called when SCIP is exiting)
Definition at line 479 of file prop_symmetry.c.
References NULL, SCIP_DECL_HASHGETKEY(), SCIP_OKAY, SCIPfreeBlockMemory, and SCIPtableGetData().
Referenced by SCIP_DECL_TABLEOUTPUT().
◆ SCIP_DECL_HASHGETKEY()
|
static |
gets the key of the given element
Definition at line 498 of file prop_symmetry.c.
References SCIP_DECL_HASHKEYEQ().
Referenced by SCIP_DECL_TABLEFREE().
◆ SCIP_DECL_HASHKEYEQ()
|
static |
returns TRUE iff both keys are equal
Compare the types of two variables according to objective, lower and upper bound, variable type, and column sparsity.
Definition at line 508 of file prop_symmetry.c.
References FALSE, SYM_Vartype::lb, SYM_Vartype::nconss, SYM_Vartype::obj, SCIP_DECL_HASHKEYVAL(), SCIPisEQ(), TRUE, SYM_Vartype::type, and SYM_Vartype::ub.
Referenced by SCIP_DECL_HASHGETKEY().
◆ SCIP_DECL_HASHKEYVAL()
|
static |
returns the hash value of the key
Definition at line 543 of file prop_symmetry.c.
References SYM_Vartype::lb, SYM_Vartype::nconss, SYM_Vartype::obj, SCIPhashFour, SCIPrealHashCode(), and SYM_Vartype::ub.
Referenced by SCIP_DECL_HASHKEYEQ().
◆ SCIP_DECL_SORTINDCOMP() [1/3]
|
static |
sorts rhs types - first by sense, then by value
Due to numerical issues, we first sort by sense, then by value.
result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value
0: ind2 comes after (is worse than) ind2
Definition at line 579 of file prop_symmetry.c.
References SCIP_Real, SYM_Sortrhstype::senses, and SYM_Sortrhstype::vals.
Referenced by SCIP_DECL_SORTINDCOMP().
◆ SCIP_DECL_SORTINDCOMP() [2/3]
|
static |
sorts matrix coefficients
result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value
0: ind2 comes after (is worse than) ind2
Definition at line 613 of file prop_symmetry.c.
References SCIP_DECL_SORTINDCOMP(), and SCIP_Real.
◆ SCIP_DECL_SORTINDCOMP() [3/3]
|
static |
sorts variable indices according to their corresponding component in the graph
Variables are sorted first by the color of their component and then by the component index.
result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value
0: ind2 comes after (is worse than) ind2
Definition at line 640 of file prop_symmetry.c.
References checkSymmetryDataFree(), SYM_Sortgraphcompvars::colors, SYM_Sortgraphcompvars::components, and SCIP_Bool.
◆ checkSymmetryDataFree()
|
static |
checks that symmetry data is all freed
- Parameters
-
propdata propagator data
Definition at line 668 of file prop_symmetry.c.
References FALSE, isLeadervartypeCompatible(), NULL, SCIP_Bool, and TRUE.
Referenced by determineSymmetry(), freeSymmetryData(), and SCIP_DECL_SORTINDCOMP().
◆ isLeadervartypeCompatible()
checks whether a variable has a type compatible with the leader vartype
- Parameters
-
var variable to check leadervartype bit set encoding possible leader variable types
Definition at line 717 of file prop_symmetry.c.
References NULL, SCIP_Bool, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), and setSymmetryMethodEnabledValues().
Referenced by checkSymmetryDataFree(), and determineSymmetry().
◆ setSymmetryMethodEnabledValues()
|
static |
sets in propdata which symmetry handling methods are active
- Parameters
-
propdata propagator data
Definition at line 746 of file prop_symmetry.c.
References FALSE, freeSymmetryData(), ISORBITALFIXINGACTIVE, ISSSTACTIVE, ISSYMRETOPESACTIVE, NULL, SCIP_OKAY, and TRUE.
Referenced by isLeadervartypeCompatible(), SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPINITPRE().
◆ freeSymmetryData()
|
static |
frees symmetry data
- Parameters
-
scip SCIP pointer propdata propagator data
Definition at line 773 of file prop_symmetry.c.
References checkSymmetryDataFree(), FALSE, ISORBITALFIXINGACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_SSTTYPE_BINARY, SCIP_VARTYPE_BINARY, SCIPdropVarEvent(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPhashmapFree(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPvarGetType(), and SymmetryFixVar().
Referenced by determineSymmetry(), SCIP_DECL_PROPEXIT(), setSymmetryMethodEnabledValues(), and tryAddSymmetryHandlingConss().
◆ SymmetryFixVar()
determines whether variable should be fixed by permutations
- Parameters
-
fixedtype bitset of variable types that should be fixed var variable to be considered
Definition at line 1004 of file prop_symmetry.c.
References FALSE, getActiveVariables(), SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.
Referenced by checkSymmetriesAreSymmetries(), computeSymmetryGroup(), and freeSymmetryData().
◆ getActiveVariables()
|
static |
Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.
- Note
constant
needs to be initialized!
- Parameters
-
scip SCIP data structure vars pointer to vars array to get active variables for scalars pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c nvars pointer to number of variables and values in vars and vals array constant pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c transformed transformed constraint?
Definition at line 1025 of file prop_symmetry.c.
References collectCoefficients(), NULL, scalars, SCIP_CALL, SCIP_OKAY, SCIPgetProbvarLinearSum(), SCIPreallocBufferArray, SCIPvarGetOrigvarSum(), and TRUE.
Referenced by collectCoefficients(), and SymmetryFixVar().
◆ collectCoefficients()
|
static |
fills in matrix elements into coefficient arrays
- Parameters
-
scip SCIP data structure doubleequations Double equations to positive/negative version? linvars array of linear variables linvals array of linear coefficients values (or NULL if all linear coefficient values are 1) nlinvars number of linear variables lhs left hand side rhs right hand side istransformed whether the constraint is transformed rhssense identifier of constraint type matrixdata matrix data to be filled in nconssforvar pointer to array to store for each var the number of conss
Definition at line 1071 of file prop_symmetry.c.
References checkSymmetriesAreSymmetries(), FALSE, getActiveVariables(), SYM_Matrixdata::matcoef, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::nmaxmatcoef, SYM_Matrixdata::nrhscoef, NULL, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhsidx, SYM_Matrixdata::rhssense, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPisEQ(), SCIPisInfinity(), SCIPisPositive(), SCIPreallocBlockMemoryArray, SCIPvarGetProbindex(), SYM_SENSE_BOUNDIS_TYPE_2, SYM_SENSE_EQUATION, SYM_SENSE_INEQUALITY, SYM_SENSE_XOR, and TRUE.
Referenced by computeSymmetryGroup(), and getActiveVariables().
◆ checkSymmetriesAreSymmetries()
|
static |
checks whether given permutations form a symmetry of a MIP
We need the matrix and rhs in the original order in order to speed up the comparison process. The matrix is needed in the right order to easily check rows. The rhs is used because of cache effects.
- Parameters
-
scip SCIP data structure fixedtype variable types that must be fixed by symmetries matrixdata matrix data nperms number of permutations perms permutations
Definition at line 1298 of file prop_symmetry.c.
References FALSE, getNSymhandableConss(), SYM_Matrixdata::matcoef, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, NULL, SYM_Matrixdata::permvars, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhssense, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPcompareExpr(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPdebugMsg, SCIPerrorMessage, SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetConsCopy(), SCIPgetConsNVars(), SCIPgetConsVars(), SCIPgetExprNonlinear(), SCIPgetLhsNonlinear(), SCIPgetRhsNonlinear(), SCIPhashmapCreate(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPhashmapRemoveAll(), SCIPisEQ(), SCIPisZero(), SCIPreleaseCons(), SCIPreleaseExpr(), SCIPsimplifyExpr(), SCIPvarGetProbindex(), SymmetryFixVar(), and TRUE.
Referenced by collectCoefficients(), and computeSymmetryGroup().
◆ getNSymhandableConss()
|
static |
returns the number of active constraints that can be handled by symmetry
- Parameters
-
scip SCIP instance conshdlr_nonlinear nonlinear constraint handler, if included
Definition at line 1556 of file prop_symmetry.c.
References hasNonlinearConstraints(), NULL, SCIP_Bool, SCIPconshdlrGetNActiveConss(), and SCIPfindConshdlr().
Referenced by checkSymmetriesAreSymmetries(), computeSymmetryGroup(), and determineSymmetry().
◆ hasNonlinearConstraints()
|
static |
returns whether there are any active nonlinear constraints
- Parameters
-
propdata propagator data
Definition at line 1594 of file prop_symmetry.c.
References NULL, SCIPconshdlrGetNActiveConss(), and setSymmetryData().
Referenced by getNSymhandableConss(), propagateOrbitalFixing(), SCIP_DECL_PROPEXITPRE(), SCIP_DECL_PROPINITPRE(), SCIP_DECL_PROPPRESOL(), and tryAddSymmetryHandlingConss().
◆ setSymmetryData()
|
static |
set symmetry data
- Parameters
-
scip SCIP pointer vars vars present at time of symmetry computation nvars number of vars present at time of symmetry computation nbinvars number of binary vars present at time of symmetry computation permvars pointer to permvars array npermvars pointer to store number of permvars nbinpermvars pointer to store number of binary permvars perms permutations matrix (nperms x nvars) nperms number of permutations nmovedvars pointer to store number of vars affected by symmetry (if usecompression) or NULL binvaraffected pointer to store whether a binary variable is affected by symmetry usecompression whether symmetry data shall be compressed compressthreshold if percentage of moved vars is at most threshold, compression is done compressed pointer to store whether compression has been performed
Definition at line 1605 of file prop_symmetry.c.
References COMPRESSNVARSLB, computeSymmetryGroup(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPisGE(), SCIPisLE(), SCIPreallocBlockMemoryArray, SCIPvarGetType(), and TRUE.
Referenced by computeSymmetryGroup(), and hasNonlinearConstraints().
◆ computeSymmetryGroup()
|
static |
computes symmetry group of a MIP
- Parameters
-
scip SCIP pointer doubleequations Double equations to positive/negative version? compresssymmetries Should non-affected variables be removed from permutation to save memory? compressthreshold Compression is used if percentage of moved vars is at most the threshold. maxgenerators maximal number of generators constructed (= 0 if unlimited) fixedtype variable types that must be fixed by symmetries local Use local variable bounds? checksymmetries Should all symmetries be checked after computation? usecolumnsparsity Should the number of conss a variable is contained in be exploited in symmetry detection? conshdlr_nonlinear Nonlinear constraint handler, if included npermvars pointer to store number of variables for permutations nbinpermvars pointer to store number of binary variables for permutations permvars pointer to store variables on which permutations act nperms pointer to store number of permutations nmaxperms pointer to store maximal number of permutations (needed for freeing storage) perms pointer to store permutation generators as (nperms x npermvars) matrix log10groupsize pointer to store log10 of size of group nmovedvars pointer to store number of moved vars isnonlinvar pointer to store which variables appear nonlinearly binvaraffected pointer to store wether a binary variable is affected by symmetry compressed pointer to store whether compression has been performed success pointer to store whether symmetry computation was successful
Definition at line 1736 of file prop_symmetry.c.
References checkSymmetriesAreSymmetries(), collectCoefficients(), SYM_Vartype::color, determineSymmetry(), FALSE, getNSymhandableConss(), SYM_Vartype::lb, SYM_Matrixdata::matcoef, SYM_Matrixdata::matcoefcolors, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, MAX, SYM_Vartype::nconss, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::nmaxmatcoef, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, SYM_Sortrhstype::nrhscoef, NULL, SYM_Exprdata::nuniquecoefs, SYM_Exprdata::nuniqueconstants, SYM_Matrixdata::nuniquemat, SYM_Exprdata::nuniqueoperators, SYM_Matrixdata::nuniquerhs, SYM_Matrixdata::nuniquevars, SYM_Vartype::obj, SYM_Matrixdata::permvarcolors, SYM_Matrixdata::permvars, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhscoefcolors, SYM_Matrixdata::rhsidx, SYM_Matrixdata::rhssense, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_ERROR, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_INVALID, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIP_SPECIALVAL, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_SOLVING, SCIP_VERBLEVEL_HIGH, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemoryArray, SCIPblkmem(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetNActiveConss(), SCIPconshdlrGetName(), SCIPconsIsActive(), SCIPconsIsConflict(), SCIPconsIsTransformed(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPexprGetNChildren(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterGetParentDFS(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeExpriter(), SCIPgetBinvarsLinking(), SCIPgetBoundsBounddisjunction(), SCIPgetBoundtypesBounddisjunction(), SCIPgetCapacityKnapsack(), SCIPgetConss(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprNonlinear(), SCIPgetIntVarXor(), SCIPgetLhsLinear(), SCIPgetLhsVarbound(), SCIPgetLinkvarLinking(), SCIPgetNActiveConss(), SCIPgetNBinVars(), SCIPgetNConss(), SCIPgetNFixedVars(), SCIPgetNVars(), SCIPgetNVarsAnd(), SCIPgetNVarsBounddisjunction(), SCIPgetNVarsKnapsack(), SCIPgetNVarsLinear(), SCIPgetNVarsLogicor(), SCIPgetNVarsOr(), SCIPgetNVarsSetppc(), SCIPgetNVarsXor(), SCIPgetResultantAnd(), SCIPgetResultantOr(), SCIPgetRhsLinear(), SCIPgetRhsVarbound(), SCIPgetRhsXor(), SCIPgetStage(), SCIPgetTypeSetppc(), SCIPgetValsLinear(), SCIPgetValsLinking(), SCIPgetVarExprVar(), SCIPgetVars(), SCIPgetVarsAnd(), SCIPgetVarsBounddisjunction(), SCIPgetVarsKnapsack(), SCIPgetVarsLinear(), SCIPgetVarsLogicor(), SCIPgetVarsOr(), SCIPgetVarsSetppc(), SCIPgetVarsXor(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPgetWeightsKnapsack(), SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetInsert(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPinfinity(), SCIPisEQ(), SCIPisExprSum(), SCIPisExprValue(), SCIPisExprVar(), SCIPisStopped(), SCIPisZero(), SCIPsort(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPverbMessage(), SYM_Sortrhstype::senses, setSymmetryData(), SYM_SENSE_AND, SYM_SENSE_BOUNDIS_TYPE_1, SYM_SENSE_BOUNDIS_TYPE_2, SYM_SENSE_EQUATION, SYM_SENSE_INEQUALITY, SYM_SENSE_OR, SYM_SENSE_UNKOWN, SYM_SENSE_XOR, SYMcanComputeSymmetry(), SYMcomputeSymmetryGenerators(), SymmetryFixVar(), TRUE, SYM_Vartype::type, SYM_Vartype::ub, and SYM_Sortrhstype::vals.
Referenced by determineSymmetry(), and setSymmetryData().
◆ determineSymmetry()
|
static |
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 2551 of file prop_symmetry.c.
References checkSymmetryDataFree(), checkTwoCyclePermsAreOrbitope(), computeSymmetryGroup(), FALSE, freeSymmetryData(), getNSymhandableConss(), isLeadervartypeCompatible(), ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, MAXGENNUMERATOR, NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_SSTTYPE_BINARY, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIP_VERBLEVEL_HIGH, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcaptureVar(), SCIPcatchVarEvent(), SCIPcomputeComponentsSym(), SCIPdetermineNVarsAffectedSym(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetNActiveBenders(), SCIPgetNActiveConss(), SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNRuns(), SCIPgetNVars(), SCIPgetSolvingTime(), SCIPhashmapCreate(), SCIPhashmapInsertInt(), SCIPisReoptEnabled(), SCIPmarkDoNotMultaggrVar(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarIsBinary(), SCIPverbMessage(), SCIPwarningMessage(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, SYMcanComputeSymmetry(), and TRUE.
Referenced by computeSymmetryGroup(), propagateOrbitalFixing(), SCIP_DECL_PROPEXITPRE(), SCIP_DECL_PROPINITPRE(), SCIP_DECL_PROPPRESOL(), and tryAddSymmetryHandlingConss().
◆ checkTwoCyclePermsAreOrbitope()
|
static |
Checks whether given set of 2-cycle permutations forms an orbitope and if so, builds the variable index matrix.
If activevars
== NULL, then the function assumes all permutations of the component are active and therefore all moved vars are considered.
We need to keep track of the number of generatored columns, because we might not be able to detect all orbitopes. For example (1,2), (2,3), (3,4), (3,5) defines the symmetric group on {1,2,3,4,5}, but the generators we expect in our construction need shape (1,2), (2,3), (3,4), (4,5).
- Precondition
orbitopevaridx
has to be an initialized 2D array of sizentwocycles
xnperms
-
columnorder
has to be an initialized array of size nperms -
nusedelems
has to be an initialized array of size npermvars
- Parameters
-
scip SCIP instance permvars array of all permutation variables npermvars number of permutation variables perms array of all permutations of the symmety group activeperms indices of the relevant permutations in perms ntwocycles number of 2-cycles in the permutations nactiveperms number of active permutations orbitopevaridx pointer to store variable index matrix columnorder pointer to store column order nusedelems pointer to store how often each element was used nusedcols pointer to store numer of columns used in orbitope (or NULL) rowisbinary pointer to store which rows are binary (or NULL) isorbitope buffer to store result activevars bitset to store whether a variable is active (or NULL)
Definition at line 3047 of file prop_symmetry.c.
References chooseOrderOfGenerators(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocClearBufferArray, SCIPextendSubOrbitope(), SCIPfreeBufferArray, SCIPvarIsBinary(), and TRUE.
Referenced by addOrbitopeSubgroup(), detectOrbitopes(), and determineSymmetry().
◆ chooseOrderOfGenerators()
|
static |
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 3232 of file prop_symmetry.c.
References buildSubgroupGraph(), SYM_Sortgraphcompvars::components, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisInvolutionPerm(), and SCIPsortIntInt().
Referenced by checkTwoCyclePermsAreOrbitope(), and detectAndHandleSubgroups().
◆ buildSubgroupGraph()
|
static |
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 3310 of file prop_symmetry.c.
References addOrbitopeSubgroup(), SYM_Sortgraphcompvars::colors, SYM_Sortgraphcompvars::components, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetGetComponentCount(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPfreeDisjointset(), SCIPreallocBufferArray, SCIPsort(), and TRUE.
Referenced by chooseOrderOfGenerators(), and detectAndHandleSubgroups().
◆ addOrbitopeSubgroup()
|
static |
adds an orbitope constraint for a suitable color of the subgroup graph
- Parameters
-
scip SCIP instance propdata pointer to data of symmetry propagator usedperms array of the permutations that build the orbitope nusedperms number of permutations in usedperms compcolorbegins array indicating where a new graphcolor begins graphcompbegins array indicating where a new graphcomponent begins graphcomponents array of all variable indices sorted by color and comp graphcoloridx index of the graph color nrows number of rows in the orbitope ncols number of columns in the orbitope firstvaridx buffer to store the index of the largest variable (or NULL) compidxfirstrow buffer to store the comp index for the first row (or NULL) lexorder pointer to array storing lexicographic order defined by sub orbitopes nvarslexorder number of variables in lexicographic order maxnvarslexorder maximum number of variables in lexicographic order mayinteract whether orbitope's symmetries might interact with other symmetries success whether the orbitpe could be added
Definition at line 3577 of file prop_symmetry.c.
References addStrongSBCsSubgroup(), checkTwoCyclePermsAreOrbitope(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_Shortbool, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateConsOrbitope(), SCIPfreeBufferArray, SCIPgenerateOrbitopeVarsMatrix(), SCIPsnprintf(), SCIPvarIsBinary(), and TRUE.
Referenced by buildSubgroupGraph(), and detectAndHandleSubgroups().
◆ addStrongSBCsSubgroup()
|
static |
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 3796 of file prop_symmetry.c.
References addWeakSBCsSubgroup(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPcreateConsLinear(), SCIPinfinity(), SCIPinfoMessage(), SCIPprintCons(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPvarGetName(), and TRUE.
Referenced by addOrbitopeSubgroup(), and detectAndHandleSubgroups().
◆ addWeakSBCsSubgroup()
|
static |
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 3890 of file prop_symmetry.c.
References adaptSymmetryDataSST(), FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPallocClearBufferArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPcomputeOrbitVar(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapInsertInt(), SCIPinfinity(), SCIPinfoMessage(), SCIPprintCons(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPvarGetName(), and TRUE.
Referenced by addStrongSBCsSubgroup(), and detectAndHandleSubgroups().
◆ adaptSymmetryDataSST()
|
static |
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 4135 of file prop_symmetry.c.
References getNOrbitopesInComp(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.
Referenced by addSymresackConss(), addWeakSBCsSubgroup(), 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 4217 of file prop_symmetry.c.
References detectAndHandleSubgroups(), FALSE, NULL, SCIP_Bool, SCIP_Real, SCIPvarIsBinary(), and TRUE.
Referenced by adaptSymmetryDataSST(), and 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
Definition at line 4300 of file prop_symmetry.c.
References adaptSymmetryDataSST(), addOrbitopeSubgroup(), addStrongSBCsSubgroup(), addWeakSBCsSubgroup(), buildSubgroupGraph(), chooseOrderOfGenerators(), FALSE, getNOrbitopesInComp(), NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Shortbool, SCIP_VERBLEVEL_HIGH, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNConss(), SCIPsnprintf(), SCIPsortOrbitope(), SCIPvarGetName(), SCIPvarIsBinary(), SCIPvarIsIntegral(), SCIPverbMessage(), SYM_HANDLETYPE_SYMBREAK, and TRUE.
Referenced by getNOrbitopesInComp(), and tryAddSymmetryHandlingConss().
◆ SCIPsortOrbitope()
|
static |
sorts orbitope vars matrix such that rows are sorted increasingly w.r.t. minimum variable index in row; columns are sorted such that first row is sorted increasingly w.r.t. variable indices
- Parameters
-
scip SCIP instance orbitopevaridx variable index matrix of orbitope vars variable matrix of orbitope nrows number of binary rows of orbitope ncols number of columns of orbitope
Definition at line 4821 of file prop_symmetry.c.
References detectOrbitopes(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortIntIntPtr(), and SCIPsortIntPtr().
Referenced by detectAndHandleSubgroups(), and detectOrbitopes().
◆ detectOrbitopes()
|
static |
checks whether components of the symmetry group can be completely handled by orbitopes
- Parameters
-
scip SCIP instance propdata pointer to data of symmetry propagator components array containing components of symmetry group componentbegins array containing begin positions of components in components array ncomponents number of components
Definition at line 4903 of file prop_symmetry.c.
References checkTwoCyclePermsAreOrbitope(), SYM_Sortgraphcompvars::components, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_Shortbool, SCIPaddCons(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateConsOrbitope(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgenerateOrbitopeVarsMatrix(), SCIPisInvolutionPerm(), SCIPsnprintf(), SCIPsortOrbitope(), SYM_HANDLETYPE_SYMBREAK, TRUE, and updateSymInfoConflictGraphSST().
Referenced by SCIPsortOrbitope(), and tryAddSymmetryHandlingConss().
◆ updateSymInfoConflictGraphSST()
|
static |
update symmetry information of conflict graph
- Parameters
-
scip SCIP instance conflictgraph conflict graph graphvars variables encoded in conflict graph (either all vars or permvars) ngraphvars number of nodes/vars in conflict graph permvars variables considered in permutations npermvars number of permvars onlypermvars whether conflict graph contains only permvars varmap map from graphvar to node label in conflict graph (or NULL if onlypermvars == TRUE) orbits array of non-trivial orbits orbitbegins array containing begin positions of new orbits in orbits array norbits number of non-trivial orbits
Definition at line 5108 of file prop_symmetry.c.
References createConflictGraphSST(), nodedata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPdigraphSetNodeData(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), and TRUE.
Referenced by addSSTConss(), and detectOrbitopes().
◆ createConflictGraphSST()
|
static |
create conflict graph either for symmetric or for all variables
This routine just creates the graph, but does not add (symmetry) information to its nodes. This has to be done separately by the routine updateSymInfoConflictGraphSST().
- Parameters
-
scip SCIP instance conflictgraph pointer to store conflict graph graphvars variables encoded in conflict graph ngraphvars number of vars encoded in conflict graph onlypermvars whether conflict graph contains only permvars permvarmap map of variables to indices in permvars array (or NULL) success pointer to store whether conflict graph could be created successfully
Definition at line 5253 of file prop_symmetry.c.
References FALSE, freeConflictGraphSST(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_SETPPCTYPE_COVERING, SCIPconsGetName(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateDigraph(), SCIPdebugMsg, SCIPdigraphAddArcSafe(), SCIPfindConshdlr(), SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), SCIPhashmapGetImageInt(), SCIPvarGetProbindex(), and TRUE.
Referenced by addSSTConss(), and updateSymInfoConflictGraphSST().
◆ freeConflictGraphSST()
|
static |
frees conflict graph
- Parameters
-
scip SCIP instance conflictgraph conflict graph nnodes number of nodes in conflict graph
Definition at line 5377 of file prop_symmetry.c.
References addSymresackConss(), nnodes, nodedata, NULL, SCIP_OKAY, SCIPdigraphFree(), SCIPdigraphGetNodeData(), and SCIPfreeBlockMemory.
Referenced by addSSTConss(), and createConflictGraphSST().
◆ addSymresackConss()
|
static |
adds symresack constraints
- Parameters
-
scip SCIP instance prop symmetry breaking propagator components array containing components of symmetry group componentbegins array containing begin positions of components in components array ncomponents number of components
Definition at line 5414 of file prop_symmetry.c.
References adaptSymmetryDataSST(), addSSTConssOrbitAndUpdateSST(), SYM_Sortgraphcompvars::components, FALSE, ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPpropGetData(), SCIPsnprintf(), SYM_HANDLETYPE_ORBITALFIXING, SYM_HANDLETYPE_SST, SYM_HANDLETYPE_SYMBREAK, and TRUE.
Referenced by freeConflictGraphSST(), and tryAddSymmetryHandlingConss().
◆ addSSTConssOrbitAndUpdateSST()
|
static |
add Schreier Sims constraints for a specific orbit and update Schreier Sims table
- Parameters
-
scip SCIP instance conflictgraph conflict graph or NULL if useconflictgraph == FALSE propdata data of symmetry propagator permvars permvars array orbits symmetry orbits orbitbegins array storing begin position for each orbit orbitidx index of orbit for Schreier Sims constraints orbitleaderidx index of leader variable for Schreier Sims constraints orbitvarinconflict indicator whether orbitvar is in conflict with orbit leader norbitvarinconflict number of variables in conflict with orbit leader nchgbds pointer to store number of bound changes (or NULL) useconflictgraph whether conflict graph shall be used
Definition at line 5578 of file prop_symmetry.c.
References FALSE, nodedata, NULL, SCIP_Bool, SCIP_CALL, SCIP_LEADERRULE_MAXCONFLICTS, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPchgVarUb(), SCIPcreateConsLinear(), SCIPdigraphGetNodeData(), SCIPinfinity(), SCIPreallocBlockMemoryArray, SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsBinary(), selectOrbitLeaderSSTConss(), and TRUE.
Referenced by addSSTConss(), and addSymresackConss().
◆ selectOrbitLeaderSSTConss()
|
static |
selection rule of next orbit/leader in orbit for Schreier Sims constraints
- Parameters
-
scip SCIP instance conflictgraph conflict graph or NULL if useconflictgraph == FALSE graphvars variables encoded in conflict graph ngraphvars number of variables encoded in conflict graph varmap map from variable to node label in conflict graph or NULL if useconflictgraph == FALSE permvars vars encoded in a permutation npermvars number of vars in a permutation orbits orbits of stabilizer subgroup orbitbegins array storing the begin position of each orbit in orbits norbits number of orbits leaderrule rule to select leader tiebreakrule tie break rule to select leader leadervartype variable type of leader orbitidx pointer to index of selected orbit leaderidx pointer to leader in orbit orbitvarinconflict array to store whether a var in the orbit is conflicting with leader norbitvarinconflict pointer to store number of vars in the orbit in conflict with leader useconflictgraph whether conflict graph shall be used success pointer to store whether orbit cut be selected successfully
Definition at line 5738 of file prop_symmetry.c.
References addSSTConss(), FALSE, nodedata, NULL, SCIP_LEADERRULE_FIRSTINORBIT, SCIP_LEADERRULE_LASTINORBIT, SCIP_LEADERRULE_MAXCONFLICTS, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXORBIT, SCIP_LEADERTIEBREAKRULE_MINORBIT, SCIP_OKAY, SCIPdigraphGetNNodes(), SCIPdigraphGetNodeData(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPhashmapGetImageInt(), SCIPvarGetProbindex(), SCIPvarGetType(), and TRUE.
Referenced by addSSTConss(), and addSSTConssOrbitAndUpdateSST().
◆ addSSTConss()
|
static |
add Schreier Sims constraints to the problem
- Parameters
-
scip SCIP instance propdata datas of symmetry propagator nchgbds pointer to store number of bound changes (or NULL)
Definition at line 5987 of file prop_symmetry.c.
References addSSTConssOrbitAndUpdateSST(), SYM_Sortgraphcompvars::components, createConflictGraphSST(), FALSE, freeConflictGraphSST(), ISSSTBINACTIVE, ISSSTCONTACTIVE, ISSSTIMPLINTACTIVE, ISSSTINTACTIVE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LEADERRULE_FIRSTINORBIT, SCIP_LEADERRULE_MAXCONFLICTS, SCIP_LEADERRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT, SCIP_LEADERTIEBREAKRULE_MAXORBIT, SCIP_OKAY, SCIP_Shortbool, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPblkmem(), SCIPcomputeOrbitsFilterSym(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapInsertInt(), SCIPvarGetType(), selectOrbitLeaderSSTConss(), SYM_HANDLETYPE_SST, TRUE, tryAddSymmetryHandlingConss(), and updateSymInfoConflictGraphSST().
Referenced by selectOrbitLeaderSSTConss(), and tryAddSymmetryHandlingConss().
◆ tryAddSymmetryHandlingConss()
|
static |
finds problem symmetries
- Parameters
-
scip SCIP instance prop symmetry breaking propagator nchgbds pointer to store number of bound changes (or NULL) earlyterm pointer to store whether we terminated early (or NULL)
Definition at line 6310 of file prop_symmetry.c.
References addSSTConss(), addSymresackConss(), detectAndHandleSubgroups(), detectOrbitopes(), determineSymmetry(), FALSE, freeSymmetryData(), hasNonlinearConstraints(), NULL, performOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPfreeBlockMemoryArrayNull, SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPisStopped(), SCIPpropGetData(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.
Referenced by addSSTConss(), SCIP_DECL_PROPEXITPRE(), SCIP_DECL_PROPINITPRE(), and SCIP_DECL_PROPPRESOL().
◆ performOrbitalFixing()
|
static |
performs orbital fixing
Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be fixed.
- Parameters
-
scip SCIP pointer permvars variables npermvars number of variables orbits array of non-trivial orbits orbitbegins array containing begin positions of new orbits in orbits array norbits number of orbits infeasible pointer to store whether problem is infeasible nfixedzero pointer to store number of variables fixed to 0 nfixedone pointer to store number of variables fixed to 1
Definition at line 6463 of file prop_symmetry.c.
References computeBranchingVariables(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateOrbitalFixing(), and tryAddSymmetryHandlingConss().
◆ computeBranchingVariables()
|
static |
Gets branching variables on the path to root
The variables are added to bg1 and bg1list, which are prefilled with the variables globally fixed to 1.
- Parameters
-
scip SCIP pointer nvars number of variables varmap map of variables to indices in vars array bg1 bitset marking the variables globally fixed or branched to 1 bg1list array to store the variable indices globally fixed or branched to 1 nbg1 pointer to store the number of variables in bg1 and bg1list
Definition at line 6601 of file prop_symmetry.c.
References NULL, propagateOrbitalFixing(), SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPboundchgGetBoundchgtype(), SCIPboundchgGetVar(), SCIPdomchgGetBoundchg(), SCIPdomchgGetNBoundchgs(), SCIPgetCurrentNode(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPnodeGetDepth(), SCIPnodeGetDomchg(), SCIPnodeGetParent(), SCIPprintNodeRootPath(), SCIPvarGetLbLocal(), SCIPvarGetType(), and TRUE.
Referenced by performOrbitalFixing(), and propagateOrbitalFixing().
◆ propagateOrbitalFixing()
|
static |
propagates orbital fixing
- Parameters
-
scip SCIP pointer propdata data of symmetry breaking propagator infeasible pointer to store whether the node is detected to be infeasible nprop pointer to store the number of propagations
Definition at line 6693 of file prop_symmetry.c.
References SYM_Sortgraphcompvars::components, computeBranchingVariables(), determineSymmetry(), FALSE, hasNonlinearConstraints(), NULL, performOrbitalFixing(), SCIP_CALL, SCIP_DECL_PROPINITPRE(), SCIP_OKAY, SCIP_Shortbool, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPallocBufferArray, SCIPcomputeOrbitsFilterSym(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPisEQ(), SCIPvarGetLbGlobal(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.
Referenced by computeBranchingVariables(), SCIP_DECL_PROPEXEC(), and SCIP_DECL_PROPPRESOL().
◆ SCIP_DECL_PROPINITPRE()
|
static |
presolving initialization method of propagator (called when presolving is about to begin)
Definition at line 6961 of file prop_symmetry.c.
References determineSymmetry(), hasNonlinearConstraints(), NULL, SCIP_CALL, SCIP_DECL_PROPEXITPRE(), SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPdebugMsg, SCIPfindConshdlr(), SCIPgetIntParam(), SCIPpropGetData(), SCIPverbMessage(), setSymmetryMethodEnabledValues(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and tryAddSymmetryHandlingConss().
Referenced by propagateOrbitalFixing().
◆ SCIP_DECL_PROPEXITPRE()
|
static |
presolving deinitialization method of propagator (called after presolving has been finished)
Definition at line 7010 of file prop_symmetry.c.
References determineSymmetry(), hasNonlinearConstraints(), NULL, PROP_NAME, SCIP_CALL, SCIP_DECL_PROPPRESOL(), SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPdebugMsg, SCIPgetStatus(), SCIPpropGetData(), SCIPpropGetName(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and tryAddSymmetryHandlingConss().
Referenced by SCIP_DECL_PROPINITPRE().
◆ SCIP_DECL_PROPPRESOL()
|
static |
presolving method of propagator
Definition at line 7052 of file prop_symmetry.c.
References determineSymmetry(), FALSE, hasNonlinearConstraints(), NULL, PROP_NAME, propagateOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_PROPEXEC(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PROPTIMING_ALWAYS, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIPconsGetName(), SCIPdebugMsg, SCIPgetStage(), SCIPisPresolveFinished(), SCIPisStopped(), SCIPpresolCons(), SCIPpropGetData(), SYM_COMPUTETIMING_AFTERPRESOL, SYM_COMPUTETIMING_DURINGPRESOL, SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, TRUE, and tryAddSymmetryHandlingConss().
Referenced by SCIP_DECL_PROPEXITPRE().
◆ SCIP_DECL_PROPEXEC()
|
static |
execution method of propagator
Definition at line 7208 of file prop_symmetry.c.
References FALSE, NULL, propagateOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_PROPEXIT(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetIntParam(), SCIPgetStage(), SCIPinProbing(), SCIPinRepropagation(), SCIPnodeGetNumber(), SCIPpropGetData(), SCIPpropGetName(), setSymmetryMethodEnabledValues(), and TRUE.
Referenced by SCIP_DECL_PROPPRESOL().
◆ SCIP_DECL_PROPEXIT()
|
static |
deinitialization method of propagator (called before transformed problem is freed)
Definition at line 7281 of file prop_symmetry.c.
References FALSE, freeSymmetryData(), NULL, PROP_NAME, SCIP_CALL, SCIP_DECL_PROPRESPROP(), SCIP_OKAY, SCIPdebugMsg, SCIPpropGetData(), and SCIPpropGetName().
Referenced by SCIP_DECL_PROPEXEC().
◆ SCIP_DECL_PROPRESPROP()
|
static |
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 7323 of file prop_symmetry.c.
References NULL, SCIP_DECL_PROPFREE(), SCIP_DIDNOTFIND, and SCIP_OKAY.
Referenced by SCIP_DECL_PROPEXIT().
◆ SCIP_DECL_PROPFREE()
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 7335 of file prop_symmetry.c.
References NULL, PROP_NAME, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPincludePropSymmetry(), SCIPpropGetData(), and SCIPpropGetName().
Referenced by SCIP_DECL_PROPRESPROP().
◆ SCIPincludePropSymmetry()
SCIP_RETCODE SCIPincludePropSymmetry | ( | SCIP * | scip | ) |
include symmetry propagator
- Parameters
-
scip SCIP data structure
Definition at line 7359 of file prop_symmetry.c.
References DEFAULT_ADDCONFLICTCUTS, DEFAULT_ADDCONSSTIMING, DEFAULT_ADDSTRONGSBCS, DEFAULT_ADDSYMRESACKS, DEFAULT_ADDWEAKSBCS, DEFAULT_CHECKSYMMETRIES, DEFAULT_COMPRESSSYMMETRIES, DEFAULT_COMPRESSTHRESHOLD, DEFAULT_CONSSADDLP, DEFAULT_DETECTORBITOPES, DEFAULT_DETECTSUBGROUPS, DEFAULT_DISPLAYNORBITVARS, DEFAULT_DOUBLEEQUATIONS, DEFAULT_MAXGENERATORS, DEFAULT_MAXNCONSSSUBGROUP, DEFAULT_OFSYMCOMPTIMING, DEFAULT_ONLYBINARYSYMMETRY, DEFAULT_PERFORMPRESOLVING, DEFAULT_PREFERLESSROWS, DEFAULT_RECOMPUTERESTART, DEFAULT_SSTADDCUTS, DEFAULT_SSTLEADERRULE, DEFAULT_SSTLEADERVARTYPE, DEFAULT_SSTMIXEDCOMPONENTS, DEFAULT_SSTTIEBREAKRULE, DEFAULT_SYMFIXNONBINARYVARS, DEFAULT_USECOLUMNSPARSITY, DEFAULT_USEDYNAMICPROP, EVENTHDLR_SYMMETRY_DESC, EVENTHDLR_SYMMETRY_NAME, FALSE, NULL, PROP_DELAY, PROP_DESC, PROP_FREQ, PROP_NAME, PROP_PRESOL_MAXROUNDS, PROP_PRESOL_PRIORITY, PROP_PRESOLTIMING, PROP_PRIORITY, PROP_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPgetSymmetry(), SCIPincludeEventhdlrBasic(), SCIPincludeExternalCodeInformation(), SCIPincludePropBasic(), SCIPincludeTable(), SCIPsetPropExit(), SCIPsetPropExitpre(), SCIPsetPropFree(), SCIPsetPropInitpre(), SCIPsetPropPresol(), SCIPsetPropResprop(), SYMcanComputeSymmetry(), SYMsymmetryGetDesc(), SYMsymmetryGetName(), TABLE_DESC_ORBITALFIXING, TABLE_EARLIEST_ORBITALFIXING, TABLE_NAME_ORBITALFIXING, TABLE_POSITION_ORBITALFIXING, and TRUE.
Referenced by SCIP_DECL_PROPFREE(), and SCIPincludeDefaultPlugins().
◆ SCIPgetSymmetry()
SCIP_RETCODE SCIPgetSymmetry | ( | SCIP * | scip, |
int * | npermvars, | ||
SCIP_VAR *** | permvars, | ||
SCIP_HASHMAP ** | permvarmap, | ||
int * | nperms, | ||
int *** | perms, | ||
int *** | permstrans, | ||
SCIP_Real * | log10groupsize, | ||
SCIP_Bool * | binvaraffected, | ||
int ** | components, | ||
int ** | componentbegins, | ||
int ** | vartocomponent, | ||
int * | ncomponents | ||
) |
return currently available symmetry group information
- Parameters
-
scip SCIP data structure npermvars pointer to store number of variables for permutations permvars pointer to store variables on which permutations act permvarmap pointer to store hash map of permvars (or NULL) nperms pointer to store number of permutations perms pointer to store permutation generators as (nperms x npermvars) matrix (or NULL) permstrans pointer to store permutation generators as (npermvars x nperms) matrix (or NULL) log10groupsize pointer to store log10 of group size (or NULL) binvaraffected pointer to store whether binary variables are affected (or NULL) components pointer to store components of symmetry group (or NULL) componentbegins pointer to store begin positions of components in components array (or NULL) vartocomponent pointer to store assignment from variable to its component (or NULL) ncomponents pointer to store number of components (or NULL)
Definition at line 7616 of file prop_symmetry.c.
References SYM_Sortgraphcompvars::components, NULL, PROP_NAME, SCIP_Bool, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPerrorMessage, SCIPfindProp(), SCIPisOrbitalfixingEnabled(), SCIPpropGetData(), and SCIPpropGetName().
Referenced by initOrbits(), and SCIPincludePropSymmetry().
◆ SCIPisOrbitalfixingEnabled()
return whether orbital fixing is enabled
- Parameters
-
scip SCIP data structure
Definition at line 7696 of file prop_symmetry.c.
References FALSE, NULL, PROP_NAME, SCIPfindProp(), SCIPgetSymmetryNGenerators(), and SCIPpropGetData().
Referenced by SCIPgetSymmetry().
◆ SCIPgetSymmetryNGenerators()
int SCIPgetSymmetryNGenerators | ( | SCIP * | scip | ) |
return number of the symmetry group's generators
- Parameters
-
scip SCIP data structure
Definition at line 7716 of file prop_symmetry.c.
References NULL, PROP_NAME, SCIPfindProp(), and SCIPpropGetData().
Referenced by SCIPisOrbitalfixingEnabled().