Detailed Description

methods for creating and manipulating symmetry detection graphs

Below you find a list of functions to create and manipulate symmetry detection graphs.

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	SCIPclearSymgraph (SCIP scip, SYM_GRAPH graph, SCIP_VAR **symvars, int nsymvars, SYM_SYMTYPE symtype)

SCIP_RETCODE	SCIPcopySymgraph (SCIP scip, SYM_GRAPH graph, SYM_GRAPH origgraph, int *perm, SYM_SPEC fixedtype)

SCIP_RETCODE	SCIPcopySymgraphAsSubgraph (SCIP scip, SYM_GRAPH sourcegraph, SYM_GRAPH targetgraph, SCIP_CONS sourcecons, int *rootidx)

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)

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)

SCIP_RETCODE	SCIPaddSymgraphEdge (SCIP scip, SYM_GRAPH graph, int first, int second, SCIP_Bool hasval, SCIP_Real val)

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)

int *	SCIPgetSymgraphConsnodeperm (SCIP scip, SYM_GRAPH graph)

SCIP_RETCODE	SCIPfreeSymgraphConsnodeperm (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

◆ SCIPcreateSymgraph()

SCIP_RETCODE SCIPcreateSymgraph	(	SCIP *	scip,
		SYM_SYMTYPE	symtype,
		SYM_GRAPH **	graph,
		SCIP_VAR **	symvars,
		int	nsymvars,
		int	nopnodes,
		int	nvalnodes,
		int	nconsnodes,
		int	nedges
	)

creates and initializes a symmetry detection graph with memory for the given number of nodes and edges

Note: at some point, the graph needs to be freed!

Parameters

scip	SCIP data structure
symtype	type of symmetries encoded in graph
graph	pointer to hold symmetry detection graph
symvars	variables used in symmetry detection
nsymvars	number of variables used in symmetry detection
nopnodes	number of operator nodes
nvalnodes	number of value nodes
nconsnodes	number of constraint nodes
nedges	number of edges

Definition at line 46 of file symmetry_graph.c.

References FALSE, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemoryArray, and SCIPinfinity().

Referenced by addSymmetryInformation(), checkSymmetriesAreSymmetries(), computeSymmetryGroup(), and SCIPcopySymgraph().

◆ SCIPfreeSymgraph()

SCIP_RETCODE SCIPfreeSymgraph	(	SCIP *	scip,
		SYM_GRAPH **	graph
	)

frees a symmetry detection graph

Parameters

scip	SCIP data structure
graph	pointer to symmetry detection graph

Definition at line 113 of file symmetry_graph.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SYM_SYMTYPE_PERM, and SYM_SYMTYPE_SIGNPERM.

Referenced by addSymmetryInformation(), checkSymmetriesAreSymmetries(), and computeSymmetryGroup().

◆ SCIPclearSymgraph()

SCIP_RETCODE SCIPclearSymgraph	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		SCIP_VAR **	symvars,
		int	nsymvars,
		SYM_SYMTYPE	symtype
	)

clears data of symmetry detection graph

Parameters

scip	SCIP data structure
graph	symmetry detection graph
symvars	variables used in symmetry detection
nsymvars	number of variables used in symmetry detection
symtype	type of symmetries encoded in graph

Definition at line 153 of file symmetry_graph.c.

