# SCIP

Solving Constraint Integer Programs

^V\}.] Suppose a user wants to implement a constraint handler cons_stableset that enforces a solution to define a stable set in $$G$$, e.g., by propagation methods and separating edge and clique inequalities. Then, the symmetries of the constraint are the weight-preserving automorphisms of the underlying graph $$G$$. The symmetry detection graph thus can be almost a copy of $$G$$.

In our construction, we introduce for each node $$v$$ of the graph an operator node $$v'$$. Moreover, for each edge $$\{u,v\}\in E$$, we add the edges $$\{u',v'\}$$ to the symmetry detection graph. To identify the symmetry detection graph as derived from cons_stableset, we add a constraint node that is connected with all operator nodes, which preserves the automorphisms of $$G$$. Finally, each node $$v'$$ is connected with the corresponding variable node for $$x_v$$ by an edge.

In the following, we present a code snippet showing how to implement the above mentioned symmetry detection graph. We assume that the constraint data consdata contains the following fields

• nnodes number of nodes in graph;
• nedges number of edges in graph;
• first array containing the first nodes of each edge;
• second array containing the second nodes of each edge;
• weights array containing for each node its corresponding weight;
• vars array containing a binary variable for each node modeling whether node is present in stable set.

The code for creating the symmetry detection callback could then look like this.

#define NODEOP 1
static
SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphStableSet)
{
SCIP_CONSDATA* consdata;
int* idx;
int vidx;
int nnodes;
int v;
consdata = SCIPconsGetData(cons);
nnodes = consdata->nnodes;
SCIP_CALL( SCIPallocBufferArray(scip, &idx, nnodes + 1) );
// create operator nodes and constraint node
for( v = 0; v < nnodes; ++v )
{
SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, NODEOP, &idx[v]) );
}
SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, 0.0, 0.0, &idx[nnodes]) );
// add edges of underlying graph
for( v = 0; v < consdata->nedges; ++v )
{
SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, idx[consdata->first[v]], idx[consdata->second[v]], FALSE, 0.0) );
}
// connect nodes with constraint node
for( v = 0; v < nnodes; ++v )
{
SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, idx[v], nodeidx[nnodes], FALSE, 0.0) );
}
// connect operator nodes with variable nodes, assign edges weight of node
for( v = 0; v < nnodes; ++v )
{
vidx = SCIPgetSymgraphVarnodeidx(scip, graph, consdata->vars[v]);
SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, idx[v], vidx, TRUE, consdata->weights[v]) );
}
SCIPfreeBufferArray(scip, &idx);
return SCIP_OKAY;
}
Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB)