Scippy

SCIP

Solving Constraint Integer Programs

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_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
permpermutation
permlennumber of original (non-negated) variables in a permutation
isinvolutionpointer to store whether perm is an involution
ntwocyclespointer to store number of 2-cycles in an involution

Definition at line 1389 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
scipSCIP pointer
permsarray of permutations
selectedpermsindices of permutations in perm that shall be considered
nselectedpermsnumber of permutations in selectedperms
permlennumber of variables in a permutation
nrowsnumber of rows of potential orbitopal symmetries
successpointer to store if orbitopal symmetries could be found
matricespointer to store matrices of orbitopal symmetries
ncolspointer to store number of columns of matrices in matrices
nmatricespointer to store the number of matrices in matrices

Definition at line 1423 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
scipSCIP pointer
nsymvarsnumber of variables on which symmetries act
matrices1first list of matrices associated with orbitopal symmetries
nrows1number of rows of first family of matrices
ncols1for each matrix in the first family, its number of columns
nmatrices1number of matrices in the first family
matrices2second list of matrices associated with orbitopal symmetries
nrows2number of rows of second family of matrices
ncols2for each matrix in the second family, its number of columns
nmatrices2number of matrices in the second family
doublelexmatrixpointer to store combined matrix
nrowspointer to store number of rows in combined matrix
ncolspointer to store number of columns in combined matrix
rowsbeginpointer to store the begin positions of a new lex subset of rows
colsbeginpointer to store the begin positions of a new lex subset of columns
successpointer to store whether combined matrix could be generated

Definition at line 1796 of file symmetry.c.

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

Referenced by SCIPdetectSingleOrDoubleLexMatrices().