Traveling Salesman Problem

Version

0.9

Author

Timo Berthold

This is an example of using SCIP to solve the TSP problem on undirected graphs. Here is the CIP model that we use:

Given: a graph \( G=(V,E) \) with edge weights \( c_e \) Task: find hamiltonian cycle \( T \) in \( G \) with minimal length \( c(T) \)

Variables: \( x_e \in \{0,1\} \, \forall e \in E, x_e = 1 \Leftrightarrow e \in T \)

Constraints:

1. \(\sum_{e \in \delta(v)} x_e = 2 \, \forall v \in V \qquad \qquad \)
2. subtour \((G,x) \)

Semantics of constraints:

1. usual linear constraints
2. subtour \((G,x)\Leftrightarrow\) \( T \) defined by \( x \) does not contain any cycle of length \( < |V| \).

A few remarks to the model and the implementation (references to code lines might not be up to date):

As one can see, the TSP-Model consists of \( |V| \) linear constraints (the degree constraints) and one "subtour" constraint. The latter is a complex, non-linear constraint for which one has to implement an own constraint handler. The variables are created in the TSP file reader ReaderTSP.cpp:

      // the variable is named after the two nodes connected by the edge it represents
      varname << "x_e_" << edge->back->adjac->id+1 << "-" << edge->adjac->id+1;
      SCIP_CALL( SCIPcreateVar(scip, &var, varname.str().c_str(), 0.0, 1.0, edge->length,
            SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );

      /* add variable to SCIP and to the graph */
      SCIP_CALL( SCIPaddVar(scip, var) );
      SCIP_CALL( addVarToEdges(scip, edge, var) );

      /* release variable for the reader. */
      SCIP_CALL( SCIPreleaseVar(scip, &var) );

A pointer to each variable is stored in the data structure of the corresponding edge (i.e., in edge->var and edge->back->var, since the formally undirected graph is represented as a directed graph with antiparallel arcs). After that, the degree constraints are created:

         SCIP_CONS* cons;
         stringstream consname;
         consname << "deg_con_v" << node->id+1;

         // a new degree constraint is created, named after a node
         SCIP_CALL( SCIPcreateConsLinear(scip, &cons, consname.str().c_str(), 0, NULL, NULL, 2.0, 2.0,
               TRUE, FALSE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );

         edge = node->first_edge;
         // sum up the values of all adjacent edges
         while( edge != NULL )
         {
            SCIP_CALL( SCIPaddCoefLinear(scip, cons, edge->var, 1.0) );
            edge = edge->next;
         }

         // add the constraint to SCIP
         SCIP_CALL( SCIPaddCons(scip, cons) );
         SCIP_CALL( SCIPreleaseCons(scip, &cons) );

The data for the linear degree constraints are the coefficients (for each \(e \in \delta(v)\) the variable \( x_e \) has coefficient 1.0) which are generated at line 437, and the left and right hand sides of the inequality, which are both set to 2.0 at line 430, such that the linear constraint becomes an equation. The subtour constraint is created at line 449. The data for this constraint is the graph and the variables (see above), but we only have to store a pointer to the graph because the edges already have links to their respective variables.

Now the problem instance is defined, and the "only" thing left is to implement the semantics of the "subtour" constraint. This is of course done in the subtour constraint handler ConshdlrSubtour.cpp. The main task of a constraint handler is to decide whether a given solution is feasible for all constraints of the constraint handler's type (i.e., for example, for all linear constraint in the instance, for all knapsack constraints in the instance, for all subtour constraints in the instance, ...). This is performed in the scip_enfolp(), scip_enfops(), and scip_check() methods. To implement these three methods and the scip_lock() method (called the "fundamental callback methods" in the SCIP documentation) is already enough to obtain a correct algorithm, which means that the solver will find (after waiting long enough) the optimal solution. The remaining methods are only needed to speed up the solving process (for example, cutting plane separation and domain propagation).

   /* last, we need a constraint forbidding subtours */
   SCIP_CONS* cons;
   SCIP_CALL( SCIPcreateConsSubtour(scip, &cons, "subtour", graph,
         FALSE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, TRUE ) );
   SCIP_CALL( SCIPaddCons(scip, cons) );
   SCIP_CALL( SCIPreleaseCons(scip, &cons) );

As there is only one subtour constraint in a TSP instance, all the loops

for( int i = 0; i < nconss; ++i )
...

in ConshdlrSubtour.cpp are a bit ridiculous, since nconss will always be equal to one. However, nothing prevents a user from using the subtour constraint handler in a different application where you have more than one graph and a solution must not contain any subtour in each of the graphs.

Additionally, this example contains two well known combinatorial heuristics for the TSP, namely a farthest insert heuristic and a 2-opt heuristic, and a rounding heuristic for TSPs. The idea of the latter one is to take an LP solution and construct a hamiltonian cycle in the following way: If \( x_e \) is equal to one, add edge \( e \) to the cycle. Iterate over the remaining variables in nonincreasing order of their LP value \( x_e \) and add the corresponding edge \( e \) , if it does not close a subtour.

Installation

See the Install file