Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_sassy.cpp File Reference
#include "compute_symmetry.h"
#include <bliss/defs.hh>
#include <bliss/graph.hh>
#include <sassy/preprocessor.h>
#include <sassy/tools/bliss_converter.h>
#include "scip/expr_var.h"
#include "scip/expr_sum.h"
#include "scip/expr_pow.h"
#include "scip/expr.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_linear.h"
#include "scip/scip_mem.h"

Go to the source code of this file.

Data Structures

struct  SYMMETRY_Data
 

Functions

static SCIP_DECL_HASHGETKEY (SYMhashGetKeyOptype)
 
static SCIP_DECL_HASHKEYEQ (SYMhashKeyEQOptype)
 
static SCIP_DECL_HASHKEYVAL (SYMhashKeyValOptype)
 
static SCIP_DECL_HASHGETKEY (SYMhashGetKeyConsttype)
 
static SCIP_DECL_HASHKEYEQ (SYMhashKeyEQConsttype)
 
static SCIP_DECL_HASHKEYVAL (SYMhashKeyValConsttype)
 
static SCIP_DECL_HASHGETKEY (SYMhashGetKeyRhstype)
 
static SCIP_DECL_HASHKEYEQ (SYMhashKeyEQRhstype)
 
static SCIP_DECL_HASHKEYVAL (SYMhashKeyValRhstype)
 
static void sassyhook (void *user_param, int n, const int *aut, int nsupp, const int *suppa)
 
static SCIP_RETCODE determineGraphSize (SCIP *scip, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int *nnodes, int *nedges, int *nlinearnodes, int *nnonlinearnodes, int *nlinearedges, int *nnonlinearedges, int **degrees, int *maxdegrees, SCIP_Bool *success)
 
static SCIP_RETCODE fillGraphByConss (SCIP *scip, sassy::static_graph *G, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int nnodes, int nedges, int nlinearnodes, int nnonlinearnodes, int nlinearedges, int nnonlinearedges, int *degrees, int *nusedcolors)
 
SCIP_Bool SYMcanComputeSymmetry (void)
 
char * initStaticSymmetryName ()
 
char * initStaticSymmetryAddName ()
 
const char * SYMsymmetryGetName (void)
 
const char * SYMsymmetryGetDesc (void)
 
const char * SYMsymmetryGetAddName (void)
 
const char * SYMsymmetryGetAddDesc (void)
 
SCIP_RETCODE SYMcomputeSymmetryGenerators (SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
 

Variables

static const char * symmetryname = initStaticSymmetryName()
 
static const char * symmetryaddname = initStaticSymmetryAddName()
 

Function Documentation

◆ SCIP_DECL_HASHGETKEY() [1/3]

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyOptype  )
static

gets the key of the given element

Definition at line 96 of file compute_symmetry_sassy.cpp.

◆ SCIP_DECL_HASHKEYEQ() [1/3]

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQOptype  )
static

returns TRUE iff both keys are equal

Compare the types of two operators according to their name, level and, in case of power, exponent.

Definition at line 106 of file compute_symmetry_sassy.cpp.

References SYM_Optype::expr, FALSE, SYM_Optype::level, SCIPexprGetHdlr(), SCIPgetExponentExprPow(), SCIPisExprPower(), and TRUE.

◆ SCIP_DECL_HASHKEYVAL() [1/3]

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValOptype  )
static

◆ SCIP_DECL_HASHGETKEY() [2/3]

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyConsttype  )
static

gets the key of the given element

Definition at line 155 of file compute_symmetry_sassy.cpp.

◆ SCIP_DECL_HASHKEYEQ() [2/3]

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQConsttype  )
static

returns TRUE iff both keys are equal

Compare two constants according to their values.

Definition at line 165 of file compute_symmetry_sassy.cpp.

References SCIP_Bool, and SYM_Consttype::value.

◆ SCIP_DECL_HASHKEYVAL() [2/3]

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValConsttype  )
static

returns the hash value of the key

Definition at line 178 of file compute_symmetry_sassy.cpp.

References SCIPrealHashCode(), and SYM_Consttype::value.

◆ SCIP_DECL_HASHGETKEY() [3/3]

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyRhstype  )
static

gets the key of the given element

Definition at line 191 of file compute_symmetry_sassy.cpp.

◆ SCIP_DECL_HASHKEYEQ() [3/3]

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQRhstype  )
static

returns TRUE iff both keys are equal

Compare two constraint sides according to lhs and rhs.

Definition at line 201 of file compute_symmetry_sassy.cpp.

References FALSE, SYM_Rhstype::lhs, SYM_Rhstype::rhs, and SCIP_Bool.

◆ SCIP_DECL_HASHKEYVAL() [3/3]

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValRhstype  )
static

returns the hash value of the key

Definition at line 217 of file compute_symmetry_sassy.cpp.

References SYM_Rhstype::lhs, SYM_Rhstype::rhs, SCIPhashTwo, and SCIPrealHashCode().

◆ sassyhook()