References SYM_Graph::conscolors, SYM_Graph::consnodeperm, SYM_Graph::edgecolors, FALSE, SYM_Graph::infinity, SYM_Graph::islocked, SYM_Graph::nconsnodes, SYM_Graph::nedges, SYM_Graph::nnodes, SYM_Graph::nopnodes, SYM_Graph::nsymvars, NULL, SYM_Graph::nvalnodes, SYM_Graph::nvarcolors, SYM_Graph::opcolors, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, SCIPinfinity(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, SYM_Graph::symtype, SYM_Graph::symvars, SYM_Graph::uniqueedgetype, SYM_Graph::valcolors, and SYM_Graph::varcolors.

Referenced by addSymmetryInformation().

◆ SCIPcopySymgraph()

SCIP_RETCODE SCIPcopySymgraph	(	SCIP *	scip,
		SYM_GRAPH **	graph,
		SYM_GRAPH *	origgraph,
		int *	perm,
		SYM_SPEC	fixedtype
	)

copies an existing graph and changes variable nodes according to a permutation

Parameters

scip	SCIP data structure
graph	pointer to hold copy of symmetry detection graph
origgraph	graph to be copied
perm	permutation of variables
fixedtype	variable types that must be fixed by symmetries

Definition at line 203 of file symmetry_graph.c.

References SYM_Graph::conss, SYM_Graph::edgevals, SYM_Graph::lhs, SYM_Graph::nconsnodes, SYM_Graph::nedges, nnodes, SYM_Graph::nnodes, SYM_Graph::nodeinfopos, SYM_Graph::nodetypes, SYM_Graph::nopnodes, SYM_Graph::nsymvars, NULL, SYM_Graph::nvalnodes, SYM_Graph::ops, SYM_Graph::rhs, SCIP_CALL, SCIP_OKAY, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPcomputeSymgraphColors(), SCIPcreateSymgraph(), SCIPgetSymgraphEdgeFirst(), SCIPgetSymgraphEdgeSecond(), SCIPisInfinity(), SYM_NODETYPE_CONS, SYM_NODETYPE_OPERATOR, SYM_NODETYPE_VAL, SYM_Graph::symtype, SYM_Graph::symvars, and SYM_Graph::vals.

Referenced by checkSymmetriesAreSymmetries().

◆ SCIPcopySymgraphAsSubgraph()

SCIP_RETCODE SCIPcopySymgraphAsSubgraph	(	SCIP *	scip,
		SYM_GRAPH *	sourcegraph,
		SYM_GRAPH *	targetgraph,
		SCIP_CONS *	sourcecons,
		int *	rootidx
	)

copies a symmetry detection graph into another symmetry detection graph

Parameters

scip	SCIP pointer
sourcegraph	graph to be copied
targetgraph	graph into which copy shall be included
sourcecons	constraint associated with sourcegraph
rootidx	pointer to hold index of root node of sourcegraph in targetgraph (or -1 if root cannot be detected)

Definition at line 272 of file symmetry_graph.c.

References SYM_Graph::conss, SYM_Graph::edgevals, SYM_Graph::lhs, SYM_Graph::nedges, nnodes, SYM_Graph::nnodes, SYM_Graph::nodeinfopos, SYM_Graph::nodetypes, NULL, SYM_Graph::ops, SYM_Graph::rhs, SCIP_CALL, SCIP_OKAY, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetSymgraphEdgeFirst(), SCIPgetSymgraphEdgeSecond(), SCIPisInfinity(), SYM_NODETYPE_CONS, SYM_NODETYPE_OPERATOR, SYM_NODETYPE_VAL, and SYM_Graph::vals.

Referenced by addSymmetryInformation().

◆ SCIPextendPermsymDetectionGraphLinear()

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
	)

adds a symmetry detection graph for a linear constraint to existing graph

For permutation symmetries, a constraint node is added that is connected to all variable nodes in the constraint. Edges are colored according to the variable coefficients. For signed permutation symmetries, also edges connecting the constraint node and the negated variable nodes are added, these edges are colored by the negative coefficients.

Parameters

scip	SCIP data structure
graph	symmetry detection graph
vars	variable array of linear constraint
vals	coefficients of linear constraint
nvars	number of variables in linear constraint
cons	constraint for which we encode symmetries
lhs	left-hand side of constraint
rhs	right-hand side of constraint
success	pointer to store whether graph could be built

Definition at line 376 of file symmetry_graph.c.

References SYM_Graph::islocked, SYM_Graph::nsymvars, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPgetSymgraphSymtype(), SCIPgetSymgraphVarnodeidx(), SCIPvarGetProbindex(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, and TRUE.

Referenced by addSymmetryInformation().

◆ SCIPaddSymgraphVarAggregation()

SCIP_RETCODE SCIPaddSymgraphVarAggregation	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		int	rootidx,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		int	nvars,
		SCIP_Real	constant
	)

adds nodes and edges corresponding to the aggregation of a variable to a symmetry detection graph

