Compute_Traveling_Salesman_Tour

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

In the function ComputeTour, we create a new instance IP of an ILP_Problem as a minimization problem.

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

Next we create a new instance of the symbolic constraint TOUR. The parameters are the graph G and the var_map<edge> 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().

#include<scil/scil.h>
#include<scil/constraints/tour.h>

using namespace SCIL;

void ComputeTour(graph& G, edge_array<double>& Cost, list<edge>& T) {
  cout<<"start\n";

  ILP_Problem IP(Optsense_Min);

  cout<<"init\n";
  edge e=nil;
  var_map<edge> VM;
  forall_edges(e,G) { 
    VM[e]=IP.add_variable(Cost[e], 0, 1, Vartype_Integer);
  }
  cout<<"vars added\n";
  IP.add_sym_constraint(new TOUR(G,VM));
  cout<<"hier\n";
  IP.optimize();

  forall_edges(e, G) {
    if(IP.get_solution(VM[e])==1) T.append(e);
  }
}

We used this function in the demo gtsp.

---