Detailed Description
methods for symmetry handling
Functions | |
SCIP_RETCODE | SCIPcomputeOrbitsSym (SCIP *scip, 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, 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) |
Function Documentation
◆ SCIPcomputeOrbitsSym()
SCIP_RETCODE SCIPcomputeOrbitsSym | ( | SCIP * | scip, |
SCIP_VAR ** | permvars, | ||
int | npermvars, | ||
int ** | perms, | ||
int | nperms, | ||
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 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 49 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 163 of file symmetry.c.
References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Shortbool, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.
Referenced by addSSTConss(), and propagateOrbitalFixing().
◆ 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-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.
This function is adapted from SCIPcomputeOrbitsFilterSym().
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.
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 411 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 311 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 533 of file symmetry.c.
References NULL, SCIP_OKAY, and SCIPvarIsBinary().
Referenced by chooseOrderOfGenerators(), and detectOrbitopes().
◆ 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 584 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, |
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 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 766 of file symmetry.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPdisjointsetCreate(), SCIPdisjointsetFind(), SCIPdisjointsetFree(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPsortIntInt(), and TRUE.
Referenced by determineSymmetry().
◆ 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 636 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 970 of file symmetry.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPreallocBlockMemoryArray, SCIPvarIsBinary(), and TRUE.
Referenced by addOrbitopeSubgroup(), and detectOrbitopes().
◆ 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 1161 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 packingUpgrade(), and strengthenOrbitopeConstraint().