For permutation symmetries, the root node is connected with all variable nodes in the aggregation. Edges are colored according to the variable coefficients. For signed permutation symmetries, also edges connecting the root node and the negated variable nodes are added, these edges are colored by the negative coefficients.

adds nodes and edges corresponding to the aggregation of a variable to a symmetry detection graph

For permutation symmetries, the root node is connected with all variable nodes in the aggregation. Edges are colored according to the variable coefficients. For signed permutation symmetries, also edges connecting the root node and the negated variable nodes are added, these edges are colored by the negative coefficients. If the variable is fixed, a node representing the constant value is added.

Parameters

scip	SCIP data structure
graph	symmetry detection graph
rootidx	index of root node of the aggegration
vars	array of variables in aggregation
vals	coefficients of variables
nvars	number of variables in aggregation
constant	constant of aggregation

Definition at line 445 of file symmetry_graph.c.

References FALSE, SYM_Graph::nsymvars, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddSymgraphEdge(), SCIPaddSymgraphValnode(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPgetSymgraphSymtype(), SCIPgetSymgraphVarnodeidx(), SCIPisZero(), SCIPvarGetProbindex(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, and TRUE.

Referenced by addSymmetryInformation(), SCIP_DECL_CONSGETPERMSYMGRAPH(), and SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH().

◆ SCIPaddSymgraphOpnode()

SCIP_RETCODE SCIPaddSymgraphOpnode	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		int	op,
		int *	nodeidx
	)

adds an operator node to a symmetry detection graph and returns its node index

Parameters

scip	SCIP data structure
graph	symmetry detection graph
op	int associated with operator of node
nodeidx	pointer to hold index of created node

Definition at line 533 of file symmetry_graph.c.

References ensureNodeArraysSize(), SYM_Graph::islocked, SYM_Graph::maxnopnodes, SYM_Graph::nnodes, SYM_Graph::nodeinfopos, SYM_Graph::nodetypes, SYM_Graph::nopnodes, NULL, SYM_Graph::ops, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPerrorMessage, SCIPreallocBlockMemoryArray, and SYM_NODETYPE_OPERATOR.

Referenced by addSymmetryInformation(), SCIP_DECL_CONSGETPERMSYMGRAPH(), SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(), SCIPcopySymgraph(), SCIPcopySymgraphAsSubgraph(), tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperatorSum(), tryAddGadgetEvenOperatorVariable(), and tryAddGadgetSquaredDifference().

◆ SCIPaddSymgraphValnode()

SCIP_RETCODE SCIPaddSymgraphValnode	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		SCIP_Real	val,
		int *	nodeidx
	)

adds a value node to a symmetry detection graph and returns its node index

Parameters

scip	SCIP data structure
graph	symmetry detection graph
val	value of node
nodeidx	pointer to hold index of created node

Definition at line 574 of file symmetry_graph.c.

References ensureNodeArraysSize(), SYM_Graph::islocked, SYM_Graph::maxnvalnodes, SYM_Graph::nnodes, SYM_Graph::nodeinfopos, SYM_Graph::nodetypes, NULL, SYM_Graph::nvalnodes, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPerrorMessage, SCIPreallocBlockMemoryArray, SYM_NODETYPE_VAL, and SYM_Graph::vals.

Referenced by addSymmetryInformation(), SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(), SCIPaddSymgraphVarAggregation(), SCIPcopySymgraph(), SCIPcopySymgraphAsSubgraph(), tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperatorSum(), tryAddGadgetEvenOperatorVariable(), and tryAddGadgetSquaredDifference().

◆ SCIPaddSymgraphConsnode()

SCIP_RETCODE SCIPaddSymgraphConsnode	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		SCIP_CONS *	cons,
		SCIP_Real	lhs,
		SCIP_Real	rhs,
		int *	nodeidx
	)

adds a constraint node to a symmetry detection graph and returns its node index

Parameters

scip	SCIP data structure
graph	symmetry detection graph
cons	constraint of node
lhs	left-hand side of node
rhs	right-hand side of node
nodeidx	pointer to hold index of created node

Definition at line 615 of file symmetry_graph.c.

