Scippy

SCIP

Solving Constraint Integer Programs

symmetry_graph.c File Reference

Detailed Description

methods for dealing with symmetry detection graphs

Author
Christopher Hojny

Definition in file symmetry_graph.c.

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPcreateSymgraph (SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH **graph, SCIP_VAR **symvars, int nsymvars, int nopnodes, int nvalnodes, int nconsnodes, int nedges)
 
SCIP_RETCODE SCIPfreeSymgraph (SCIP *scip, SYM_GRAPH **graph)
 
SCIP_RETCODE SCIPcopySymgraph (SCIP *scip, SYM_GRAPH **graph, SYM_GRAPH *origgraph, int *perm, SYM_SPEC fixedtype)
 
SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear (SCIP *scip, SYM_GRAPH *graph, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool *success)
 
SCIP_RETCODE SCIPaddSymgraphVarAggregation (SCIP *scip, SYM_GRAPH *graph, int rootidx, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real constant)
 
static SCIP_RETCODE ensureNodeArraysSize (SCIP *scip, SYM_GRAPH *graph, int addsize)
 
SCIP_RETCODE SCIPaddSymgraphOpnode (SCIP *scip, SYM_GRAPH *graph, int op, int *nodeidx)
 
SCIP_RETCODE SCIPaddSymgraphValnode (SCIP *scip, SYM_GRAPH *graph, SCIP_Real val, int *nodeidx)
 
SCIP_RETCODE SCIPaddSymgraphConsnode (SCIP *scip, SYM_GRAPH *graph, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, int *nodeidx)
 
int SCIPgetSymgraphVarnodeidx (SCIP *scip, SYM_GRAPH *graph, SCIP_VAR *var)
 
int SCIPgetSymgraphNegatedVarnodeidx (SCIP *scip, SYM_GRAPH *graph, SCIP_VAR *var)
 
SCIP_RETCODE SCIPupdateSymgraphLhs (SYM_GRAPH *graph, int nodeidx, SCIP_Real newlhs)
 
SCIP_RETCODE SCIPupdateSymgraphRhs (SYM_GRAPH *graph, int nodeidx, SCIP_Real newrhs)
 
SCIP_RETCODE SCIPfixSymgraphVarnode (SYM_GRAPH *graph, SCIP_VAR *var)
 
static SCIP_RETCODE ensureEdgeArraysSize (SCIP *scip, SYM_GRAPH *graph, int addsize)
 
SCIP_RETCODE SCIPaddSymgraphEdge (SCIP *scip, SYM_GRAPH *graph, int first, int second, SCIP_Bool hasval, SCIP_Real val)
 
static int compareVars (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2)
 
static int compareVarsFixed (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Bool isfixed1, SCIP_Bool isfixed2)
 
static SCIP_DECL_SORTINDCOMP (SYMsortVarnodesPermsym)
 
static int compareVarsSignedPerm (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Bool isneg1, SCIP_Bool isneg2, SCIP_Real infinity)
 
static int compareVarsFixedSignedPerm (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Bool isfixed1, SCIP_Bool isfixed2, SCIP_Bool isneg1, SCIP_Bool isneg2, SCIP_Real infinity)
 
static SCIP_DECL_SORTINDCOMP (SYMsortVarnodesSignedPermsym)
 
static int compareOps (int op1, int op2)
 
static SCIP_DECL_SORTINDCOMP (SYMsortOpnodes)
 
static SCIP_DECL_SORTINDCOMP (SYMsortReals)
 
static int compareConsnodes (SCIP *scip, SYM_GRAPH *graph, int ind1, int ind2)
 
static SCIP_DECL_SORTINDCOMP (SYMsortConsnodes)
 
static SCIP_DECL_SORTINDCOMP (SYMsortEdges)
 
static SCIP_Bool isFixedVar (SCIP_VAR *var, SYM_SPEC fixedtype)
 