static void sassyhook ( void *  user_param,
int  n,
const int *  aut,
int  nsupp,
const int *  suppa 
)
static

callback function for sassy

Parameters
user_paramparameter supplied at call to sassy
ndimension of permutations
autpermutation
nsuppsupport size
suppasupport list

Definition at line 231 of file compute_symmetry_sassy.cpp.

References SYMMETRY_Data::maxgenerators, SYMMETRY_Data::nmaxperms, SYMMETRY_Data::nperms, SYMMETRY_Data::npermvars, NULL, SYMMETRY_Data::perms, SYMMETRY_Data::scip, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPfreeBlockMemoryArray, and SCIPreallocBlockMemoryArray.

Referenced by SYMcomputeSymmetryGenerators().

◆ determineGraphSize()

static SCIP_RETCODE determineGraphSize ( SCIP scip,
SYM_MATRIXDATA matrixdata,
SYM_EXPRDATA exprdata,
int *  nnodes,
int *  nedges,
int *  nlinearnodes,
int *  nnonlinearnodes,
int *  nlinearedges,
int *  nnonlinearedges,
int **  degrees,
int *  maxdegrees,
SCIP_Bool success 
)
static

determine number of nodes and edges

Parameters
scipSCIP instance
matrixdatadata for MIP matrix
exprdatadata for nonlinear constraints
nnodespointer to store the total number of nodes in graph
nedgespointer to store the total number of edges in graph
nlinearnodespointer to store the number of internal nodes for linear constraints
nnonlinearnodespointer to store the number of internal nodes for nonlinear constraints
nlinearedgespointer to store the number of edges for linear constraints
nnonlinearedgespointer to store the number of edges for nonlinear constraints
degreespointer to store the degrees of the nodes
maxdegreespointer to store the maximal size of the degree array
successpointer to store whether the construction was successful

Definition at line 303 of file compute_symmetry_sassy.cpp.

