License

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

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.