Chinese_Postman_Problem

This example makes use of the T-Join constraint to solve the Chinese Postman Problem.

Every instance has to give the number of vertices and number of edges in the first two lines. Then all edges of the graph are written in the format: source target weight

After creating the ILP model and reading the problem instance we check if the input graph is connected which is a necessary precondition for this problem.

The needed set T for T-Join is the set of all vertices with odd degree.

Then we can add the T-Join constraint to the model and call optimize.

int main(int argc, char** argv){

   vertex_descriptor v, w;
   edge_descriptor e;
   var_map<edge_descriptor> VM;
   map<vertex_descriptor, bool> T;
   Graph G;

   ILP_Problem IP(Optsense_Min);

   read_instance(argv[1], G, VM, IP);

   vector<int> components(num_vertices(G));
   if(connected_components(G, &components[0]) != 1){
      cerr<<"Graph is not connected!"<<endl;
      exit(1);
   }

   //find vertices with odd degree
   BGL_FORALL_VERTICES(v, G, Graph)
      if(out_degree(v, G) % 2 == 1){
         cout<<v<<endl;
         T[v] = true;
      }
      else{
         cout<<v<<" even"<<endl;
         T[v] = false;
      }
   
   IP.add_sym_constraint(new TJOIN<Graph>(G, VM, T));

   IP.optimize();

   //print solution
   
   solution sol = IP.get_solution();
   cout<<"Additional edges (Minimum T-Join):"<<endl;
   double sum = 0;
   BGL_FORALL_EDGES(e, G, Graph){
     cout<<e<<": "<<sol.value(VM[e])<<endl;
     sum += IP.get_obj_coefficient(VM[e]) * (1 + sol.value(VM[e]));
   }
   cout<<"Weight of Postman Tour: "<<sum<<endl; 
   
   
   return 0;
}