symmetry_graph.c File Reference

Detailed Description

methods for dealing with symmetry detection graphs

Author

Christopher Hojny

Definition in file symmetry_graph.c.

#include "scip/symmetry_graph.h"
#include "scip/scip.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	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_Real *	SCIPgetSymExprdataConstants (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

scip	SCIP data structure
graph	symmetry detection graph
addsize	required 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

scip	SCIP data structure
graph	symmetry detection graph
addsize	required 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

scip	SCIP pointer (or NULL for exact comparison)
var1	first variable for comparison
var2	second 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

scip	SCIP pointer (or NULL for exact comparison)
var1	first variable for comparison
var2	second variable for comparison
isfixed1	whether var1 needs to be fixed
isfixed2	whether 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

scip	SCIP pointer (or NULL for exact comparison)
var1	first variable for comparison
var2	second variable for comparison
isneg1	whether var1 needs to be negated
isneg2	whether var2 needs to be negated
infinity	values as least as large as this are regarded as infinite

Definition at line 807 of file symmetry_graph.c.

References 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

scip	SCIP pointer (or NULL for exact comparison)
var1	first variable for comparison
var2	second variable for comparison
isfixed1	whether var1 needs to be fixed
isfixed2	whether var2 needs to be fixed
isneg1	whether var1 needs to be negated
isneg2	whether var2 needs to be negated
infinity	values as least as large as this are regarded as infinite

Definition at line 936 of file symmetry_graph.c.

References compareVarsSignedPerm(), 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 971 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

op1	first operator in comparison
op2	second operator in comparison

Definition at line 1020 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 1041 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 1058 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

scip	SCIP data structure
graph	underlying symmetry detection graph
ind1	index of first constraint node
ind2	index of second constraint node

Definition at line 1082 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 1143 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 1158 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

var	active problem variable
fixedtype	variable types that must be fixed by symmetries

Definition at line 1174 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().