# 10.9 Travelling Salesman Problem (TSP)¶

The *Travelling Salesman Problem* is one of the most famous and studied problems in combinatorics and integer optimization. In this case study we shall:

- show how to compactly define a model with
*Fusion*; - implement an iterative algorithm that solves a sequence of optimization problems;
- modify an optimization problem by adding more constraints;
- show how to access the solution of an optimization problem.

The material presented in this section draws inspiration from [Pat03].

In a TSP instance we are given a directed graph \(G=(N,A)\), where \(N\) is the set of nodes and \(A\) is the set of arcs. To each arc \((i,j)\in A\) corresponds a nonnegative cost \(c_{ij}\). The goal is to find a minimum cost *Hamilton cycle* in \(G\), that is a closed tour passing through each node exactly once. For example, consider the small directed graph in Fig. 10.7.

Its corresponding adjacency and cost matrices \(A\) and \(c\) are:

Typically, the problem is modelled introducing a set of binary variables \(x_{ij}\) such that

Now we can introduce the following simple model:

It describes the constraint that every vertex has exactly one incoming and one outgoing arc in the tour, and that only arcs present in the graph can be chosen. Problem (1) can be easily implemented in *Fusion*:

```
M = Model();
x = M.variable(Set.make(n,n), Domain.binary());
M.constraint(Expr.sum(x,0), Domain.equalsTo(1.0));
M.constraint(Expr.sum(x,1), Domain.equalsTo(1.0));
M.constraint(x, Domain.lessThan( A ));
M.objective(ObjectiveSense.Minimize, Expr.sum(Expr.mulElm(C, x)));
```

Note in particular how:

- we can sum over rows and/or columns using the
`Expr.sum`

function; - we use
`Expr.dot`

to compute the objective function.

The solution to problem (1) is not necessarily a closed tour. In fact (1) models another problem known as *minimum cost cycle cover*, whose solution may consist of more than one cycle. In our example we get the solution depicted in Fig. 10.7, i.e. there are two loops, namely 0->3->0 and 1->2->1.

A solution to (1) solves the TSP problem if and only if it consists of a single cycle. One classical approach ensuring this is the so-called *subtour elimination*: once we found a solution of (1) composed of at least two cycles, we add constraints that explicitly avoid that particular solution:

Thus the problem we want to solve at each step is

where \(C\) is the set of cycles in all the cycle covers we have seen so far. The overall solution scheme is the following:

- set \(C\) as the empty set,
- solve problem (3),
**if**\(x\) has only one cycle**stop**,**else**add the cycles of \(x\) to \(C\) and**goto**2.

Cycle detection is a fairly easy task and we omit the procedure here for the sake of simplicity. Now we show how to add a constraint for each cycle. Since we have the list of arcs, and each one corresponds to a variable \(x_{ij}\), we can use the function `Variable.pick`

to compactly define constraints of the form (2):

```
M.constraint(Expr.sum(x.pick(I, J)), Domain.lessThan(1.0*length(I) - 1 ));
```

Executing our procedure will yield the following output:

```
it #1 - solution cost: 2.200000
cycles:
[0,3] - [3,0] -
[1,2] - [2,1] -
it #2 - solution cost: 4.000000
cycles:
[0,1] - [1,2] - [2,3] - [3,0] -
solution:
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
```

Thus we first discover the two-cycle solution; then the second iteration is forced not to include those cycles, and a new solution is located. This time it consists of one loop, and as expected the cost is higher. The solution is depicted in Fig. 10.7.

Formulation (3) can be improved in some cases by exploiting the graph structure. Some simple tricks follow.

Self-loops

Self-loops are never part of a TSP tour. Typically self-loops are removed by penalizing them with a huge cost \(c_{ii}\). Although this works in practice, it is more advisable to just fix the corresponding variables to zero, i.e.

This removes redundant variables, and avoids unnecessarily large coefficients that can negatively affect the solver.

Constraints (4) are easily implemented as follows:

```
M.constraint(x.diag(), Domain.equalsTo(0.));
```

Two-arc loops removal

In networks with more than two nodes two-loop arcs can also be ignored. They are simple to detect and their number is of the same order as the size of the graph. The constraints we need to add are:

Constraints (5) are easily implemented as follows:

```
M.constraint(Expr.add(x, x.transpose()), Domain.lessThan(1.0));
```

The complete working example

```
function tsp()
import mosek.fusion.*;
A_i = [1,2,3,4,2,1,3,1]
A_j = [2,3,4,1,1,3,2,4]
C_v = [1.,1.,1.,1.,0.1,0.1,0.1,0.1]
n= max(max(A_i),max(A_j))
x = tsp_fusion(n, Matrix.sparse(n,n,A_i,A_j,1.), Matrix.sparse(n,n,A_i,A_j,C_v) , true, true)
x = tsp_fusion(n, Matrix.sparse(n,n,A_i,A_j,1.), Matrix.sparse(n,n,A_i,A_j,C_v) , true, false)
end
function solution = tsp_fusion(n, A, C, remove_loops, remove_2_hop_loops)
import mosek.fusion.*;
M = Model();
x = M.variable(Set.make(n,n), Domain.binary());
M.constraint(Expr.sum(x,0), Domain.equalsTo(1.0));
M.constraint(Expr.sum(x,1), Domain.equalsTo(1.0));
M.constraint(x, Domain.lessThan( A ));
M.objective(ObjectiveSense.Minimize, Expr.sum(Expr.mulElm(C, x)));
if remove_loops == true
M.constraint(x.diag(), Domain.equalsTo(0.));
end
if remove_2_hop_loops == true
M.constraint(Expr.add(x, x.transpose()), Domain.lessThan(1.0));
end
it = 0;
solution = [];
not_done = 1;
while not_done
it = it + 1
fprintf('\n\n--------------------\nIteration',it);
M.solve();
fprintf('\nsolution cost: %f', M.primalObjValue());
sol = reshape(x.level(), n, n);
start = 1
fprintf('looking for cycles...')
while length( find(sol>0.5) ) > 0
cycle = zeros(n,n);
i = start;
while true
xi = sol(i,:);
j = find(xi>0.5);
if length(j) == 1
cycle (i,j) = 1;
sol(i,j) = 0;
if start == j
break
end
i = j;
else
i = i+1;
start = i;
end
end
[ I, J ]= ind2sub([n,n],find(cycle>0.5));
cycle
if length(I) == n
not_done = 0
break;
end
M.constraint(Expr.sum(x.pick(I, J)), Domain.lessThan(1.0*length(I) - 1 ));
end
end
end
```