SCIP_RETCODE SCIPcomputeSymgraphColors (SCIP *scip, SYM_GRAPH *graph, SYM_SPEC fixedtype)
 
SYM_SYMTYPE SCIPgetSymgraphSymtype (SYM_GRAPH *graph)
 
SCIP_VAR ** SCIPgetSymgraphVars (SYM_GRAPH *graph)
 
int SCIPgetSymgraphNVars (SYM_GRAPH *graph)
 
int SCIPgetSymgraphNConsnodes (SYM_GRAPH *graph)
 
int SCIPgetSymgraphNNodes (SYM_GRAPH *graph)
 
int SCIPgetSymgraphNEdges (SYM_GRAPH *graph)
 
int SCIPgetSymgraphEdgeFirst (SYM_GRAPH *graph, int edgeidx)
 
int SCIPgetSymgraphEdgeSecond (SYM_GRAPH *graph, int edgeidx)
 
int SCIPgetSymgraphVarnodeColor (SYM_GRAPH *graph, int nodeidx)
 
SYM_NODETYPE SCIPgetSymgraphNodeType (SYM_GRAPH *graph, int nodeidx)
 
int SCIPgetSymgraphNodeColor (SYM_GRAPH *graph, int nodeidx)
 
SCIP_Bool SCIPisSymgraphEdgeColored (SYM_GRAPH *graph, int edgeidx)
 
int SCIPgetSymgraphEdgeColor (SYM_GRAPH *graph, int edgeidx)
 
int SCIPgetSymgraphNVarcolors (SYM_GRAPH *graph)
 
SCIP_Bool SCIPhasGraphUniqueEdgetype (SYM_GRAPH *graph)
 
SCIP_RETCODE SCIPcreateSymgraphConsnodeperm (SCIP *scip, SYM_GRAPH *graph)
 
SCIP_RETCODE SCIPfreeSymgraphConsnodeperm (SCIP *scip, SYM_GRAPH *graph)
 
int * SCIPgetSymgraphConsnodeperm (SCIP *scip, SYM_GRAPH *graph)
 
