Steiner_Arborescence

This example demonstrates the use of the symbolic constraint SCIL::SteinerArborescence.

First we read the instance given by the first parameter of the program. The first vertex is marked as the root, and argv[2] terminals are chosen sequentially.

Then we build the ILP model, add a variable for each edge of the graph and add a new symbolic constraint to model the underlying Steiner Arborescence.

Now we solve the problem with a call to IP.optimize and print the solution.

#include<scil/scil.h>
#include<scil/constraints/SteinerArborescence.h>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/iteration_macros.hpp>

using namespace std;
using namespace SCIL;
using namespace boost;


typedef boost::adjacency_list<vecS,vecS,bidirectionalS> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;


void read_network(char* file_name, Graph& G, map<edge_descriptor, double>& edge_weights, map<vertex_descriptor, pair<int, int> >& vertexmap)
{
   ifstream file;
   file.open(file_name);

   int number_of_vertices;

   file >> number_of_vertices;
   double x,y;
   vertex_descriptor v,w;

   for(int i = 0; i<number_of_vertices; i++){
      file >> x >> y;
      vertexmap[add_vertex(G)] = make_pair(x,y);
   }

   file.close();

   BGL_FORALL_VERTICES(v, G, Graph){
      BGL_FORALL_VERTICES(w, G, Graph){
         if(v != w){
            edge_descriptor e = add_edge(v,w,G).first;
            double dist = sqrt(((vertexmap[w].second - vertexmap[v].second) * (vertexmap[w].second - vertexmap[v].second) ) + ((vertexmap[w].first - vertexmap[v].first) * (vertexmap[w].first - vertexmap[v].first)));
            edge_weights[e] = dist;
         }
      }
   }
}


int main(int argc, char** argv){
   
   Graph G;
   map<edge_descriptor, double> edge_weights;
   map<vertex_descriptor, pair<int, int> > vertexmap;
   var_map<edge_descriptor> VM;

   read_network(argv[1], G, edge_weights, vertexmap);
   
   vertex_descriptor root = *(vertices(G).first);
   list<vertex_descriptor> terminals;
   int num_terminals = atoi(argv[2]);

   int i = 0;
   BGL_FORALL_VERTICES(v, G, Graph){
      if(v != root && (i < num_terminals || num_terminals == 0)){
         terminals.push_back(v);
         i++;
      }
   }

   ILP_Problem IP(Optsense_Min);

   BGL_FORALL_EDGES(e, G, Graph)
      VM[e] = IP.add_binary_variable(edge_weights[e]);

   IP.add_sym_constraint(new SteinerArborescence<Graph>(G, root, terminals, VM));

   IP.optimize();

   cout<<"Optimum: "<<IP.get_optimum()<<endl;
   BGL_FORALL_EDGES(e, G, Graph){
      if(IP.get_solution(VM[e]) == 1)
         cout<<e<<endl;
   }
}