References SYM_Graph::conss, ensureNodeArraysSize(), SYM_Graph::infinity, SYM_Graph::islocked, SYM_Graph::lhs, MAX, SYM_Graph::maxnconsnodes, MIN, SYM_Graph::nconsnodes, SYM_Graph::nnodes, SYM_Graph::nodeinfopos, SYM_Graph::nodetypes, NULL, SYM_Graph::rhs, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPerrorMessage, SCIPreallocBlockMemoryArray, and SYM_NODETYPE_CONS.

Referenced by addSymmetryInformation(), SCIP_DECL_CONSGETPERMSYMGRAPH(), SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(), SCIPcopySymgraph(), SCIPcopySymgraphAsSubgraph(), and SCIPextendPermsymDetectionGraphLinear().

◆ SCIPgetSymgraphVarnodeidx()

int SCIPgetSymgraphVarnodeidx	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		SCIP_VAR *	var
	)

returns the (hypothetical) node index of a variable

Parameters

scip	SCIP data structure
graph	symmetry detection graph
var	variable

Definition at line 663 of file symmetry_graph.c.

References NULL, SCIPvarGetProbindex(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, and SYM_Graph::symtype.

Referenced by addSymmetryInformation(), SCIP_DECL_CONSGETPERMSYMGRAPH(), SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(), SCIPaddSymgraphVarAggregation(), SCIPextendPermsymDetectionGraphLinear(), SCIPgetSymgraphNegatedVarnodeidx(), tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperatorSum(), tryAddGadgetEvenOperatorVariable(), and tryAddGadgetSquaredDifference().

◆ SCIPgetSymgraphNegatedVarnodeidx()

int SCIPgetSymgraphNegatedVarnodeidx	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		SCIP_VAR *	var
	)

returns the (hypothetical) node index of a negated variable

Parameters

scip	SCIP data structure
graph	symmetry detection graph
var	variable

Definition at line 683 of file symmetry_graph.c.

References SYM_Graph::nsymvars, NULL, SCIPgetSymgraphVarnodeidx(), SYM_SYMTYPE_SIGNPERM, and SYM_Graph::symtype.

Referenced by addSymmetryInformation(), SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(), SCIPaddSymgraphVarAggregation(), SCIPextendPermsymDetectionGraphLinear(), tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperatorSum(), tryAddGadgetEvenOperatorVariable(), and tryAddGadgetSquaredDifference().

◆ SCIPupdateSymgraphLhs()

SCIP_RETCODE SCIPupdateSymgraphLhs	(	SYM_GRAPH *	graph,
		int	nodeidx,
		SCIP_Real	newlhs
	)

updates the lhs of a constraint node

Parameters

graph	symmetry detection graph
nodeidx	index of constraint node in graph
newlhs	new left-hand side of node

Definition at line 704 of file symmetry_graph.c.

References SYM_Graph::lhs, SYM_Graph::nodeinfopos, SYM_Graph::nodetypes, NULL, SCIP_OKAY, and SYM_NODETYPE_CONS.

◆ SCIPupdateSymgraphRhs()

SCIP_RETCODE SCIPupdateSymgraphRhs	(	SYM_GRAPH *	graph,
		int	nodeidx,
		SCIP_Real	newrhs
	)

updates the rhs of a constraint node

Parameters

graph	symmetry detection graph
nodeidx	index of constraint node in graph
newrhs	new reft-hand side of node

Definition at line 720 of file symmetry_graph.c.

References SYM_Graph::nodeinfopos, SYM_Graph::nodetypes, NULL, SYM_Graph::rhs, SCIP_OKAY, and SYM_NODETYPE_CONS.

◆ SCIPfixSymgraphVarnode()

SCIP_RETCODE SCIPfixSymgraphVarnode	(	SYM_GRAPH *	graph,
		SCIP_VAR *	var
	)

registers a variable node (corresponding to active variable) to be fixed by symmetry

Parameters

graph	symmetry detection graph
var	active variable that needs to be fixed

Definition at line 736 of file symmetry_graph.c.

References SYM_Graph::isfixedvar, NULL, SCIP_OKAY, SCIPvarGetProbindex(), and TRUE.

