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
-
scip SCIP instance issigned whether orbits for signed permutations shall be computed permvars variables considered in a permutation 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 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 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
-
scip SCIP instance npermvars length of a permutation array permstrans transposed matrix containing in each column a permutation of the symmetry group nperms number of permutations encoded in perms inactiveperms array to store whether permutations are inactive 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 components array containing the indices of permutations sorted by components componentbegins array containing in i-th position the first position of component i in components array vartocomponent array containing for each permvar the index of the component it is contained in (-1 if not affected) componentblocked array to store which symmetry methods have been used on a component using the same bitset information as for misc/usesymmetry ncomponents number of components of symmetry group nmovedpermvars number 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
-
scip SCIP instance npermvars length of a permutation array permstrans transposed matrix containing in each column a permutation of the symmetry group nperms number of permutations encoded in perms components array containing the indices of permutations sorted by components componentbegins array containing in i-th position the first position of component i in components array vartocomponent array containing for each permvar the index of the component it is contained in (-1 if not affected) ncomponents number of components of symmetry group 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 varorbitmap array 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
andpermstrans
should not be NULL
- Parameters
-
scip SCIP instance npermvars number of variables in permvars perms the generators of the permutation group (or NULL) permstrans the transposed matrix of generators (or NULL) components the components of the permutation group componentbegins array containing the starting index of each component ignoredvars array indicating which variables should be ignored varfound bitmap to mark which variables have been added (or NULL) varidx index of variable for which the orbit is requested component component that var is in orbit array in which the orbit should be stored orbitsize buffer 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
-
perm permutation vars array of variables perm is acting on nvars number of variables ntwocyclesperm pointer to store number of 2-cycles or 0 if perm is not an involution nbincyclesperm pointer to store number of binary cycles earlytermination whether 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
-
scip SCIP instance perms permutations nperms number of permutations in perms permvars variables corresponding to permutations npermvars number of permvars in perms nvarsaffected pointer 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
-
scip SCIP instance symtype type of symmetries in perms perms permutation generators as (either nperms x npermvars or npermvars x nperms) matrix nperms number of permutations permvars variables on which permutations act npermvars number of variables for permutations transposed transposed permutation generators as (npermvars x nperms) matrix components array containing the indices of permutations sorted by components componentbegins array containing in i-th position the first position of component i in components array vartocomponent array containing for each permvar the index of the component it is contained in (-1 if not affected) componentblocked array to store which symmetry methods have been used on a component using the same bitset information as for misc/usesymmetry ncomponents pointer 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
-
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 permvars permutation vars array rowisbinary array encoding whether variables in an orbitope row are binary (or NULL) success pointer to store whether extension was successful infeasible pointer 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
-
scip SCIP instance 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 rowisbinary array encoding whether a row contains only binary variables (or NULL) infeasible pointer to store whether the potential orbitope is not an orbitope storelexorder whether the lexicographic order induced by the orbitope shall be stored lexorder pointer to array storing the lexorder (or NULL) nvarsorder pointer to store number of variables in lexorder (or NULL) maxnvarsorder pointer 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
-
scip SCIP data structure vars variable matrix of orbitope constraint nrows pointer to number of rows of variable matrix ncols number of columns of variable matrix pprows pointer to store which rows are are contained in packing/partitioning constraints or NULL if not needed npprows pointer to store how many rows are contained in packing/partitioning constraints or NULL if not needed type pointer 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
-
scip SCIP pointer detectsinglelex whether single lex matrices shall be detected perms array of permutations nperms number of permutations in perms permlen number of variables in a permutation success pointer to store whether structure could be detected isorbitope pointer to store whether detected matrix is orbitopal lexmatrix pointer to store single or double lex matrix nrows pointer to store number of rows of lexmatrix ncols pointer to store number of columns of lexmatrix lexrowsbegin pointer to store array indicating begin of new row-lexmatrix lexcolsbegin pointer to store array indicating begin of new col-lexmatrix nrowmatrices pointer to store number of single lex row matrices in rows ncolmatrices pointer 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()
helper function to test if val1 = val2 while permitting infinity-values
- Parameters
-
scip SCIP data structure val1 left-hand side value val2 right-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()
helper function to test if val1 <= val2 while permitting infinity-values
- Parameters
-
scip SCIP data structure val1 left-hand side value val2 right-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()
helper function to test if val1 >= val2 while permitting infinity-values
- Parameters
-
scip SCIP data structure val1 left-hand side value val2 right-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()
helper function to test if val1 < val2 while permitting infinity-values
- Parameters
-
scip SCIP data structure val1 left-hand side value val2 right-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()
helper function to test if val1 > val2 while permitting infinity-values
- Parameters
-
scip SCIP data structure val1 left-hand side value val2 right-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().