Scippy

SCIP

Solving Constraint Integer Programs

presol_symbreak.c File Reference

Detailed Description

presolver for adding symmetry breaking constraints

Author
Marc Pfetsch
Thomas Rehn
Christopher Hojny

This presolver adds the following symmetry breaking constraints:

  • minimal cover inequalities for symresacks via a constraint handler
Note
It is important to control the order of presolvers within SCIP in order to avoid contraditions. First, one needs to take care of presolvers that have an effect on symmetry, e.g., presol_domcol. If symmetry is computed on the original formulation, we perform this presolver at the very beginning. Otherwise, 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.

Definition in file presol_symbreak.c.

#include "blockmemshell/memory.h"
#include "scip/cons_orbitope.h"
#include "scip/cons_symresack.h"
#include "scip/presol_symbreak.h"
#include "scip/presol_symmetry.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_presol.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_param.h"
#include "scip/scip_presol.h"
#include "scip/scip_prob.h"
#include <string.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   FALSE
 
#define DEFAULT_ADDCONSSTIMING   2
 

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_RETCODE tryAddSymmetryHandlingConss (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_PRESOLEXITPRE (presolExitpreSymbreak)
 
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)
 

Macro Definition Documentation

◆ PRESOL_NAME

#define PRESOL_NAME   "symbreak"

Definition at line 57 of file presol_symbreak.c.

Referenced by SCIP_DECL_PRESOLEXITPRE(), and SCIPincludePresolSymbreak().

◆ PRESOL_DESC

#define PRESOL_DESC   "presolver for adding symmetry breaking constraints"

Definition at line 58 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ PRESOL_PRIORITY

#define PRESOL_PRIORITY   -10000000

priority of the presolver (>= 0: before, < 0: after constraint handlers)

Definition at line 59 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ PRESOL_MAXROUNDS

#define PRESOL_MAXROUNDS   -1

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 60 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ PRESOL_TIMING

#define PRESOL_TIMING   SCIP_PRESOLTIMING_EXHAUSTIVE

timing for presolving

Definition at line 61 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ DEFAULT_CONSSADDLP

#define DEFAULT_CONSSADDLP   TRUE

Should the symmetry breaking constraints be added to the LP?

Definition at line 64 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ DEFAULT_ADDSYMRESACKS

#define DEFAULT_ADDSYMRESACKS   TRUE

Add inequalities for symresacks for each generator?

Definition at line 65 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ DEFAULT_COMPUTEORBITS

#define DEFAULT_COMPUTEORBITS   FALSE

Should the orbits of the symmetry group be computed?

Definition at line 66 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ DEFAULT_DETECTORBITOPES

#define DEFAULT_DETECTORBITOPES   FALSE

Should we check whether the components of the symmetry group can be handled by orbitopes?

Definition at line 67 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ DEFAULT_ADDCONSSTIMING

#define DEFAULT_ADDCONSSTIMING   2

timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)

Definition at line 68 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

Function Documentation

◆ computeComponents()

static SCIP_RETCODE computeComponents ( SCIP scip,
SCIP_PRESOLDATA presoldata 
)
static

compute components of symmetry group

Parameters
scipSCIP instance
presoldatadata of symmetry breaking presolver

Definition at line 113 of file presol_symbreak.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetUnion(), SCIPfreeDisjointset(), and TRUE.

Referenced by detectOrbitopes().

◆ getPermProperties()

static SCIP_RETCODE getPermProperties ( int *  perm,
SCIP_VAR **  vars,
int  nvars,
SCIP_Bool iscompoftwocycles,
int *  ntwocyclesperm,
SCIP_Bool allvarsbinary 
)
static

check whether a permutation is a composition of 2-cycles of binary variables and in this case determines the number of 2-cycles

Parameters
permpermutation
varsarray of variables perm is acting on
nvarsnumber of variables
iscompoftwocyclespointer to store whether permutation is a composition of 2-cycles
ntwocyclespermpointer to store number of 2-cycles
allvarsbinarypointer to store whether perm is acting on binary variables only

Definition at line 295 of file presol_symbreak.c.

References FALSE, NULL, SCIP_OKAY, SCIPvarIsBinary(), and TRUE.

Referenced by detectOrbitopes().

◆ extendSubOrbitope()

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

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.

Precondition
Every non-trivial cycle of perm is a 2-cycle.
perm has nrows many 2-cycles
Parameters
suborbitopematrix containing suborbitope entries
nrowsnumber of rows of suborbitope
nfilledcolsnumber of columns of suborbitope which are filled with entries
coltoextendindex of column that should be extended by perm
permpermutation
leftextensionwhether we extend the suborbitope to the left
nusedelemspointer to array storing how often an element was used in the orbitope
successpointer to store whether extension was successful
infeasiblepointer to store if the number of intersecting cycles is too small

Definition at line 355 of file presol_symbreak.c.

References FALSE, NULL, SCIP_OKAY, and TRUE.

Referenced by detectOrbitopes().

