Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

methods for symmetry handling

Functions

SCIP_RETCODE SCIPcomputeOrbitsSym (SCIP *scip, SCIP_Bool issigned, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
 
SCIP_RETCODE SCIPcomputeOrbitsFilterSym (SCIP *scip, int npermvars, int **permstrans, int nperms, SCIP_Shortbool *inactiveperms, int *orbits, int *orbitbegins, int *norbits, int *components, int *componentbegins, int *vartocomponent, unsigned *componentblocked, int ncomponents, int nmovedpermvars)
 
SCIP_RETCODE SCIPcomputeOrbitsComponentsSym (SCIP *scip, int npermvars, int **permstrans, int nperms, int *components, int *componentbegins, int *vartocomponent, int ncomponents, int *orbits, int *orbitbegins, int *norbits, int *varorbitmap)
 
SCIP_RETCODE SCIPcomputeOrbitVar (SCIP *scip, int npermvars, int **perms, int **permstrans, int *components, int *componentbegins, SCIP_Shortbool *ignoredvars, SCIP_Shortbool *varfound, int varidx, int component, int *orbit, int *orbitsize)
 
SCIP_RETCODE SCIPisInvolutionPerm (int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
 
SCIP_RETCODE SCIPdetermineNVarsAffectedSym (SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
 
SCIP_RETCODE SCIPcomputeComponentsSym (SCIP *scip, SYM_SYMTYPE symtype, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, unsigned **componentblocked, int *ncomponents)
 
SCIP_RETCODE SCIPextendSubOrbitope (int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_VAR **permvars, SCIP_Shortbool *rowisbinary, SCIP_Bool *success, SCIP_Bool *infeasible)
 
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix (SCIP *scip, SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Shortbool *rowisbinary, SCIP_Bool *infeasible, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
 
SCIP_RETCODE SCIPisPackingPartitioningOrbitope (SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
 
SCIP_RETCODE SCIPdetectSingleOrDoubleLexMatrices (SCIP *scip, SCIP_Bool detectsinglelex, int **perms, int nperms, int permlen, SCIP_Bool *success, SCIP_Bool *isorbitope, int ***lexmatrix, int *nrows, int *ncols, int **lexrowsbegin, int **lexcolsbegin, int *nrowmatrices, int *ncolmatrices)
 
SCIP_Bool SCIPsymEQ (SCIP *scip, SCIP_Real val1, SCIP_Real val2)
 
SCIP_Bool SCIPsymLE (SCIP *scip, SCIP_Real val1, SCIP_Real val2)
 
SCIP_Bool SCIPsymGE (SCIP *scip, SCIP_Real val1, SCIP_Real val2)
 
SCIP_Bool SCIPsymLT (SCIP *scip, SCIP_Real val1, SCIP_Real val2)
 
SCIP_Bool SCIPsymGT (SCIP *scip, SCIP_Real val1, SCIP_Real val2)
 

Function Documentation

◆ SCIPcomputeOrbitsSym()

SCIP_RETCODE SCIPcomputeOrbitsSym ( SCIP scip,
SCIP_Bool  issigned,
SCIP_VAR **  permvars,
int  npermvars,
int **  perms,
int  nperms,
int *  orbits,
int *  orbitbegins,
int *  norbits 
)

compute non-trivial orbits of symmetry group

The non-trivial 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
issignedwhether orbits for signed permutations shall be computed
permvarsvariables considered in a permutation
npermvarslength of a permutation array
permsmatrix containing in each row a permutation of the symmetry group
npermsnumber of permutations encoded in perms
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 52 of file symmetry.c.

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

◆ SCIPcomputeOrbitsFilterSym()

SCIP_RETCODE SCIPcomputeOrbitsFilterSym ( SCIP scip,
int  npermvars,
int **  permstrans,
int  nperms,
SCIP_Shortbool inactiveperms,
int *  orbits,
int *  orbitbegins,
int *  norbits,
int *  components,
int *  componentbegins,
int *  vartocomponent,
unsigned *  componentblocked,
int  ncomponents,
int  nmovedpermvars 
)

compute non-trivial orbits of symmetry group using filtered generators

The non-trivial 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.

Only permutations that are not inactive (as marked by inactiveperms) are used. Thus, one can use this array to filter out permutations.

Parameters
scipSCIP instance
npermvarslength of a permutation array
permstranstransposed matrix containing in each column a permutation of the symmetry group
npermsnumber of permutations encoded in perms
inactivepermsarray to store whether permutations are inactive
orbitsarray of non-trivial orbits
orbitbeginsarray containing begin positions of new orbits in orbits array
norbitspointer to number of orbits currently stored in orbits
componentsarray containing the indices of permutations sorted by components
componentbeginsarray containing in i-th position the first position of component i in components array
vartocomponentarray containing for each permvar the index of the component it is contained in (-1 if not affected)
componentblockedarray to store which symmetry methods have been used on a component using the same bitset information as for misc/usesymmetry
ncomponentsnumber of components of symmetry group
nmovedpermvarsnumber of variables moved by any permutation in a symmetry component that is handled by orbital fixing

Definition at line 172 of file symmetry.c.

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

Referenced by addSSTConss().

◆ SCIPcomputeOrbitsComponentsSym()

SCIP_RETCODE SCIPcomputeOrbitsComponentsSym ( SCIP scip,
int  npermvars,
int **  permstrans,
int  nperms,
int *  components,
int *  componentbegins,
int *  vartocomponent,
int  ncomponents,
int *  orbits,
int *  orbitbegins,
int *  norbits,
int *  varorbitmap 
)

compute non-trivial orbits of symmetry group

The non-trivial 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.

This function is adapted from SCIPcomputeOrbitsFilterSym().

compute non-trivial orbits of symmetry group

The non-trivial 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.

This function is adapted from computeGroupOrbitsFilter().

Parameters
scipSCIP instance
npermvarslength of a permutation array
permstranstransposed matrix containing in each column a permutation of the symmetry group
npermsnumber of permutations encoded in perms
componentsarray containing the indices of permutations sorted by components
componentbeginsarray containing in i-th position the first position of component i in components array
vartocomponentarray containing for each permvar the index of the component it is contained in (-1 if not affected)
ncomponentsnumber of components of symmetry group
orbitsarray of non-trivial orbits
orbitbeginsarray containing begin positions of new orbits in orbits array
norbitspointer to number of orbits currently stored in orbits
varorbitmaparray for storing the orbits for each variable

Definition at line 420 of file symmetry.c.

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

Referenced by initOrbits().

◆ SCIPcomputeOrbitVar()

SCIP_RETCODE SCIPcomputeOrbitVar ( SCIP scip,
int  npermvars,
int **  perms,
int **  permstrans,
int *  components,
int *  componentbegins,
SCIP_Shortbool ignoredvars,
SCIP_Shortbool varfound,
int  varidx,
int  component,
int *  orbit,
int *  orbitsize 
)

Compute orbit of a given variable and store it in orbit. The first entry of the orbit will be the given variable index and the rest is filled with the remaining variables excluding the ones specified in ignoredvars.

Precondition
orbit is an initialized array of size propdata->npermvars
at least one of perms and permstrans should not be NULL
Parameters
scipSCIP instance
npermvarsnumber of variables in permvars
permsthe generators of the permutation group (or NULL)
permstransthe transposed matrix of generators (or NULL)
componentsthe components of the permutation group
componentbeginsarray containing the starting index of each component
ignoredvarsarray indicating which variables should be ignored
varfoundbitmap to mark which variables have been added (or NULL)
varidxindex of variable for which the orbit is requested
componentcomponent that var is in
orbitarray in which the orbit should be stored
orbitsizebuffer to store the size of the orbit

Definition at line 320 of file symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocClearBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by addWeakSBCsSubgroup().

◆ SCIPisInvolutionPerm()

SCIP_RETCODE SCIPisInvolutionPerm ( int *  perm,
SCIP_VAR **  vars,
int  nvars,
int *  ntwocyclesperm,
int *  nbincyclesperm,
SCIP_Bool  earlytermination 
)

Checks whether a permutation is a composition of 2-cycles and in this case determine the number of overall 2-cycles and binary 2-cycles. It is a composition of 2-cycles iff ntwocyclesperm > 0 upon termination.

Checks whether a permutation is a composition of 2-cycles and in this case determines the number of overall 2-cycles and binary 2-cycles. It is a composition of 2-cycles iff ntwocyclesperm > 0 upon termination.

Parameters
permpermutation
varsarray of variables perm is acting on
nvarsnumber of variables
ntwocyclespermpointer to store number of 2-cycles or 0 if perm is not an involution
nbincyclespermpointer to store number of binary cycles
earlyterminationwhether we terminate early if not all affected variables are binary

Definition at line 542 of file symmetry.c.

References NULL, SCIP_OKAY, and SCIPvarIsBinary().

Referenced by chooseOrderOfGenerators().

◆ SCIPdetermineNVarsAffectedSym()

SCIP_RETCODE SCIPdetermineNVarsAffectedSym ( SCIP scip,
int **  perms,
int  nperms,
SCIP_VAR **  permvars,
int  npermvars,
int *  nvarsaffected 
)

determine number of variables affected by symmetry group

Parameters
scipSCIP instance
permspermutations
npermsnumber of permutations in perms
permvarsvariables corresponding to permutations
npermvarsnumber of permvars in perms
nvarsaffectedpointer to store number of all affected variables

Definition at line 593 of file symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocClearBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by determineSymmetry().

◆ SCIPcomputeComponentsSym()

SCIP_RETCODE SCIPcomputeComponentsSym ( SCIP scip,
SYM_SYMTYPE  symtype,
int **  perms,
int  nperms,
SCIP_VAR **  permvars,
int  npermvars,
SCIP_Bool  transposed,
int **  components,
int **  componentbegins,
int **  vartocomponent,
unsigned **  componentblocked,
int *  ncomponents 
)

compute components of symmetry group

Parameters
scipSCIP instance
symtypetype of symmetries in perms
permspermutation generators as (either nperms x npermvars or npermvars x nperms) matrix
npermsnumber of permutations
permvarsvariables on which permutations act
npermvarsnumber of variables for permutations
transposedtransposed permutation generators as (npermvars x nperms) matrix
componentsarray containing the indices of permutations sorted by components
componentbeginsarray containing in i-th position the first position of component i in components array
vartocomponentarray containing for each permvar the index of the component it is contained in (-1 if not affected)
componentblockedarray to store which symmetry methods have been used on a component using the same bitset information as for misc/usesymmetry
ncomponentspointer to store number of components of symmetry group

Definition at line 775 of file symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPdisjointsetCreate(), SCIPdisjointsetFind(), SCIPdisjointsetFree(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPsortIntInt(), SYM_SYMTYPE_SIGNPERM, and TRUE.

Referenced by ensureSymmetryComponentsComputed().

◆ SCIPextendSubOrbitope()

SCIP_RETCODE SCIPextendSubOrbitope ( int **  suborbitope,
int  nrows,
int  nfilledcols,
int  coltoextend,
int *  perm,
SCIP_Bool  leftextension,
int **  nusedelems,
SCIP_VAR **  permvars,
SCIP_Shortbool rowisbinary,
SCIP_Bool success,
SCIP_Bool infeasible 
)

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
permvarspermutation vars array
rowisbinaryarray encoding whether variables in an orbitope row are binary (or NULL)
successpointer to store whether extension was successful
infeasiblepointer to store if the number of intersecting cycles is too small

Definition at line 645 of file symmetry.c.

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

Referenced by checkTwoCyclePermsAreOrbitope().

◆ SCIPgenerateOrbitopeVarsMatrix()

SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix ( SCIP scip,
SCIP_VAR ****  vars,
int  nrows,
int  ncols,
SCIP_VAR **  permvars,
int  npermvars,
int **  orbitopevaridx,
int *  columnorder,
int *  nusedelems,
SCIP_Shortbool rowisbinary,
SCIP_Bool infeasible,
SCIP_Bool  storelexorder,
int **  lexorder,
int *  nvarsorder,
int *  maxnvarsorder 
)

generate variable matrix for orbitope constraint handler

generate variable matrix for orbitope constraint handler

Precondition
if storelexorder is TRUE, then the permutations define an orbitope
Parameters
scipSCIP instance
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
rowisbinaryarray encoding whether a row contains only binary variables (or NULL)
infeasiblepointer to store whether the potential orbitope is not an orbitope
storelexorderwhether the lexicographic order induced by the orbitope shall be stored
lexorderpointer to array storing the lexorder (or NULL)
nvarsorderpointer to store number of variables in lexorder (or NULL)
maxnvarsorderpointer to store maximum number of variables in lexorder (or NULL)

Definition at line 987 of file symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPreallocBlockMemoryArray, SCIPvarIsBinary(), and TRUE.

Referenced by addOrbitopeSubgroup().

◆ SCIPisPackingPartitioningOrbitope()

SCIP_RETCODE SCIPisPackingPartitioningOrbitope ( SCIP scip,
SCIP_VAR ***  vars,
int  nrows,
int  ncols,
SCIP_Bool **  pprows,
int *  npprows,
SCIP_ORBITOPETYPE type 
)

checks whether an orbitope is a packing or partitioning orbitope

checks whether an orbitope is a packing or partitioning orbitope; if npprows != NULL, count how many rows are contained in packing/partitioning constraints

Parameters
scipSCIP data structure
varsvariable matrix of orbitope constraint
nrowspointer to number of rows of variable matrix
ncolsnumber of columns of variable matrix
pprowspointer to store which rows are are contained in packing/partitioning constraints or NULL if not needed
npprowspointer to store how many rows are contained in packing/partitioning constraints or NULL if not needed
typepointer to store type of orbitope constraint after strengthening

Definition at line 1178 of file symmetry.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_ORBITOPETYPE_FULL, SCIP_ORBITOPETYPE_PACKING, SCIP_ORBITOPETYPE_PARTITIONING, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPallocClearBufferArray, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetNTotalVars(), SCIPgetNVarsSetppc(), SCIPgetTypeSetppc(), SCIPgetVarsSetppc(), and SCIPvarGetIndex().

Referenced by addOrbitopesDynamic(), packingUpgrade(), and strengthenOrbitopeConstraint().

◆ SCIPdetectSingleOrDoubleLexMatrices()

SCIP_RETCODE SCIPdetectSingleOrDoubleLexMatrices ( SCIP scip,
SCIP_Bool  detectsinglelex,
int **  perms,
int  nperms,
int  permlen,
SCIP_Bool success,
SCIP_Bool isorbitope,
int ***  lexmatrix,
int *  nrows,
int *  ncols,
int **  lexrowsbegin,
int **  lexcolsbegin,
int *  nrowmatrices,
int *  ncolmatrices 
)

detects whether permutations define single or double lex matrices

A single lex matrix is a matrix whose columns can be partitioned into blocks such that the columns within each block can be permuted arbitrarily. A double lex matrix is a single lex matrix such that also blocks of rows have the aforementioned property.

Parameters
scipSCIP pointer
detectsinglelexwhether single lex matrices shall be detected
permsarray of permutations
npermsnumber of permutations in perms
permlennumber of variables in a permutation
successpointer to store whether structure could be detected
isorbitopepointer to store whether detected matrix is orbitopal
lexmatrixpointer to store single or double lex matrix
nrowspointer to store number of rows of lexmatrix
ncolspointer to store number of columns of lexmatrix
lexrowsbeginpointer to store array indicating begin of new row-lexmatrix
lexcolsbeginpointer to store array indicating begin of new col-lexmatrix
nrowmatricespointer to store number of single lex row matrices in rows
ncolmatricespointer to store number of single lex column matrices in rows

Definition at line 2024 of file symmetry.c.

References detectOrbitopalSymmetries(), FALSE, isDoublelLexSym(), isPermInvolution(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, and TRUE.

Referenced by tryHandleSingleOrDoubleLexMatricesComponent().

◆ SCIPsymEQ()

SCIP_Bool SCIPsymEQ ( SCIP scip,
SCIP_Real  val1,
SCIP_Real  val2 
)

helper function to test if val1 = val2 while permitting infinity-values

Parameters
scipSCIP data structure
val1left-hand side value
val2right-hand side value

Definition at line 2192 of file symmetry.c.

References FALSE, SCIP_Bool, SCIPisEQ(), SCIPisInfinity(), and TRUE.

Referenced by assertIsOrbitopeMatrix(), identifyOrbitalSymmetriesBroken(), propagateStaticLexred(), propagateStaticOrbitope(), testColumnsAreSymmetricallyEquivalent(), and updateColumnOrderWhenBranchingOnColumn().

◆ SCIPsymLE()

SCIP_Bool SCIPsymLE ( SCIP scip,
SCIP_Real  val1,
SCIP_Real  val2 
)

helper function to test if val1 <= val2 while permitting infinity-values

Parameters
scipSCIP data structure
val1left-hand side value
val2right-hand side value

Definition at line 2226 of file symmetry.c.

References FALSE, SCIP_Bool, SCIPisInfinity(), SCIPisLE(), and TRUE.

Referenced by assertIsOrbitopeMatrix(), identifyOrbitalSymmetriesBroken(), propagateStaticLexred(), and propagateStaticOrbitope().

◆ SCIPsymGE()

SCIP_Bool SCIPsymGE ( SCIP scip,
SCIP_Real  val1,
SCIP_Real  val2 
)

helper function to test if val1 >= val2 while permitting infinity-values

Parameters
scipSCIP data structure
val1left-hand side value
val2right-hand side value

Definition at line 2264 of file symmetry.c.

References FALSE, SCIP_Bool, SCIPisGE(), SCIPisInfinity(), and TRUE.

Referenced by assertIsOrbitopeMatrix(), identifyOrbitalSymmetriesBroken(), propagateStaticLexred(), and propagateStaticOrbitope().

◆ SCIPsymLT()

SCIP_Bool SCIPsymLT ( SCIP scip,
SCIP_Real  val1,
SCIP_Real  val2 
)

helper function to test if val1 < val2 while permitting infinity-values

Parameters
scipSCIP data structure
val1left-hand side value
val2right-hand side value

Definition at line 2302 of file symmetry.c.

References FALSE, SCIP_Bool, SCIPisInfinity(), SCIPisLT(), and TRUE.

Referenced by identifyOrbitalSymmetriesBroken(), and propagateStaticOrbitope().

◆ SCIPsymGT()

SCIP_Bool SCIPsymGT ( SCIP scip,
SCIP_Real  val1,
SCIP_Real  val2 
)

helper function to test if val1 > val2 while permitting infinity-values

Parameters
scipSCIP data structure
val1left-hand side value
val2right-hand side value

Definition at line 2340 of file symmetry.c.

References FALSE, SCIP_Bool, SCIPisGT(), SCIPisInfinity(), and TRUE.

Referenced by assertIsOrbitopeMatrix(), identifyOrbitalSymmetriesBroken(), propagateStaticLexred(), and propagateStaticOrbitope().