◆ SCIPaddSymgraphEdge()

SCIP_RETCODE SCIPaddSymgraphEdge	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		int	first,
		int	second,
		SCIP_Bool	hasval,
		SCIP_Real	val
	)

adds an edge to a symmetry detection graph

Parameters

scip	SCIP data structure
graph	symmetry detection graph
first	first node index of edge
second	second node index of edge
hasval	whether the edge has a value
val	value of the edge (is it has a value)

Definition at line 785 of file symmetry_graph.c.

References SYM_Graph::edgefirst, SYM_Graph::edgesecond, SYM_Graph::edgevals, ensureEdgeArraysSize(), SYM_Graph::islocked, SYM_Graph::nedges, NULL, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIPerrorMessage, and SCIPinfinity().

Referenced by addSymmetryInformation(), SCIP_DECL_CONSGETPERMSYMGRAPH(), SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(), SCIPaddSymgraphVarAggregation(), SCIPcopySymgraph(), SCIPcopySymgraphAsSubgraph(), SCIPextendPermsymDetectionGraphLinear(), tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperatorSum(), tryAddGadgetEvenOperatorVariable(), and tryAddGadgetSquaredDifference().

◆ SCIPcomputeSymgraphColors()

SCIP_RETCODE SCIPcomputeSymgraphColors	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		SYM_SPEC	fixedtype
	)

computes colors of nodes and edges

Colors are detected by sorting different types of nodes (variables, operators, values, and constraint) and edges. If two consecutive nodes of the same type differ (e.g., different variable type), they are assigned a new color.

Parameters

scip	SCIP data structure
graph	symmetry detection graph
fixedtype	variable types that must be fixed by symmetries

Definition at line 1346 of file symmetry_graph.c.