◆ generateOrbitopeVarsMatrix()

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

generate variable matrix for orbitope constraint handler

Parameters
varspointer to matrix of orbitope variables
nrowsnumber of rows of orbitope
ncolsnumber of columns of orbitope
permvarssuperset of variables that are contained in orbitope
npermvarsnumber of variables in permvars array
orbitopevaridxpermuted index table of variables in permvars that are contained in orbitope
columnorderpermutation to reorder column of orbitopevaridx
nusedelemsarray storing how often an element was used in the orbitope
infeasiblepointer to store whether the potential orbitope is not an orbitope

Definition at line 475 of file presol_symbreak.c.

References NULL, SCIP_OKAY, SCIPvarIsBinary(), and TRUE.

Referenced by detectOrbitopes().

◆ detectOrbitopes()

static SCIP_RETCODE detectOrbitopes ( SCIP scip,
SCIP_PRESOLDATA presoldata 
)
static

check whether components of the symmetry group can be completely handled by orbitopes

Parameters
scipSCIP instance
presoldatapointer to data of symbreak presolver

Definition at line 590 of file presol_symbreak.c.

References computeComponents(), extendSubOrbitope(), FALSE, generateOrbitopeVarsMatrix(), getPermProperties(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIPaddCons(), SCIPallocBufferArray, SCIPcreateConsOrbitope(), SCIPfreeBufferArray, and TRUE.

Referenced by tryAddSymmetryHandlingConss().

◆ addSymresackConss()

static SCIP_RETCODE addSymresackConss ( SCIP scip,
SCIP_PRESOL presol 
)
static

add symresack constraints

Parameters
scipSCIP instance
presolsymmetry breaking presolver

Definition at line 848 of file presol_symbreak.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddCons(), SCIPcreateSymbreakCons(), SCIPdebugMsg, SCIPpresolGetData(), SCIPsnprintf(), and TRUE.

Referenced by addSymmetryBreakingConstraints().

◆ addSymmetryBreakingConstraints()

static SCIP_RETCODE addSymmetryBreakingConstraints ( SCIP scip,
SCIP_PRESOL presol 
)
static

analyze generators and add symmetry breaking constraints

Parameters
scipSCIP instance
presolpresolver

Definition at line 945 of file presol_symbreak.c.

References addSymresackConss(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPpresolGetData().

Referenced by tryAddSymmetryHandlingConss().

◆ tryAddSymmetryHandlingConss()

static SCIP_RETCODE tryAddSymmetryHandlingConss ( SCIP scip,
SCIP_PRESOL presol 
)
static

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeSymbreak  )
static

destructor of presolver to free user data (called when SCIP is exiting)

Definition at line 1060 of file presol_symbreak.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, and SCIPpresolGetData().

◆ SCIP_DECL_PRESOLINIT()

static SCIP_DECL_PRESOLINIT ( presolInitSymbreak  )
static

initialization method of presolver (called after problem was transformed)

Definition at line 1078 of file presol_symbreak.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetIntParam(), SCIPpresolGetData(), SYM_HANDLETYPE_SYMBREAK, and TRUE.

◆ SCIP_DECL_PRESOLEXIT()

static SCIP_DECL_PRESOLEXIT ( presolExitSymbreak  )
static

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

Definition at line 1106 of file presol_symbreak.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPpresolGetData(), SCIPreleaseCons(), and TRUE.

◆ SCIP_DECL_PRESOLINITPRE()

static SCIP_DECL_PRESOLINITPRE ( presolInitpreSymbreak  )
static

presolving initialization method of presolver (called when presolving is about to begin)

Definition at line 1181 of file presol_symbreak.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetIntParam(), SCIPpresolGetData(), SCIPsetIntParam(), SYM_HANDLETYPE_SYMBREAK, TRUE, and tryAddSymmetryHandlingConss().

◆ SCIP_DECL_PRESOLEXITPRE()

static SCIP_DECL_PRESOLEXITPRE ( presolExitpreSymbreak  )
static

presolving deinitialization method of presolver (called after presolving has been finished)

Definition at line 1216 of file presol_symbreak.c.

References NULL, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPpresolGetData(), SCIPpresolGetName(), and tryAddSymmetryHandlingConss().

◆ SCIP_DECL_PRESOLEXEC()

◆ SCIPincludePresolSymbreak()

◆ SCIPcomputeGroupOrbitsSymbreak()

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.

Parameters
scipSCIP instance
permvarsvariables considered by symbreak presolver
npermvarslength of a permutation array
permsmatrix containing in each row a permutation of the symmetry group
npermsnumber of permutations encoded in perms
activepermsarray for marking active permutations (or NULL)
orbitsarray of non-trivial orbits
orbitbeginsarray containing begin positions of new orbits in orbits array
norbitspointer to number of orbits currently stored in orbits

Definition at line 1391 of file presol_symbreak.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by propagateOrbitalFixing(), and tryAddSymmetryHandlingConss().