Scippy

SCIP

Solving Constraint Integer Programs

PublicSymmetryMethods

Detailed Description

Functions

SCIP_EXPORT SCIP_RETCODE SCIPcomputeOrbitsSym (SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, int *orbits, int *orbitbegins, int *norbits)
 
SCIP_EXPORT 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, SCIP_Shortbool *componentblocked, int ncomponents, int nmovedpermvars)
 
SCIP_EXPORT 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_EXPORT SCIP_RETCODE SCIPgetPropertiesPerm (int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool *iscompoftwocycles, int *ntwocyclesperm, SCIP_Bool *allvarsbinary)
 
SCIP_EXPORT SCIP_RETCODE SCIPdetermineNVarsAffectedSym (SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
 
SCIP_EXPORT SCIP_RETCODE SCIPcomputeComponentsSym (SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, SCIP_Shortbool **componentblocked, int *ncomponents)
 
SCIP_EXPORT SCIP_RETCODE SCIPextendSubOrbitope (int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_Bool *success, SCIP_Bool *infeasible)
 
SCIP_EXPORT SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix (SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Bool *infeasible)
 

Function Documentation

◆ SCIPcomputeOrbitsSym()

SCIP_EXPORT 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
scipSCIP instance
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 38 of file symmetry.c.

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

◆ SCIPcomputeOrbitsFilterSym()

SCIP_EXPORT 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,
SCIP_Shortbool 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 whether a component is blocked to be considered by further symmetry handling techniques
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 152 of file symmetry.c.

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

Referenced by propagateOrbitalFixing().

◆ SCIPcomputeOrbitsComponentsSym()

SCIP_EXPORT 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
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 304 of file symmetry.c.

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

Referenced by initOrbits().

◆ SCIPgetPropertiesPerm()

SCIP_EXPORT SCIP_RETCODE SCIPgetPropertiesPerm ( int *  perm,
SCIP_VAR **  vars,
int  nvars,
SCIP_Bool iscompoftwocycles,
int *  ntwocyclesperm,
SCIP_Bool allvarsbinary 
)

check whether a permutation is a composition of 2-cycles of binary variables and in this case determine 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 424 of file symmetry.c.

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

Referenced by detectOrbitopes().

◆ SCIPdetermineNVarsAffectedSym()

SCIP_EXPORT 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 478 of file symmetry.c.

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

Referenced by determineSymmetry().

◆ SCIPcomputeComponentsSym()

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

compute components of symmetry group

Parameters
scipSCIP instance
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 whether a component is blocked to be considered by further symmetry handling techniques
ncomponentspointer to store number of components of symmetry group

Definition at line 651 of file symmetry.c.

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

Referenced by determineSymmetry().

◆ SCIPextendSubOrbitope()

SCIP_EXPORT SCIP_RETCODE SCIPextendSubOrbitope ( int **  suborbitope,
int  nrows,
int  nfilledcols,
int  coltoextend,
int *  perm,
SCIP_Bool  leftextension,
int **  nusedelems,
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
successpointer to store whether extension was successful
infeasiblepointer to store if the number of intersecting cycles is too small

Definition at line 530 of file symmetry.c.

References FALSE, NULL, SCIP_OKAY, and TRUE.

Referenced by detectOrbitopes().

◆ SCIPgenerateOrbitopeVarsMatrix()

SCIP_EXPORT SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix ( SCIP_VAR ****  vars,
int  nrows,
int  ncols,
SCIP_VAR **  permvars,
int  npermvars,
int **  orbitopevaridx,
int *  columnorder,
int *  nusedelems,
SCIP_Bool infeasible 
)

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 852 of file symmetry.c.

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

Referenced by detectOrbitopes().