References compareConsnodes(), compareOps(), compareVars(), compareVarsSignedPerm(), SYM_Graph::conscolors, SYM_Graph::edgecolors, FALSE, isFixedVar(), SYM_Graph::isfixedvar, SYM_Graph::islocked, SYM_Graph::nconsnodes, SYM_Graph::nedges, SYM_Graph::nopnodes, SYM_Graph::nsymvars, NULL, SYM_Graph::nvalnodes, SYM_Graph::opcolors, SYM_Graph::ops, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisInfinity(), SCIPsort(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, SYM_Graph::symtype, SYM_Graph::symvars, TRUE, SYM_Graph::valcolors, SYM_Graph::vals, and SYM_Graph::varcolors.

Referenced by checkSymmetriesAreSymmetries(), computeSymmetryGroup(), and SCIPcopySymgraph().

◆ SCIPgetSymgraphSymtype()

SYM_SYMTYPE SCIPgetSymgraphSymtype ( SYM_GRAPH * graph )

returns the type of symmetries encoded in graph

Parameters

graph symmetry detection graph

Definition at line 1587 of file symmetry_graph.c.

References NULL, and SYM_Graph::symtype.

Referenced by createOrDetermineSizeGraph(), createOrDetermineSizeGraphCheck(), SCIPaddSymgraphVarAggregation(), SCIPextendPermsymDetectionGraphLinear(), SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().

int SCIPgetSymgraphEdgeFirst	(	SYM_GRAPH *	graph,
		int	edgeidx
	)

return the first node index of an edge

Parameters

graph	symmetry detection graph
edgeidx	index of edge

Definition at line 1647 of file symmetry_graph.c.

References SYM_Graph::edgefirst, and NULL.

Referenced by createOrDetermineSizeGraph(), createOrDetermineSizeGraphCheck(), isEdgeGroupable(), SCIPcopySymgraph(), SCIPcopySymgraphAsSubgraph(), and SYMcomputeSymmetryGenerators().

◆ SCIPgetSymgraphEdgeSecond()

int SCIPgetSymgraphEdgeSecond	(	SYM_GRAPH *	graph,
		int	edgeidx
	)

return the second node index of an edge

Parameters

graph	symmetry detection graph
edgeidx	index of edge

Definition at line 1659 of file symmetry_graph.c.

References SYM_Graph::edgesecond, and NULL.

Referenced by createOrDetermineSizeGraph(), createOrDetermineSizeGraphCheck(), isEdgeGroupable(), SCIPcopySymgraph(), SCIPcopySymgraphAsSubgraph(), and SYMcomputeSymmetryGenerators().

◆ SCIPgetSymgraphVarnodeColor()

int SCIPgetSymgraphVarnodeColor	(	SYM_GRAPH *	graph,
		int	nodeidx
	)

returns the color of a variable node

Parameters

graph	symmetry detection graph
nodeidx	index of variable node

Definition at line 1671 of file symmetry_graph.c.

References SYM_Graph::islocked, NULL, SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, SYM_Graph::symtype, and SYM_Graph::varcolors.

Referenced by createOrDetermineSizeGraph(), createOrDetermineSizeGraphCheck(), and SYMcomputeSymmetryGenerators().

◆ SCIPgetSymgraphNodeType()

SYM_NODETYPE SCIPgetSymgraphNodeType	(	SYM_GRAPH *	graph,
		int	nodeidx
	)

returns the type of a node

Parameters

graph	symmetry detection graph
nodeidx	index of node

Definition at line 1693 of file symmetry_graph.c.

References nnodes, SYM_Graph::nodetypes, NULL, and SYM_NODETYPE_VAR.

Referenced by createOrDetermineSizeGraph(), createOrDetermineSizeGraphCheck(), isEdgeGroupable(), and SYMcomputeSymmetryGenerators().

◆ SCIPgetSymgraphNodeColor()

int SCIPgetSymgraphNodeColor	(	SYM_GRAPH *	graph,
		int	nodeidx
	)

returns the color of a non-variable node

Parameters

graph	symmetry detection graph
nodeidx	index of node

Definition at line 1708 of file symmetry_graph.c.

References SYM_Graph::conscolors, SYM_Graph::islocked, nnodes, SYM_Graph::nodeinfopos, SYM_Graph::nodetypes, NULL, SYM_Graph::opcolors, SYM_NODETYPE_CONS, SYM_NODETYPE_OPERATOR, SYM_NODETYPE_VAL, and SYM_Graph::valcolors.

Referenced by createOrDetermineSizeGraph(), createOrDetermineSizeGraphCheck(), SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().

◆ SCIPisSymgraphEdgeColored()

SCIP_Bool SCIPisSymgraphEdgeColored	(	SYM_GRAPH *	graph,
		int	edgeidx
	)

returns whether an edge is colored

Parameters

graph	symmetry detection graph
edgeidx	index of edge

Definition at line 1731 of file symmetry_graph.c.

References SYM_Graph::edgecolors, FALSE, SYM_Graph::islocked, NULL, and TRUE.

Referenced by createOrDetermineSizeGraph(), createOrDetermineSizeGraphCheck(), isEdgeGroupable(), SCIPgetSymgraphEdgeColor(), SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().

◆ SCIPgetSymgraphEdgeColor()

int SCIPgetSymgraphEdgeColor	(	SYM_GRAPH *	graph,
		int	edgeidx
	)

returns color of an edge

Parameters

graph	symmetry detection graph
edgeidx	index of edge

Definition at line 1746 of file symmetry_graph.c.

References SYM_Graph::edgecolors, NULL, and SCIPisSymgraphEdgeColored().

Referenced by createOrDetermineSizeGraph(), createOrDetermineSizeGraphCheck(), SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().

◆ SCIPgetSymgraphNVarcolors()

int SCIPgetSymgraphNVarcolors ( SYM_GRAPH * graph )

returns the number of unique variable colors in the graph

Parameters

graph symmetry detection graph

Definition at line 1759 of file symmetry_graph.c.

References SYM_Graph::nsymvars, NULL, and SYM_Graph::nvarcolors.

Referenced by computeSymmetryGroup().

◆ SCIPhasGraphUniqueEdgetype()

SCIP_Bool SCIPhasGraphUniqueEdgetype ( SYM_GRAPH * graph )

returns whether the graph has a unique edge type

Parameters

graph symmetry detection graph

Definition at line 1772 of file symmetry_graph.c.

References NULL, and SYM_Graph::uniqueedgetype.

Referenced by createOrDetermineSizeGraph(), createOrDetermineSizeGraphCheck(), and SYMcomputeSymmetryGenerators().

◆ SCIPcreateSymgraphConsnodeperm()

SCIP_RETCODE SCIPcreateSymgraphConsnodeperm	(	SCIP *	scip,
		SYM_GRAPH *	graph
	)

creates consnodeperm array for symmetry detection graph

Note: colors of symmetry detection graph must have been computed

Parameters

scip	SCIP data structure
graph	symmetry detection graph

Definition at line 1785 of file symmetry_graph.c.

References SYM_Graph::consnodeperm, SYM_Graph::islocked, SYM_Graph::nconsnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and SCIPsort().

Referenced by checkSymmetriesAreSymmetries(), and SCIPgetSymgraphConsnodeperm().

◆ SCIPgetSymgraphConsnodeperm()

int * SCIPgetSymgraphConsnodeperm	(	SCIP *	scip,
		SYM_GRAPH *	graph
	)

returns consnodeperm array for symmetry detection graph

Note: colors of symmetry detection graph must have been computed

Parameters

scip	SCIP data structure
graph	symmetry detection graph

Definition at line 1823 of file symmetry_graph.c.

References SYM_Graph::consnodeperm, SYM_Graph::islocked, NULL, SCIP_CALL_ABORT, and SCIPcreateSymgraphConsnodeperm().

◆ SCIPfreeSymgraphConsnodeperm()

SCIP_RETCODE SCIPfreeSymgraphConsnodeperm	(	SCIP *	scip,
		SYM_GRAPH *	graph
	)

frees consnodeperm array for symmetry detection graph

Parameters

scip	SCIP data structure
graph	symmetry detection graph

Definition at line 1805 of file symmetry_graph.c.

References SYM_Graph::consnodeperm, SYM_Graph::islocked, SYM_Graph::nconsnodes, NULL, SCIP_OKAY, and SCIPfreeBlockMemoryArrayNull.

Referenced by checkSymmetriesAreSymmetries().

◆ SCIPgetSymActiveVariables()

SCIP_RETCODE SCIPgetSymActiveVariables	(	SCIP *	scip,
		SYM_SYMTYPE	symtype,
		SCIP_VAR ***	vars,
		SCIP_Real **	scalars,
		int *	nvars,
		SCIP_Real *	constant,
		SCIP_Bool	transformed
	)

Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.

For permutation symmetries, active variables as encoded in SCIP are used. For signed permutation symmetries, active variables are shifted such that their domain is centered at 0 (if both their upper and lower bounds are finite).

Note: constant needs to be initialized!

Parameters

scip	SCIP data structure
symtype	type of symmetries for which variables are required
vars	pointer to vars array to get active variables for
scalars	pointer to scalars a_1, ..., a_n in linear sum a_1x_1 + ... + a_nx_n + c
nvars	pointer to number of variables and values in vars and vals array
constant	pointer to constant c in linear sum a_1x_1 + ... + a_nx_n + c
transformed	transformed constraint?

Definition at line 1845 of file symmetry_graph.c.

References NULL, scalars, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetProbvarLinearSum(), SCIPisInfinity(), SCIPreallocBufferArray, SCIPvarGetLbGlobal(), SCIPvarGetOrigvarSum(), SCIPvarGetUbGlobal(), and SYM_SYMTYPE_SIGNPERM.

Referenced by addSymmetryInformation(), SCIP_DECL_CONSGETPERMSYMGRAPH(), SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(), tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperatorSum(), tryAddGadgetEvenOperatorVariable(), and tryAddGadgetSquaredDifference().

◆ SCIPfreeSymDataExpr()

SCIP_RETCODE SCIPfreeSymDataExpr	(	SCIP *	scip,
		SYM_EXPRDATA **	symdata
	)

frees symmetry information of an expression

Parameters

scip	SCIP data structure
symdata	symmetry information of an expression

Definition at line 1909 of file symmetry_graph.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArrayNull.

Referenced by addSymmetryInformation(), isEvenOperator(), SCIPgetCoefSymData(), tryAddGadgetBilinearProductSignedPerm(), and tryAddGadgetSquaredDifference().

◆ SCIPgetSymExprdataNConstants()

int SCIPgetSymExprdataNConstants ( SYM_EXPRDATA * symdata )

returns number of coefficients from exprdata

Parameters

symdata symmetry information of an expression

Definition at line 1932 of file symmetry_graph.c.

References SYM_ExprData::nconstants, and NULL.

Referenced by addSymmetryInformation(), isEvenOperator(), tryAddGadgetBilinearProductSignedPerm(), and tryAddGadgetSquaredDifference().

◆ SCIPgetSymExprdataConstants()

SCIP_Real * SCIPgetSymExprdataConstants ( SYM_EXPRDATA * symdata )

returns number of coefficients form exprdata

Parameters

symdata symmetry information of an expression

Definition at line 1942 of file symmetry_graph.c.

References SYM_ExprData::constants, and NULL.

Referenced by addSymmetryInformation(), isEvenOperator(), tryAddGadgetBilinearProductSignedPerm(), and tryAddGadgetSquaredDifference().

◆ SCIPgetCoefSymData()

SCIP_RETCODE SCIPgetCoefSymData	(	SCIP *	scip,
		SCIP_EXPR *	expr,
		SCIP_EXPR *	parentexpr,
		SCIP_Real *	coef,
		SCIP_Bool *	success
	)

gets coefficient of expression from parent expression

Parameters

scip	SCIP data structure
expr	expression for which coefficient needs to be found
parentexpr	parent of expr
coef	buffer to store coefficient
success	whether a coefficient is found

Definition at line 1952 of file symmetry_graph.c.

References SYM_ExprData::children, SYM_ExprData::coefficients, FALSE, SYM_ExprData::ncoefficients, NULL, SCIP_CALL, SCIP_OKAY, SCIPexprGetHdlr(), SCIPexprhdlrHasGetSymData(), SCIPfreeSymDataExpr(), SCIPgetSymDataExpr(), and TRUE.

Referenced by addSymmetryInformation().

SCIP

Detailed Description

Functions

Function Documentation

◆ SCIPcreateSymgraph()

◆ SCIPfreeSymgraph()

◆ SCIPclearSymgraph()

◆ SCIPcopySymgraph()

◆ SCIPcopySymgraphAsSubgraph()

◆ SCIPextendPermsymDetectionGraphLinear()

◆ SCIPaddSymgraphVarAggregation()

◆ SCIPaddSymgraphOpnode()

◆ SCIPaddSymgraphValnode()

◆ SCIPaddSymgraphConsnode()

◆ SCIPgetSymgraphVarnodeidx()

◆ SCIPgetSymgraphNegatedVarnodeidx()

◆ SCIPupdateSymgraphLhs()

◆ SCIPupdateSymgraphRhs()

◆ SCIPfixSymgraphVarnode()

◆ SCIPaddSymgraphEdge()

◆ SCIPcomputeSymgraphColors()

◆ SCIPgetSymgraphSymtype()

◆ SCIPgetSymgraphVars()

◆ SCIPgetSymgraphNVars()

◆ SCIPgetSymgraphNConsnodes()

◆ SCIPgetSymgraphNNodes()

◆ SCIPgetSymgraphNEdges()

◆ SCIPgetSymgraphEdgeFirst()

◆ SCIPgetSymgraphEdgeSecond()

◆ SCIPgetSymgraphVarnodeColor()

◆ SCIPgetSymgraphNodeType()

◆ SCIPgetSymgraphNodeColor()

◆ SCIPisSymgraphEdgeColored()

◆ SCIPgetSymgraphEdgeColor()

◆ SCIPgetSymgraphNVarcolors()

◆ SCIPhasGraphUniqueEdgetype()

◆ SCIPcreateSymgraphConsnodeperm()

◆ SCIPgetSymgraphConsnodeperm()

◆ SCIPfreeSymgraphConsnodeperm()

◆ SCIPgetSymActiveVariables()

◆ SCIPfreeSymDataExpr()

◆ SCIPgetSymExprdataNConstants()

◆ SCIPgetSymExprdataConstants()

◆ SCIPgetCoefSymData()