Traveling_Salesman_Tour

A SCIL-program starts with some includes. We include the SCIL-core and the symbolic constraint TOUR.

This example is able to read tsplib instances with EDGE_WEIGHT_TYPE EUC_2D.

First we create a new instance IP of an SCIL::ILP_Problem as a minimization problem.

As we want to use the symbolic constraint SCIL::TOUR we have to create a binary variable for every edge of the graph. We use the var_map<edge_descriptor> VM to store the connection. The objective function value of the variable corresponding to edge e is costs[e].

Next we create a new instance of the symbolic constraint TOUR. Its template parameter describes the used graph type. The other parameters are the Graph G and the var_map<edge_descriptor> VM.

We solve the model IP by the command IP.optimize(). This command starts the optimization process.

Finally we access the solution found by the function IP.optimize().

int main(int argc, char ** argv) {
   Graph G;
   map<vertex_descriptor, double> xp,yp;
   readTsplibFile(G, argv[1], xp, yp);

   //calculate costs
   map<edge_descriptor, double> costs;
   vertex_iterator it1,it2;
   for(it1 = vertices(G).first; it1 != vertices(G).second; it1++){
      it2 = it1;
      it2++;
      for(;it2 != vertices(G).second; it2++){
         costs[add_edge(*it1, *it2, G).first] = sqrt((xp[*it1]-xp[*it2])*(xp[*it1]-xp[*it2])+(yp[*it1]-yp[*it2])*(yp[*it1]-yp[*it2]));
      }
   }

  ILP_Problem IP(Optsense_Min);

  var_map<edge_descriptor> VM;
  BGL_FORALL_EDGES(e,G, Graph) { 
    VM[e]=IP.add_binary_variable(costs[e]);
  }
  IP.add_sym_constraint(new TOUR<Graph>(G,VM));
  IP.optimize();
 
 
  //examine the solution
   cout<<"Optimal Solution Value: "<<IP.get_optimum()<<endl;
   cout<<"Tour: "<<endl;
   std::vector<edge_descriptor> v;
   solution s = IP.get_solution();
   BGL_FORALL_EDGES(e, G, Graph)
      if(s.value(VM[e]) > 0.9)
         v.push_back(e);
   std::vector<edge_descriptor>::iterator it = v.begin();
   unsigned int pos,start;
   start = source(*it, G);
   pos=target(*it, G);
   cout<<start<<endl;
   while(pos!=start) {
      it++;
      if(it==v.end())
         it=v.begin();
      if(source(*it, G) == pos) {
         cout<<pos<<endl;
         pos=target(*it, G);
      }else if(target(*it, G) == pos) {
         cout<<pos<<endl;
         pos=source(*it, G);
      }
   }
}