SCIP
Solving Constraint Integer Programs
Traveling Salesman Problem
- Version
- 0.9
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:
- \(\sum_{e \in \delta(v)} x_e = 2 \, \forall v \in V \qquad \qquad \)
- subtour \((G,x) \)
Semantics of constraints:
- usual linear constraints
- 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;
/* add variable to SCIP and to the graph */
/* release variable for the reader. */
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:114
Definition: objbenders.h:44
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
edge = node->first_edge;
// sum up the values of all adjacent edges
while( edge != NULL )
{
edge = edge->next;
}
// add the constraint to SCIP
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
Definition: cons_linear.c:18207
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_linear.c:17855
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
Definition: struct_cons.h:47
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_RETCODE SCIPcreateConsSubtour(SCIP *scip, SCIP_CONS **cons, const char *name, GRAPH *graph, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)
Definition: ConshdlrSubtour.cpp:639
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