MaxCut

This example shows how to compute a maximum cut of a given graph G using the symbolic constraint SCIL::CUT.

We first create an empty graph and initialize it using the function readgraph.

   Graph G;
   map<vertex_descriptor, int> vertex_index;
   map<edge_descriptor, double> edge_property;
   int base = atoi(argv[1]);
   readgraph(base, argv[2], G, vertex_index, edge_property);

We then create a new instance IP of an SCIL::ILP_Problem as a maximization problem.

   ILP_Problem IP(Optsense_Max);

To compute minimum cuts one would use ILP_Problem IP(Optsense_Min); here. The row_map VM is used to store the variables that are added to the model. These variables are binary and correspond to the edges of the graph G.

   edge_descriptor e;
   row_map<edge_descriptor> VM;
   BGL_FORALL_EDGES(e, G, Graph)
      VM[e]=IP.add_binary_variable(edge_property[e]);

The edges corresponding to variables with value 1 in an optimal solution should form a valid cut in G. To achieve this we add the symbolic constraint CUT to the model.

   CUT<Graph>* scc = new CUT<Graph>(G, VM);
   IP.add_sym_constraint(scc);

As this is the only constraint, our model is now complete and we can compute an optimum solution by calling optimize.

   IP.optimize();

The optimal solution value can be accessed directedly using SCIL::ILP_Problem::get_optimum().

   double optimum = IP.get_optimum();

The configuration corresponding to the optimal solution can be accessed using getConfiguration.

   list<vertex_descriptor> configuration = scc->getConfiguration(sol);
   vertex_descriptor v;
   BOOST_FOREACH(v, configuration)
      cout << vertex_index[v] + abs(base) << " ";
   cout << endl;