Symmetry

Detailed Description

methods for symmetry handling

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

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

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 whether a component is blocked to be considered by further symmetry handling techniques
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 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

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

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

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

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 whether a component is blocked to be considered by further symmetry handling techniques
ncomponents	pointer 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

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

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

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

Referenced by detectOrbitopes().