SCIP_RETCODE SCIPgetSymActiveVariables (SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
 
SCIP_RETCODE SCIPfreeSymDataExpr (SCIP *scip, SYM_EXPRDATA **symdata)
 
int SCIPgetSymExprdataNConstants (SYM_EXPRDATA *symdata)
 
SCIP_RealSCIPgetSymExprdataConstants (SYM_EXPRDATA *symdata)
 
SCIP_RETCODE SCIPgetCoefSymData (SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *parentexpr, SCIP_Real *coef, SCIP_Bool *success)
 

Function Documentation

◆ ensureNodeArraysSize()

static SCIP_RETCODE ensureNodeArraysSize ( SCIP scip,
SYM_GRAPH graph,
int  addsize 
)
static

ensures that the node-based arrays in symmetry graph are sufficiently long

Parameters
scipSCIP data structure
graphsymmetry detection graph
addsizerequired additional size of node-based arrays

Definition at line 358 of file symmetry_graph.c.

References SYM_Graph::maxnnodes, SYM_Graph::nnodes, SYM_Graph::nodeinfopos, SYM_Graph::nodetypes, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by SCIPaddSymgraphConsnode(), SCIPaddSymgraphOpnode(), and SCIPaddSymgraphValnode().

◆ ensureEdgeArraysSize()

static SCIP_RETCODE ensureEdgeArraysSize ( SCIP scip,
SYM_GRAPH graph,
int  addsize 
)
static

ensures that the edge-based arrays in symmetry graph are sufficiently long

Parameters
scipSCIP data structure
graphsymmetry detection graph
addsizerequired additional size of edge-based arrays

Definition at line 609 of file symmetry_graph.c.

References SYM_Graph::edgefirst, SYM_Graph::edgesecond, SYM_Graph::edgevals, SYM_Graph::maxnedges, SYM_Graph::nedges, NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by SCIPaddSymgraphEdge().

◆ compareVars()

static int compareVars ( SCIP scip,
SCIP_VAR var1,
SCIP_VAR var2 
)
static

compares two variables for permutation symmetry detection

Variables are sorted first by their type, then by their objective coefficient, then by their lower bound, and then by their upper bound.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Parameters
scipSCIP pointer (or NULL for exact comparison)
var1first variable for comparison
var2second variable for comparison

Definition at line 682 of file symmetry_graph.c.

References NULL, SCIPisGT(), SCIPisLT(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

Referenced by compareVarsFixed(), and SCIPcomputeSymgraphColors().

◆ compareVarsFixed()

static int compareVarsFixed ( SCIP scip,
SCIP_VAR var1,
SCIP_VAR var2,
SCIP_Bool  isfixed1,
SCIP_Bool  isfixed2 
)
static

compares two variables for permutation symmetry detection

Variables are sorted first by whether they are fixed, then by their type, then by their objective coefficient, then by their lower bound, and then by their upper bound.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Parameters
scipSCIP pointer (or NULL for exact comparison)
var1first variable for comparison
var2second variable for comparison
isfixed1whether var1 needs to be fixed
isfixed2whether var2 needs to be fixed

Definition at line 746 of file symmetry_graph.c.

References compareVars(), and NULL.

Referenced by SCIP_DECL_SORTINDCOMP().

◆ SCIP_DECL_SORTINDCOMP() [1/6]

static SCIP_DECL_SORTINDCOMP ( SYMsortVarnodesPermsym  )
static

sorts nodes of a permutation symmetry detection graph

Variables are sorted first by whether they are fixed, then by their type, then by their objective coefficient, then by their lower bound, and then by their upper bound.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Definition at line 776 of file symmetry_graph.c.

References compareVarsFixed(), SYM_Graph::isfixedvar, NULL, SCIP_Bool, and SYM_Graph::symvars.

◆ compareVarsSignedPerm()

static int compareVarsSignedPerm ( SCIP scip,
SCIP_VAR var1,
SCIP_VAR var2,
SCIP_Bool  isneg1,
SCIP_Bool  isneg2,
SCIP_Real  infinity 
)
static

compares two variables for signed permutation symmetry detection

Variables are sorted first by their type, then by their objective coefficient, then by their lower bound, and then by their upper bound. To take signed permutations into account, variable domains are centered at origin if the domain is finite.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Parameters
scipSCIP pointer (or NULL for exact comparison)
var1first variable for comparison
var2second variable for comparison
isneg1whether var1 needs to be negated
isneg2whether var2 needs to be negated
infinityvalues as least as large as this are regarded as infinite

Definition at line 807 of file symmetry_graph.c.

References infinity, NULL, SCIP_Real, SCIPisGT(), SCIPisLT(), SCIPvarGetLbGlobal(), SCIPvarGetObj(), SCIPvarGetType(), and SCIPvarGetUbGlobal().

Referenced by compareVarsFixedSignedPerm(), and SCIPcomputeSymgraphColors().

◆ compareVarsFixedSignedPerm()

static int compareVarsFixedSignedPerm ( SCIP scip,
SCIP_VAR var1,
SCIP_VAR var2,
SCIP_Bool  isfixed1,
SCIP_Bool  isfixed2,
SCIP_Bool  isneg1,
SCIP_Bool  isneg2,
SCIP_Real  infinity 
)
static

compares two variables for signed permutation symmetry detection

Variables are sorted first by whether they are fixed, then by their type, then by their objective coefficient, then by their lower bound and then by their upper bound. To take signed permutations into account, variable domains are centered at origin if the domain is finite.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Parameters
scipSCIP pointer (or NULL for exact comparison)
var1first variable for comparison
var2second variable for comparison
isfixed1whether var1 needs to be fixed
isfixed2whether var2 needs to be fixed
isneg1whether var1 needs to be negated
isneg2whether var2 needs to be negated
infinityvalues as least as large as this are regarded as infinite

Definition at line 925 of file symmetry_graph.c.

References compareVarsSignedPerm(), infinity, and NULL.

Referenced by SCIP_DECL_SORTINDCOMP().

◆ SCIP_DECL_SORTINDCOMP() [2/6]

static SCIP_DECL_SORTINDCOMP ( SYMsortVarnodesSignedPermsym  )
static

sorts nodes of a signed permutation symmetry detection graph

Variables are sorted first by whether they are fixed, then by their type, then by their objective coefficient, then by their lower bound and then by their upper bound. To take signed permutations into account, variable domains are centered at origin if the domain is finite.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Definition at line 960 of file symmetry_graph.c.

References compareVarsFixedSignedPerm(), FALSE, SYM_Graph::infinity, SYM_Graph::isfixedvar, SYM_Graph::nsymvars, NULL, SCIP_Bool, SYM_Graph::symvars, and TRUE.

◆ compareOps()

static int compareOps ( int  op1,
int  op2 
)
static

compares two operators

Operators are sorted by their int values.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Parameters
op1first operator in comparison
op2second operator in comparison

Definition at line 1009 of file symmetry_graph.c.

Referenced by SCIP_DECL_SORTINDCOMP(), and SCIPcomputeSymgraphColors().

◆ SCIP_DECL_SORTINDCOMP() [3/6]

static SCIP_DECL_SORTINDCOMP ( SYMsortOpnodes  )
static

sorts operators corresponding to SCIP_EXPRHDLR*

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Definition at line 1030 of file symmetry_graph.c.

References compareOps().

◆ SCIP_DECL_SORTINDCOMP() [4/6]

static SCIP_DECL_SORTINDCOMP ( SYMsortReals  )
static

sorts real values

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Definition at line 1047 of file symmetry_graph.c.

References SCIP_Real.

◆ compareConsnodes()

static int compareConsnodes ( SCIP scip,
SYM_GRAPH graph,
int  ind1,
int  ind2 
)
static

compares constraint nodes

Nodes are sorted by their type of constraint, then by the lhs, and then by the rhs.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Parameters
scipSCIP data structure
graphunderlying symmetry detection graph
ind1index of first constraint node
ind2index of second constraint node

Definition at line 1071 of file symmetry_graph.c.

References SYM_Graph::conss, SYM_Graph::lhs, NULL, SYM_Graph::rhs, SCIPconsGetHdlr(), SCIPisGT(), and SCIPisLT().

Referenced by SCIP_DECL_SORTINDCOMP(), and SCIPcomputeSymgraphColors().

◆ SCIP_DECL_SORTINDCOMP() [5/6]

static SCIP_DECL_SORTINDCOMP ( SYMsortConsnodes  )
static

sorts constraint nodes

Nodes are sorted by their type of constraint, then by the lhs, and then by the rhs.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Definition at line 1132 of file symmetry_graph.c.

References compareConsnodes(), and NULL.

◆ SCIP_DECL_SORTINDCOMP() [6/6]

static SCIP_DECL_SORTINDCOMP ( SYMsortEdges  )
static

sorts edges

Edges are sorted by their weights.

result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value

‍0: ind2 comes after (is worse than) ind2

Definition at line 1147 of file symmetry_graph.c.

References SYM_Graph::edgevals.

◆ isFixedVar()

static SCIP_Bool isFixedVar ( SCIP_VAR var,
SYM_SPEC  fixedtype 
)
static

returns whether a node of the symmetry detection graph needs to be fixed

Parameters
varactive problem variable
fixedtypevariable types that must be fixed by symmetries

Definition at line 1163 of file symmetry_graph.c.

References FALSE, NULL, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.

Referenced by SCIPcomputeSymgraphColors().