presolver for adding symmetry breaking constraints
This presolver adds the following symmetry breaking constraints:
Definition in file presol_symbreak.c.
#include <assert.h>
#include <scip/cons_linear.h>
#include <scip/cons_orbitope.h>
#include <scip/cons_setppc.h>
#include <scip/cons_symresack.h>
#include <scip/misc.h>
#include <scip/prop_probing.h>
#include <scip/presol_symbreak.h>
#include <scip/presol_symmetry.h>
#include <symmetry/type_symmetry.h>
Go to the source code of this file.
Macros | |
#define | PRESOL_NAME "symbreak" |
#define | PRESOL_DESC "presolver for adding symmetry breaking constraints" |
#define | PRESOL_PRIORITY -10000000 |
#define | PRESOL_MAXROUNDS -1 |
#define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE |
#define | DEFAULT_CONSSADDLP TRUE |
#define | DEFAULT_ADDSYMRESACKS TRUE |
#define | DEFAULT_COMPUTEORBITS FALSE |
#define | DEFAULT_DETECTORBITOPES TRUE |
Functions | |
static SCIP_RETCODE | computeComponents (SCIP *scip, SCIP_PRESOLDATA *presoldata) |
static SCIP_RETCODE | getPermProperties (int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool *iscompoftwocycles, int *ntwocyclesperm, SCIP_Bool *allvarsbinary) |
static SCIP_RETCODE | extendSubOrbitope (int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_Bool *success, SCIP_Bool *infeasible) |
static SCIP_RETCODE | generateOrbitopeVarsMatrix (SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Bool *infeasible) |
static SCIP_RETCODE | detectOrbitopes (SCIP *scip, SCIP_PRESOLDATA *presoldata) |
static SCIP_RETCODE | addSymresackConss (SCIP *scip, SCIP_PRESOL *presol) |
static SCIP_RETCODE | addSymmetryBreakingConstraints (SCIP *scip, SCIP_PRESOL *presol) |
static | SCIP_DECL_PRESOLFREE (presolFreeSymbreak) |
static | SCIP_DECL_PRESOLINIT (presolInitSymbreak) |
static | SCIP_DECL_PRESOLEXIT (presolExitSymbreak) |
static | SCIP_DECL_PRESOLINITPRE (presolInitpreSymbreak) |
static | SCIP_DECL_PRESOLEXEC (presolExecSymbreak) |
SCIP_RETCODE | SCIPincludePresolSymbreak (SCIP *scip) |
SCIP_RETCODE | SCIPcomputeGroupOrbitsSymbreak (SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Shortbool *activeperms, int *orbits, int *orbitbegins, int *norbits) |
#define PRESOL_NAME "symbreak" |
Definition at line 50 of file presol_symbreak.c.
Referenced by SCIP_DECL_PRESOLINITPRE(), and SCIPincludePresolSymbreak().
#define PRESOL_DESC "presolver for adding symmetry breaking constraints" |
Definition at line 51 of file presol_symbreak.c.
Referenced by SCIPincludePresolSymbreak().
#define PRESOL_PRIORITY -10000000 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 52 of file presol_symbreak.c.
Referenced by SCIPincludePresolSymbreak().
#define PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 53 of file presol_symbreak.c.
Referenced by SCIPincludePresolSymbreak().
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE |
timing for presolving
Definition at line 54 of file presol_symbreak.c.
Referenced by SCIPincludePresolSymbreak().
#define DEFAULT_CONSSADDLP TRUE |
Should the symmetry breaking constraints be added to the LP?
Definition at line 57 of file presol_symbreak.c.
Referenced by SCIPincludePresolSymbreak().
#define DEFAULT_ADDSYMRESACKS TRUE |
Add inequalities for symresacks for each generator?
Definition at line 58 of file presol_symbreak.c.
Referenced by SCIPincludePresolSymbreak().
#define DEFAULT_COMPUTEORBITS FALSE |
Should the orbits of the symmetry group be computed?
Definition at line 59 of file presol_symbreak.c.
Referenced by SCIPincludePresolSymbreak().
#define DEFAULT_DETECTORBITOPES TRUE |
Should we check whether the components of the symmetry group can be handled by orbitopes?
Definition at line 60 of file presol_symbreak.c.
Referenced by SCIPincludePresolSymbreak().
|
static |
compute components of symmetry group
scip | SCIP instance |
presoldata | data of symmetry breaking presolver |
Definition at line 104 of file presol_symbreak.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPdisjointsetCreate(), SCIPdisjointsetFind(), SCIPdisjointsetFree(), SCIPdisjointsetUnion(), and TRUE.
Referenced by detectOrbitopes().
|
static |
check whether a permutation is a composition of 2-cycles of binary variables and in this case determines the number of 2-cycles
perm | permutation |
vars | array of variables perm is acting on |
nvars | number of variables |
iscompoftwocycles | pointer to store whether permutation is a composition of 2-cycles |
ntwocyclesperm | pointer to store number of 2-cycles |
allvarsbinary | pointer to store whether perm is acting on binary variables only |
Definition at line 286 of file presol_symbreak.c.
References FALSE, SCIP_OKAY, SCIPvarIsBinary(), and TRUE.
Referenced by detectOrbitopes().
|
static |
Given a matrix with nrows and #perms + 1 columns whose first nfilledcols columns contain entries of variables, this routine checks whether the 2-cycles of perm intersect each row of column coltoextend in exactly one position. In this case, we add one column to the suborbitope of the first nfilledcols columns.
suborbitope | matrix containing suborbitope entries |
nrows | number of rows of suborbitope |
nfilledcols | number of columns of suborbitope which are filled with entries |
coltoextend | index of column that should be extended by perm |
perm | permutation |
leftextension | whether we extend the suborbitope to the left |
nusedelems | pointer to array storing how often an element was used in the orbitope |
success | pointer to store whether extension was successful |
infeasible | pointer to store if the number of intersecting cycles is too small |
Definition at line 346 of file presol_symbreak.c.
References FALSE, SCIP_OKAY, and TRUE.
Referenced by detectOrbitopes().
|
static |
generate variable matrix for orbitope constraint handler
vars | pointer to matrix of orbitope variables |
nrows | number of rows of orbitope |
ncols | number of columns of orbitope |
permvars | superset of variables that are contained in orbitope |
npermvars | number of variables in permvars array |
orbitopevaridx | permuted index table of variables in permvars that are contained in orbitope |
columnorder | permutation to reorder column of orbitopevaridx |
nusedelems | array storing how often an element was used in the orbitope |
infeasible | pointer to store whether the potential orbitope is not an orbitope |
Definition at line 467 of file presol_symbreak.c.
References SCIP_OKAY, SCIPvarIsBinary(), and TRUE.
Referenced by detectOrbitopes().
|
static |
check whether components of the symmetry group can be completely handled by orbitopes
scip | SCIP instance |
presoldata | pointer to data of symbreak presolver |
Definition at line 582 of file presol_symbreak.c.
References computeComponents(), extendSubOrbitope(), FALSE, generateOrbitopeVarsMatrix(), getPermProperties(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsOrbitope(), SCIPfreeBufferArray, and TRUE.
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
add symresack constraints
scip | SCIP instance |
presol | symmetry breaking presolver |
Definition at line 838 of file presol_symbreak.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPpresolGetData(), SCIPsnprintf(), and TRUE.
Referenced by addSymmetryBreakingConstraints().
|
static |
analyze generators and add symmetry breaking constraints
scip | SCIP instance |
presol | presolver |
Definition at line 932 of file presol_symbreak.c.
References addSymresackConss(), SCIP_CALL, SCIP_OKAY, and SCIPpresolGetData().
Referenced by SCIP_DECL_PRESOLEXEC().
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 965 of file presol_symbreak.c.
References SCIP_OKAY, SCIPfreeMemory, and SCIPpresolGetData().
|
static |
initialization method of presolver (called after problem was transformed)
Definition at line 983 of file presol_symbreak.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetIntParam(), SCIPpresolGetData(), SCIPregisterSymmetry(), SYM_HANDLETYPE_SYMBREAK, SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.
|
static |
deinitialization method of presolver (called before transformed problem is freed)
Definition at line 1017 of file presol_symbreak.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPpresolGetData(), SCIPreleaseCons(), and TRUE.
|
static |
presolving initialization method of presolver (called when presolving is about to begin)
Definition at line 1092 of file presol_symbreak.c.
References FALSE, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_MINIMAL, SCIPgetIntParam(), SCIPgetTimingSymmetry(), SCIPpresolGetData(), SCIPpresolGetName(), SCIPregisterSymmetry(), SCIPsetIntParam(), SCIPverbMessage(), SYM_HANDLETYPE_SYMBREAK, SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.
|
static |
execution method of presolver
Definition at line 1136 of file presol_symbreak.c.
References addSymmetryBreakingConstraints(), detectOrbitopes(), FALSE, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PRESOLTIMING_ALWAYS, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIPallocBlockMemoryArray, SCIPcomputeGroupOrbitsSymbreak(), SCIPconsGetName(), SCIPdebugMsg, SCIPgetGeneratorsSymmetry(), SCIPgetStage(), SCIPisPresolveFinished(), SCIPisStopped(), SCIPpresolCons(), SCIPpresolGetData(), SCIPsetIntParam(), and TRUE.
SCIP_RETCODE SCIPincludePresolSymbreak | ( | SCIP * | scip | ) |
creates the symbreak presolver and includes it in SCIP
scip | SCIP data structure |
Definition at line 1264 of file presol_symbreak.c.
References DEFAULT_ADDSYMRESACKS, DEFAULT_COMPUTEORBITS, DEFAULT_CONSSADDLP, DEFAULT_DETECTORBITOPES, FALSE, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, PRESOL_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPallocMemory, SCIPincludePresolBasic(), SCIPsetPresolExit(), SCIPsetPresolFree(), SCIPsetPresolInit(), SCIPsetPresolInitpre(), and TRUE.
Referenced by SCIPincludeDefaultPlugins().
SCIP_RETCODE SCIPcomputeGroupOrbitsSymbreak | ( | SCIP * | scip, |
SCIP_VAR ** | permvars, | ||
int | npermvars, | ||
int ** | perms, | ||
int | nperms, | ||
SCIP_Shortbool * | activeperms, | ||
int * | orbits, | ||
int * | orbitbegins, | ||
int * | norbits | ||
) |
compute non-trivial orbits of symmetry group
The non-tivial orbits of the group action are stored in the array orbits of length npermvars. This array contains the indices of variables from the permvars array such that variables that are contained in the same orbit appear consecutively in the orbits array. The variables of the i-th orbit have indices orbits[orbitbegins[i]], ... , orbits[orbitbegins[i + 1] - 1]. Note that the description of the orbits ends at orbitbegins[norbits] - 1.
scip | SCIP instance |
permvars | variables considered by symbreak presolver |
npermvars | length of a permutation array |
perms | matrix containing in each row a permutation of the symmetry group |
nperms | number of permutations encoded in perms |
activeperms | array for marking active permutations (or NULL) |
orbits | array of non-trivial orbits |
orbitbegins | array containing begin positions of new orbits in orbits array |
norbits | pointer to number of orbits currently stored in orbits |
Definition at line 1336 of file presol_symbreak.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.
Referenced by propagateOrbitalFixing(), and SCIP_DECL_PRESOLEXEC().