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.

#include "blockmemshell/memory.h"
#include "scip/cons_orbitope.h"
#include "scip/cons_symresack.h"
#include "scip/misc.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 58 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 59 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 60 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 61 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ PRESOL_TIMING

#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE

timing for presolving

Definition at line 62 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 65 of file presol_symbreak.c.

Referenced by SCIPincludePresolSymbreak().

◆ DEFAULT_ADDSYMRESACKS

#define DEFAULT_ADDSYMRESACKS TRUE

Add inequalities for symresacks for each generator?

Definition at line 66 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 67 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 68 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 69 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

scip	SCIP instance
presoldata	data of symmetry breaking presolver

Definition at line 114 of file presol_symbreak.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPdisjointsetCreate(), SCIPdisjointsetFind(), SCIPdisjointsetFree(), SCIPdisjointsetUnion(), 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

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 296 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

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 356 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

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 476 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

scip	SCIP instance
presoldata	pointer to data of symbreak presolver

Definition at line 591 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

scip	SCIP instance
presol	symmetry breaking presolver

Definition at line 849 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

scip	SCIP instance
presol	presolver

Definition at line 946 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

find problem symmetries

Parameters

scip	SCIP instance
presol	data of presolver

Definition at line 974 of file presol_symbreak.c.

References addSymmetryBreakingConstraints(), detectOrbitopes(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcomputeGroupOrbitsSymbreak(), SCIPdebugMsg, SCIPgetGeneratorsSymmetry(), SCIPisStopped(), SCIPpresolGetData(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.

Referenced by SCIP_DECL_PRESOLEXEC(), SCIP_DECL_PRESOLEXITPRE(), and SCIP_DECL_PRESOLINITPRE().

◆ SCIP_DECL_PRESOLFREE()

static SCIP_DECL_PRESOLFREE ( presolFreeSymbreak )

static

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

Definition at line 1061 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 1079 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 1107 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 1182 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 1217 of file presol_symbreak.c.

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

◆ SCIP_DECL_PRESOLEXEC()

static SCIP_DECL_PRESOLEXEC ( presolExecSymbreak )

static

execution method of presolver

Definition at line 1242 of file presol_symbreak.c.

References NULL, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PRESOLTIMING_ALWAYS, SCIP_STAGE_PRESOLVING, SCIP_SUCCESS, SCIP_UNBOUNDED, SCIPconsGetName(), SCIPdebugMsg, SCIPgetStage(), SCIPisPresolveFinished(), SCIPisStopped(), SCIPpresolCons(), SCIPpresolGetData(), and tryAddSymmetryHandlingConss().

◆ SCIPincludePresolSymbreak()

SCIP_RETCODE SCIPincludePresolSymbreak ( SCIP * scip )

creates the symbreak presolver and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 1314 of file presol_symbreak.c.

References DEFAULT_ADDCONSSTIMING, DEFAULT_ADDSYMRESACKS, DEFAULT_COMPUTEORBITS, DEFAULT_CONSSADDLP, DEFAULT_DETECTORBITOPES, FALSE, NULL, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, PRESOL_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocMemory, SCIPincludePresolBasic(), SCIPsetPresolExit(), SCIPsetPresolExitpre(), SCIPsetPresolFree(), SCIPsetPresolInit(), SCIPsetPresolInitpre(), and TRUE.

Referenced by SCIPincludeDefaultPlugins().

◆ 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

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 1392 of file presol_symbreak.c.

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

Referenced by propagateOrbitalFixing(), and tryAddSymmetryHandlingConss().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ PRESOL_NAME

◆ PRESOL_DESC

◆ PRESOL_PRIORITY

◆ PRESOL_MAXROUNDS

◆ PRESOL_TIMING

◆ DEFAULT_CONSSADDLP

◆ DEFAULT_ADDSYMRESACKS

◆ DEFAULT_COMPUTEORBITS

◆ DEFAULT_DETECTORBITOPES

◆ DEFAULT_ADDCONSSTIMING

Function Documentation

◆ computeComponents()

◆ getPermProperties()

◆ extendSubOrbitope()

◆ generateOrbitopeVarsMatrix()

◆ detectOrbitopes()

◆ addSymresackConss()

◆ addSymmetryBreakingConstraints()

◆ tryAddSymmetryHandlingConss()

◆ SCIP_DECL_PRESOLFREE()

◆ SCIP_DECL_PRESOLINIT()

◆ SCIP_DECL_PRESOLEXIT()

◆ SCIP_DECL_PRESOLINITPRE()

◆ SCIP_DECL_PRESOLEXITPRE()

◆ SCIP_DECL_PRESOLEXEC()

◆ SCIPincludePresolSymbreak()

◆ SCIPcomputeGroupOrbitsSymbreak()