In this post we want to try to provide a solution to solve the Traveling Salesman Problem (TSP) using linear programming. The post is based on this excellent video from Mr. Michel Bierlaire at the EPFL. A good written documentation of the Miller Tucker Zemlin Constraint can be found here.
What is a TSP?
The Traveling Salesman Problem goes as follows:
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?Source: Wikipedia
This problem is one of the most intensely treated tasks in Operations Research.
It is an NP-hard problem and the possible solutions explode exponentially in the number of cities. Even though the problem is computationally difficult, many heuristics and exact algorithms are known, so that instances with tens of thousands of cities can be solved.
TSP solved using Linear Programming
Now let’s try to solve the TSP using a linear model. Consider the following graph with the cities 1-5:
In order to minimize the TSP tour we need to know the distance between all nodes. Let denote the distance between the nodes and . Now in order to model this as an optimization problem, we need:
- decision variables
- objective function
Let be our binary decision variables, telling us, whether node is visited directly after node ( otherwise).
Since we know the distance between all nodes (), together with we can now write down our objective function which minimizes the total distance of our TSP tour:
Now let’s think about the constraints we need to establish, in order to get valid TSP tours. After a bit of reflection, one might come up with the followin two ideas:
Constraint 1: Every node has exactly one successor node.
Constraint 2: Every node has exactly one predecessor node.
If we would try to solve the problem above with the 5 cities using the model above, we might get a solution as follows:
As can be seen, not all nodes are connected to one single tour. The resulting tour consists of two unconnected subtours: Tour 1-2-3-1 and tour 4-5-4. Although this tour is not a valid TSP tour we can easily determine that both constraints are met. Our model obviously does not prevent our solution to consist of unconnected subtours. We need a so called subtour elimination constraint to prevent the situation above.
There are multiple ways to prevent subtours. Here, we have a look at one possible approach known as the Miller-Tucker-Zemlin Subtour Elimination Constraint (MTZ-STE).
A first Subtour Elimination Constraint (STE)
The core idea here is to suppress subtours is to enumerate all but the start location in the resulting tour. If we can make sure, that the first stop after the depot gets assigned index 1 and every subsequent stop in the tour gets a succeeding integer index assigned compared to its predecessor, we could eliminate unconnected subtours. The MTZ formulation goes as follows:
Let’s check, whether this makes sense. If , we get:
This is exactly what we want. Every subsequent node gets assigned an index which is at least 1 larger than the index of its predecessor. If , we get:
Also this is true, since the largest difference between two indexes of any (non start) nodes equals to , which is exactly what’s written here.