Precedence_Constrained_Traveling_Salesman_Tours

Precedence Constrained Traveling Salesman Tours

Input for the algorithm is a directed GRAPH<int,int> G, where the node information stores an index for every node and the edge information stores the distance between the two endpoints. The source node of the tour is the node with index G.number_of_nodes() - 1 . Furthermore we a given a list<prec> L, where prec is a typedef for two_tuple<node,node>. This list stores all precedences that must be respected, i.e. if the tuple (u,v) is in L, the node u must be visited before the node v.

The formulation idea is as follows. We model the Hamiltonian cycle using the directed version of the tour-constraint ATOUR. To enforce the precedences we use the constraint PATH. If u must be visited before the node v, there is a path from u to v in the computed tour, even if one ignores the two edges incoming and outgoing the source node.

We create a variable for each edge of the graph and maintain two different row_map<edge>, one which we use in the symbolic constraint ATOUR, the other we use in the symbolic constraints PATH. One stores all variables corresponding to the edges, the other stores the same variables for all edges that are not adjacent to the source node and the constant 0 (the default value) for the edges adjacent to the source node.

  ILP_Problem IP(Optsense_Min);

  var_map<edge_descriptor> VM, VM1;

  property_map<Graph, edge_weight_t>::type w
  = get(edge_weight, G);


  BGL_FORALL_EDGES(e,G,Graph) {
    VM[e]=IP.add_binary_variable(w[e]);                 
    if( (source(e,G)!=V[i-1]) && (target(e,G)!=V[i-1]))
      VM1[e]=VM[e];
  }


  //FIXME
  IP.add_sym_constraint(new ATOUR<Graph>(G, VM));


  prec p;
  std::list< PATH<Graph>* > paths;

  BOOST_FOREACH(p, PL) {
    IP.add_sym_constraint(new PATH<Graph>(G, p.first, p.second, VM1));
  };

  //IP.add_sym_constraint(new disjunctive()); 

  IP.optimize();

  BGL_FORALL_EDGES(e,G,Graph) 
    if(IP.get_solution(VM[e])==1) 
      cout << source(e,G) << " " << target(e,G) << " edge\n";

};

To complete the implementation of this demo, we show the code that reads an input graph from a file.

  // READ_GRAPH
  const char* fname = (argc > 1) ? argv[1] : "data.sop";
  ifstream is(fname);

  int i=0, j=0;

  Graph G;

  vertex_descriptor V[1000];
  std::list<prec> PL;

  while(j<1000) {
    is>>j;
    if(j<1000) {
      V[i] = add_vertex(G);
      i++;
    }
  };
  is>>j;

  for(int s=0; s<i; s++) {
    for(int t=0; t<i; t++) {
      is>>j;
      if(s!=t) {
        if((s!=i-1) && (t!=i-1)) {
          if(j>=0)
            add_edge(V[s],V[t],j,G);
          else PL.push_back(prec(V[t], V[s]));
        }
        if((s==i-1) || (t==i-1))
          add_edge(V[s],V[t],0,G);
      }
      cout<<j<<" ";
    };
    is>>j;
    cout<<endl;
  };

  // END_READ_GRAPH