Detailed Description

methods for handling symmetries

Author: Jasper van Doornmalen; Christopher Hojny; Marc Pfetsch

Definition in file symmetry.c.

#include "scip/symmetry.h"
#include "scip/scip.h"
#include "scip/cons_setppc.h"
#include "scip/cons_orbitope.h"
#include "scip/misc.h"
#include "symmetry/struct_symmetry.h"
#include "symmetry/type_symmetry.h"

Go to the source code of this file.

Functions
SCIP_VARTYPE	SCIPgetSymInferredVarType (SCIP_VAR *var)

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

static SCIP_RETCODE	isPermInvolution (int perm, int permlen, SCIP_Bool isinvolution, int *ntwocycles)

static SCIP_RETCODE	detectOrbitopalSymmetries (SCIP scip, int perms, int selectedperms, int nselectedperms, int permlen, int nrows, SCIP_Bool success, int *matrices, int ncols, int *nmatrices)

static SCIP_RETCODE	isDoublelLexSym (SCIP scip, int nsymvars, int *matrices1, int nrows1, int ncols1, int nmatrices1, int **matrices2, int nrows2, int ncols2, int nmatrices2, int **doublelexmatrix, int nrows, int ncols, int rowsbegin, int colsbegin, SCIP_Bool success)

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

◆ isPermInvolution()

static SCIP_RETCODE isPermInvolution	(	int *	perm,
		int	permlen,
		SCIP_Bool *	isinvolution,
		int *	ntwocycles
	)

static

checks whether a (signed) permutation is an involution

Parameters

perm	permutation
permlen	number of original (non-negated) variables in a permutation
isinvolution	pointer to store whether perm is an involution
ntwocycles	pointer to store number of 2-cycles in an involution

Definition at line 1404 of file symmetry.c.

References FALSE, NULL, SCIP_OKAY, and TRUE.

Referenced by SCIPdetectSingleOrDoubleLexMatrices().

◆ detectOrbitopalSymmetries()

static SCIP_RETCODE detectOrbitopalSymmetries	(	SCIP *	scip,
		int **	perms,
		int *	selectedperms,
		int	nselectedperms,
		int	permlen,
		int	nrows,
		SCIP_Bool *	success,
		int ****	matrices,
		int **	ncols,
		int *	nmatrices
	)

static

checks whether selected permutations define orbitopal symmetries

Parameters

scip	SCIP pointer
perms	array of permutations
selectedperms	indices of permutations in perm that shall be considered
nselectedperms	number of permutations in selectedperms
permlen	number of variables in a permutation
nrows	number of rows of potential orbitopal symmetries
success	pointer to store if orbitopal symmetries could be found
matrices	pointer to store matrices of orbitopal symmetries
ncols	pointer to store number of columns of matrices in matrices
nmatrices	pointer to store the number of matrices in matrices

Definition at line 1438 of file symmetry.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetUnion(), SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPfreeDisjointset(), SCIPsortIntInt(), SCIPsortIntIntInt(), TRUE, and w.

Referenced by SCIPdetectSingleOrDoubleLexMatrices().

◆ isDoublelLexSym()

static SCIP_RETCODE isDoublelLexSym	(	SCIP *	scip,
		int	nsymvars,
		int ***	matrices1,
		int	nrows1,
		int *	ncols1,
		int	nmatrices1,
		int ***	matrices2,
		int	nrows2,
		int *	ncols2,
		int	nmatrices2,
		int ***	doublelexmatrix,
		int *	nrows,
		int *	ncols,
		int **	rowsbegin,
		int **	colsbegin,
		SCIP_Bool *	success
	)

static

checks whether two families of orbitopal symmetries define a double lex matrix, and in case of success, generates matrix

The columns of matrix1 will serve as the columns of the matrix to be generated, the columns of matrix2 will serve as rows.

Parameters

scip	SCIP pointer
nsymvars	number of variables on which symmetries act
matrices1	first list of matrices associated with orbitopal symmetries
nrows1	number of rows of first family of matrices
ncols1	for each matrix in the first family, its number of columns
nmatrices1	number of matrices in the first family
matrices2	second list of matrices associated with orbitopal symmetries
nrows2	number of rows of second family of matrices
ncols2	for each matrix in the second family, its number of columns
nmatrices2	number of matrices in the second family
doublelexmatrix	pointer to store combined matrix
nrows	pointer to store number of rows in combined matrix
ncols	pointer to store number of columns in combined matrix
rowsbegin	pointer to store the begin positions of a new lex subset of rows
colsbegin	pointer to store the begin positions of a new lex subset of columns
success	pointer to store whether combined matrix could be generated

Definition at line 1811 of file symmetry.c.

References FALSE, MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPsortIntInt(), SCIPsortIntPtr(), and TRUE.

Referenced by SCIPdetectSingleOrDoubleLexMatrices().

SCIP

Detailed Description

Functions

Function Documentation

◆ isPermInvolution()

◆ detectOrbitopalSymmetries()

◆ isDoublelLexSym()