Angle_TSP

This example solves a Euclidean traveling salesman problem which objective is to minimize the sum of all angles between two consecutive edges in the tour.

First we create a new instance IP of an SCIL::ILP_Problem as a minimization problem. After this, in read_instance, we read the instance file providing the coordinates of the vertices and add the necessary binary variable for each edge of the graph. In the var_map<edge_descriptor> VM we store each edge and its corresponding variable. Further we calculate the corresponding angles and add an appropriate monomial consisting of the variables linked with the involved edges to the objectiv function using IP.add_polynomial().

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;
   std::vector<edge_descriptor> VE;
   var_map<edge_descriptor> VM;
   std::vector<monomial> lm;
   ILP_Problem IP(Optsense_Min);

   //read Euclidian TSP instance and create objective function
   read_instance(argv[1], G, VE, VM, lm, IP);

   //add symbolic constraint for Tour
   IP.add_sym_constraint(new TOUR<Graph>(G, VM));

   //solve the problem
   IP.optimize();

   //examine the solution
   edge_descriptor e;
   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();
   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);
      }
   }
   return 0;
};