References FALSE, SYM_Matrixdata::matcoef, SYM_Matrixdata::matcoefcolors, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, nnodes, SYMMETRY_Data::npermvars, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, NULL, SYM_Exprdata::nuniquecoefs, SYM_Exprdata::nuniqueconstants, SYM_Matrixdata::nuniquemat, SYM_Exprdata::nuniqueoperators, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_EXPRITER_LEAVEEXPR, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPensureBlockMemoryArray, SCIPexprGetNChildren(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterGetParentDFS(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPgetConstantExprSum(), SCIPgetExprNonlinear(), SCIPgetNVars(), SCIPgetProbvarLinearSum(), SCIPgetVarExprVar(), SCIPisEQ(), SCIPisExprSum(), SCIPisExprVar(), SCIPvarGetProbindex(), SCIPvarIsActive(), and TRUE.

Referenced by SYMcomputeSymmetryGenerators().

◆ fillGraphByConss()

static SCIP_RETCODE fillGraphByConss ( SCIP scip,
sassy::static_graph *  G,
SYM_MATRIXDATA matrixdata,
SYM_EXPRDATA exprdata,
int  nnodes,
int  nedges,
int  nlinearnodes,
int  nnonlinearnodes,
int  nlinearedges,
int  nnonlinearedges,
int *  degrees,
int *  nusedcolors 
)
static

Construct linear and nonlinear part of colored graph for symmetry computations

Construct linear graph:

  • Each variable gets a different node.
  • Each constraint gets a different node.
  • Each matrix coefficient gets a different node that is connected to the two nodes corresponding to the respective constraint and variable.
  • Each different variable, rhs, matrix coefficient gets a different color that is attached to the corresponding entries.

    Construct nonlinear graph:

  • Each node of the expression trees gets a different node.
  • Each coefficient of a sum expression gets its own node connected to the node of the corresponding child.
  • Each constraint (with lhs and (!) rhs) gets its own node connected to the corresponding node of the root expression.
Note
: In contrast to the linear part, lhs and rhs are treated together here, so that each unique combination of lhs and rhs gets its own node. This makes the implementation a lot simpler with the small downside, that different formulations of the same constraints would not be detected as equivalent, e.g. for 0 <= x1 + x2 <= 1 0 <= x3 + x4 x3 + x4 <= 1 there would be no symmetry between (x1,x2) and (x3,x4) detected.

Each different constraint (sides), sum-expression coefficient, constant and operator type gets a different color that is attached to the corresponding entries.

Parameters
scipSCIP instance
Ggraph to be constructed
matrixdatadata for MIP matrix
exprdatadata for nonlinear constraints
nnodestotal number of nodes in graph
nedgestotal number of edges in graph
nlinearnodesnumber of intermediate nodes for linear constraints
nnonlinearnodesnumber of intermediate nodes for nonlinear constraints
nlinearedgesnumber of intermediate edges for linear constraints
nnonlinearedgesnumber of intermediate edges for nonlinear constraints
degreesarray with the degrees of the nodes
nusedcolorspointer to store number of used colors in the graph so far

Definition at line 822 of file compute_symmetry_sassy.cpp.

References SYM_Optype::expr, FALSE, SYM_Optype::level, SYM_Rhstype::lhs, SYM_Matrixdata::matcoef, SYM_Matrixdata::matcoefcolors, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYMMETRY_Data::npermvars, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, NULL, SYM_Exprdata::nuniquecoefs, SYM_Exprdata::nuniqueconstants, SYM_Matrixdata::nuniquemat, SYM_Exprdata::nuniqueoperators, SYM_Matrixdata::nuniquerhs, SYM_Matrixdata::nuniquevars, SYM_Matrixdata::permvarcolors, SYM_Rhstype::rhs, SYM_Matrixdata::rhscoefcolors, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_EXPRITER_LEAVEEXPR, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPensureBlockMemoryArray, SCIPexprGetNChildren(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterGetParentDFS(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetExprNonlinear(), SCIPgetLhsNonlinear(), SCIPgetNVars(), SCIPgetProbvarLinearSum(), SCIPgetRhsNonlinear(), SCIPgetValueExprValue(), SCIPgetVarExprVar(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPisEQ(), SCIPisExprSum(), SCIPisExprValue(), SCIPisExprVar(), SCIPvarGetProbindex(), SCIPvarIsActive(), TRUE, and SYM_Consttype::value.

Referenced by SYMcomputeSymmetryGenerators().

◆ SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry ( void  )

return whether symmetry can be computed

Definition at line 1493 of file compute_symmetry_sassy.cpp.

References TRUE.

Referenced by computeSymmetryGroup(), determineSymmetry(), and SCIPincludePropSymmetry().

◆ initStaticSymmetryName()

char* initStaticSymmetryName ( )

return name of external program used to compute generators

Definition at line 1500 of file compute_symmetry_sassy.cpp.

References blissname, and SCIPsnprintf().

◆ initStaticSymmetryAddName()

char* initStaticSymmetryAddName ( )

return name of external program used to compute generators

Definition at line 1513 of file compute_symmetry_sassy.cpp.

References SCIPsnprintf().

◆ SYMsymmetryGetName()

const char* SYMsymmetryGetName ( void  )

return name of external program used to compute generators

Definition at line 1524 of file compute_symmetry_sassy.cpp.

References symmetryname.

Referenced by SCIPincludePropSymmetry().

◆ SYMsymmetryGetDesc()

const char* SYMsymmetryGetDesc ( void  )

return description of external program used to compute generators

Definition at line 1530 of file compute_symmetry_sassy.cpp.

Referenced by SCIPincludePropSymmetry().

◆ SYMsymmetryGetAddName()

const char* SYMsymmetryGetAddName ( void  )

return name of additional external program used for computing symmetries

Definition at line 1536 of file compute_symmetry_sassy.cpp.

References symmetryaddname.

Referenced by SCIPincludePropSymmetry().

◆ SYMsymmetryGetAddDesc()

const char* SYMsymmetryGetAddDesc ( void  )

return description of additional external program used to compute symmetries

Definition at line 1542 of file compute_symmetry_sassy.cpp.

Referenced by SCIPincludePropSymmetry().

◆ SYMcomputeSymmetryGenerators()

SCIP_RETCODE SYMcomputeSymmetryGenerators ( SCIP scip,
int  maxgenerators,
SYM_MATRIXDATA matrixdata,
SYM_EXPRDATA exprdata,
int *  nperms,
int *  nmaxperms,
int ***  perms,
SCIP_Real log10groupsize,
SCIP_Real symcodetime 
)

compute generators of symmetry group

Parameters
scipSCIP pointer
maxgeneratorsmaximal number of generators constructed (= 0 if unlimited)
matrixdatadata for MIP matrix
exprdatadata for nonlinear constraints
npermspointer to store number of permutations
nmaxpermspointer to store maximal number of permutations (needed for freeing storage)
permspointer to store permutation generators as (nperms x npermvars) matrix
log10groupsizepointer to store size of group
symcodetimepointer to store the time for symmetry code

Definition at line 1548 of file compute_symmetry_sassy.cpp.

References determineGraphSize(), FALSE, fillGraphByConss(), SYMMETRY_Data::maxgenerators, SYMMETRY_Data::nmaxperms, nnodes, SYMMETRY_Data::nperms, SYMMETRY_Data::npermvars, SYM_Matrixdata::npermvars, NULL, SYMMETRY_Data::perms, sassyhook(), SYMMETRY_Data::scip, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPgetProbName(), SCIPgetSolvingTime(), SCIPsnprintf(), and SCIPverbMessage().

Referenced by computeSymmetryGroup().

Variable Documentation

◆ symmetryname

const char* symmetryname = initStaticSymmetryName()
static

Definition at line 1520 of file compute_symmetry_sassy.cpp.

Referenced by SYMsymmetryGetName().

◆ symmetryaddname

const char* symmetryaddname = initStaticSymmetryAddName()
static

Definition at line 1521 of file compute_symmetry_sassy.cpp.

Referenced by SYMsymmetryGetAddName().