Lesson 10
The Travelling Salesman Problem
I. Travelling Salesman: Problem formulation
A salesman has to travel to \(N\) different cities to promote a product, then go back to his original location. What is the shortest path he could take?Let us denote the distance between city \(i\) and \(j\) with \(d(i,j)\). This is known for every \((i,j)\) pair. Moreover, this is \(\ge 0\), symmetric, and obeys the triangle-inequality.
We need to find a cycle between all \(N\) cities that minimizes the total distance travelled.
Let \(x(i,j)\) be a binary decision variable. It is \(1\) if the salesman takes the route from city \(i\) to \(j\), \(0\) otherwise. Then we need the following constraints for the path taken:
Each city travelled from has 1 successor: $$\forall{i \in \{1,\dots,N\}}:\quad \sum_{\begin{matrix}j = 1 \\ i \ne j\end{matrix}}^N x(i,j) = 1$$ Each city travelled to has 1 predecessor: $$\forall{j \in \{1,\dots,N\}}:\quad \sum_{\begin{matrix}i = 1 \\ i \ne j\end{matrix}}^N x(i,j) = 1$$ And the objective function is the total distance travelled on the selected paths: $$\min \sum_{\begin{matrix}i,j=1 \\ i \ne j\end{matrix}}^N d(i,j)x(i,j)$$ Download the Lesson10_TravellingSalesman1.mos Mosel model from here
Download the distances9.dat Data file from here
I./1. Exercise 1
a) Run the program and observe the output!b) Is this a solution of the Travelling Salesman problem? (Draw the exact path the salesman travels!) What's the problem?
c) Suggest solutions to fix the problem! Could the solution ever be tested in polynomial time?
SOLUTION BELOW!
II. Subtour elimination
Idea: We want at least 1 outgoing edge from all subsets of cities.Let \(S = \mathcal{P}(\{1,\dots,N\}) \setminus \{1,\dots,N\} \setminus \emptyset\) be the set of all proper subsets of all city indices. Then $$\forall V \in S:\quad \sum_{i \in V} \sum_{j \in \{1,\dots,N\} \setminus V} x(i,j) \ge 1$$ Download the Lesson10_TravellingSalesman2.mos Mosel model from here
II./1. Exercise 2
a) How would you generate all subsets of a set?b) What does the condition v div round(2^(i-1)) mod 2 = 1 do? (Hint: Look at the toBase2 function.)
c) Draw the solution! Is it correct now?
d) Try to run the code with the following dataset as well on the university server:
Download the distances15.dat Data file from here
How does the solving time scale?
e) EXACTLY ONE STUDENT should try to run the code with the following dataset on the university server:
Download the distances20.dat Data file from here
How does the solving time scale?
II./2. Subtour generation algorithm
1. Solve the problem with only the successor and predecessor constraints.2. If the solution is a Hamiltonian cycle, then we're done! Otherwise, go to 3.
3. Find the cycle that starts from 1. Let \(S\) be the set of vertices on this cycle.
4. Add the single subtour elimination constraint: $$\sum_{i \in V} \sum_{j \in \{1,\dots,N\} \setminus V} x(i,j) \ge 1$$ 5. Solve the problem with this additional constraint. Go to 2.
Download the Lesson10_TravellingSalesman3.mos Mosel model from here
II./3. Exercise 3
a) Go through the subtour generation algorithm in Mosel!b) Compare the runtime of this model for the various datasets!
c) Approximately how many subtours were eliminated per dataset?
III. The Miller-Tucker-Zemlin formulation
Idea: New variable \(u_i\) for each city \(i\) that counts the number of steps taken from city 1. We aren't allowed to go back to a city with a lower \(u_i\) than the current one!Problem: This is an algorithmic idea and not an optimization idea. The optimizer fids all edges at the same time. We need a constraint for the \(u_i\)s that is equivalent to the above idea!
The Miller-Tucker-Zemlin formulation yields this equivalence: $$\begin{align} \forall i \ge 2:\quad &1 \le u_i \le N-1 \\ \forall i,j \ge 2, i \ne j:\quad &u_i-u_j+Nx_{ij} \le N-1 \end{align}$$ Download the Lesson10_TravellingSalesman4.mos Mosel model from here
III./1. Exercise 4
a) How much faster is the Miller-Tucker-Zemlin formulation than the Subtour generation algorithm on the 3 datasets?b) We no longer have anything exponential in the model. Can the Travelling Salesman problem be solved in polynomial time...?