Detailed Description

methods for dealing with symmetry detection graphs

Author: Christopher Hojny

#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

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

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

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

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

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

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

Parameters

op1	first operator in comparison
op2	second 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

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

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

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

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

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

var	active problem variable
fixedtype	variable 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().

SCIP

Detailed Description

Functions

Function Documentation

◆ ensureNodeArraysSize()

◆ ensureEdgeArraysSize()

◆ compareVars()

◆ compareVarsFixed()

◆ SCIP_DECL_SORTINDCOMP() [1/6]

◆ compareVarsSignedPerm()

◆ compareVarsFixedSignedPerm()

◆ SCIP_DECL_SORTINDCOMP() [2/6]

◆ compareOps()

◆ SCIP_DECL_SORTINDCOMP() [3/6]

◆ SCIP_DECL_SORTINDCOMP() [4/6]

◆ compareConsnodes()

◆ SCIP_DECL_SORTINDCOMP() [5/6]

◆ SCIP_DECL_SORTINDCOMP() [6/6]

◆ isFixedVar()