13.2 ILP models for the Travelling Salesman Problem¶
Part 2 · Formulations and their properties · Chapter 13 · Chapter 13: Routing problems · Lecture notes, volume 2 (PDF) · Slides · Exercises: Routing problems
The Travelling Salesman Problem and its reference instance (Example 6.1) are defined in Chapter 6 «Routing problems», Section 6.2.
-
The TSP has two classical ILP models on the arc variables \(x_{ij}\): the model of Miller, Tucker and Zemlin (MTZ) of Section 13.3, with position variables, and the model of Dantzig, Fulkerson and Johnson (DFJ) of Section 13.4, with subtour elimination constraints.
-
Section 13.5 compares the Linear Programming relaxations of the two models.
13.3 A model with position variables (MTZ)¶
-
We introduce the following \(n(n-1)\) binary variables:
\[ x_{ij}= \begin{cases} 1 & \text{if arc $(i,j)$ is traversed by the tour}\\[1.5ex] 0 & \text{otherwise} \end{cases} \qquad \forall (i,j)\in A, \]and the following \(n-1\) continuous variables:
\[ u_i=\text{position of city $i$ after leaving city $1$}, \qquad \forall i\in\mathscr{V}\setminus\{1\}. \]The city \(1\) is used only as a reference city: a tour has no preferred starting city.
Using these variables, an Integer Linear Programming (ILP) model for the Travelling Salesman Problem (TSP) reads as follows:
This ILP model is referred to as the \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) model, or MTZ model.
-
Description of the objective function and constraints of the \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) model:
-
the linear objective function \(\eqref{obj:TSP}\) minimizes the total distance travelled by the tour;
-
constraints \(\eqref{out:TSP}\) ensure that exactly one arc leaves each city (\(n\) linear constraints);
-
constraints \(\eqref{in:TSP}\) ensure that exactly one arc enters each city (\(n\) linear constraints);
-
constraints \(\eqref{MTZ:TSP}\) link the arc variables with the position variables and eliminate the subtours that do not contain city \(1\) (\((n-1)(n-2)\) linear constraints);
-
finally, constraints \(\eqref{bin:TSP}\) and \(\eqref{pos:TSP}\) define the variables of the ILP model.
-
Explanation of the link between the variables
-
For each pair of cities \(i,j\) different from city \(1\), if arc \((i,j)\) is traversed, then the position of city \(j\) is at least one unit greater than the position of city \(i\). This logical relation is the implication
\[ x_{ij}=1 ~~~\Longrightarrow~~~ u_j\ge u_i+1. \] -
Its contrapositive is
\[ u_j< u_i+1 ~~~\Longrightarrow~~~ x_{ij}=0. \]In particular, an arc from a city to a city in the same or in an earlier position cannot be traversed.
-
Both implications are imposed by the linear constraints \(\eqref{MTZ:TSP}\). If \(x_{ij}=1\), then the constraint gives \(u_i-u_j+(n-1)\le n-2\), that is \(u_j\ge u_i+1\).
-
Conversely, if \(u_j<u_i+1\), then the constraint gives \((n-1)x_{ij}\le n-2+u_j-u_i<n-1\). Since \(x_{ij}\) is binary, this forces \(x_{ij}=0\).
-
When \(x_{ij}=0\), the constraint becomes \(u_i-u_j\le n-2\), which is always satisfied because both positions belong to \([1,n-1]\). Accordingly, \(n-1\) is the smallest possible big-M coefficient for these bounds.
Proposition 13.1: MTZ constraints eliminate subtours
The constraints \(\eqref{out:TSP}\)–\(\eqref{pos:TSP}\) are satisfied by an integer solution if and only if its selected arcs form one tour through all the cities.
Proof
Constraints \(\eqref{out:TSP}\) and \(\eqref{in:TSP}\) make the selected arcs a collection of vertex-disjoint directed cycles covering all cities. Suppose that one such cycle does not contain city \(1\) and visits, in order, \(i_1,i_2,\dots,i_k\). Since every arc \((i_r,i_{r+1})\) is selected, the implication above gives
where \(i_{k+1}=i_1\). Summing the inequalities gives \(u_{i_1}\ge u_{i_1}+k\), a contradiction. Thus no cycle can avoid city \(1\), and the collection is one tour.
Conversely, consider any tour and start it from city \(1\). For every city \(i\neq1\), set \(u_i\) equal to the position at which city \(i\) is visited after leaving city \(1\). The bounds \(\eqref{pos:TSP}\) hold. If a selected arc \((i,j)\) has \(i,j\neq1\), then city \(j\) immediately follows city \(i\), so that \(u_j=u_i+1\) and \(\eqref{MTZ:TSP}\) holds. If the arc is not selected, constraint \(\eqref{MTZ:TSP}\) holds by the bounds on the positions. Hence the tour defines a feasible integer solution. □
Example 13.1: TSP instance
We consider the set \(\mathscr{V}=\{1,2,3,4,5\}\) of \(5\) cities (\(n=5\)), with the distance matrix
This is the instance of Example 6.1 of Chapter 6 «Routing problems». We refer to this TSP instance as Example 13.1.
Example 13.2: \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) model
The \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) model for the TSP instance of Example 13.1 has \(20\) arc variables, \(4\) position variables, \(10\) degree constraints and \(12\) constraints \(\eqref{MTZ:TSP}\):
An optimal solution \((\tilde{\vet x},\tilde{\vet u})(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}})\) is:
The optimal value \(z(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}})\) is \(18\). The associated optimal solution of the TSP is the tour \(\tilde\sigma=(1,3,5,2,4)\), of length \(L(\tilde\sigma)=2+7+4+3+2=18\); it is the unique optimal tour, up to the direction.
13.4 A model with subtour elimination constraints (DFJ)¶
- The second model uses only the \(n(n-1)\) arc variables \(x_{ij}\) of the MTZ model: there are no position variables. The subtours are forbidden directly, with one constraint for every subset of cities.
Using these variables, a second Integer Linear Programming (ILP) model for the Travelling Salesman Problem (TSP) reads as follows:
This ILP model is referred to as the \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) model, or DFJ model.
-
Description of the objective function and constraints of the \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) model:
-
the objective function \(\eqref{obj:TSP-DFJ}\) and the degree constraints \(\eqref{out:TSP-DFJ}\) and \(\eqref{in:TSP-DFJ}\) are those of the MTZ model;
-
constraints \(\eqref{SEC:TSP}\) are called subtour elimination constraints: a tour cannot contain all the \(|S|\) arcs of a cycle on the cities of \(S\), so it uses at most \(|S|-1\) arcs inside \(S\) (\(2^{n-1}-n\) linear constraints);
-
finally, constraints \(\eqref{bin:TSP-DFJ}\) define the variables of the ILP model.
-
-
The number \(2^{n-1}-n\) of constraints \(\eqref{SEC:TSP}\) is exponential in \(n\): for \(n=5\) they are \(11\), for \(n=20\) they are \(524\,268\).
Proposition 13.2: Subtour elimination constraints
The constraints \(\eqref{out:TSP-DFJ}\)–\(\eqref{bin:TSP-DFJ}\) are satisfied by an integer solution if and only if its selected arcs form one tour through all the cities.
Proof
Let a tour be given and let \(S\subseteq\mathscr{V}\setminus\{1\}\) with \(|S|\ge2\). If the tour used \(|S|\) arcs inside \(S\), these arcs would form a cycle on the cities of \(S\), which is not the whole tour since \(1\notin S\): a contradiction. Hence \(\eqref{SEC:TSP}\) holds, and the degree constraints hold by definition of a tour.
Conversely, constraints \(\eqref{out:TSP-DFJ}\) and \(\eqref{in:TSP-DFJ}\) make the selected arcs a collection of vertex-disjoint directed cycles. If there were more than one cycle, one of them would not contain city \(1\). Let \(S\) be its set of cities: then \(|S|\ge2\) and the cycle uses \(|S|\) arcs inside \(S\), which violates \(\eqref{SEC:TSP}\). Hence there is one cycle, a tour. □
Example 13.3: \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) model
The \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) model for the TSP instance of Example 13.1 has \(20\) arc variables, \(10\) degree constraints and \(11\) constraints \(\eqref{SEC:TSP}\), one for every subset \(S\subseteq\{2,3,4,5\}\) with at least two cities:
The subtour \(2\to5\to2\) together with the subtour \(1\to3\to4\to1\) satisfies the degree constraints but violates the constraint \(x_{25}+x_{52}\le1\) of \(S=\{2,5\}\). An optimal solution \(\tilde{\vet x}(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}})\) is the tour \(\tilde\sigma=(1,3,5,2,4)\):
The optimal value \(z(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}})\) is \(18\).
13.5 Linear Programming relaxations¶
13.5.1 The assignment relaxation¶
Keeping only the degree constraints of the two models, and relaxing the binary constraints into non-negativity constraints, we obtain the following LP model:
This LP model is referred to as the \(\mathrm{LP}\text{-}0_{\mathrm{TSP}}\) model, or assignment relaxation.
-
Adding the upper bounds \(x_{ij}\le1\) does not change this relaxation, nor the two relaxations below: for every arc \((i,j)\), non-negativity and the degree equation \(\eqref{out:LP0-TSP}\) give
\[ x_{ij}\le \sum_{\substack{k\in\mathscr{V}\\k\neq i}}x_{ik}=1. \]
Example 13.4: \(\mathrm{LP}\text{-}0_{\mathrm{TSP}}\) model
The \(\mathrm{LP}\text{-}0_{\mathrm{TSP}}\) model for the TSP instance of Example 13.1 is:
An optimal solution \(\tilde{\vet x}(\mathrm{LP}\text{-}0_{\mathrm{TSP}})\) is:
It is integer, but it is made of the two subtours \(1\to3\to4\to1\) and \(2\to5\to2\). The optimal value \(z(\mathrm{LP}\text{-}0_{\mathrm{TSP}})\) is \(16\). Accordingly we have the lower bound:
13.5.2 The relaxation of the MTZ model¶
To obtain an LP relaxation of the \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) model, we relax constraints \(\eqref{bin:TSP}\) into non-negativity constraints; the position variables keep their bounds. The obtained LP model reads as follows:
This LP model is referred to as the \(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) model.
Proposition 13.3: A weak region of the MTZ relaxation
Let \((x,u)\) satisfy the degree equations \(\eqref{out:LP-MTZ}\)–\(\eqref{in:LP-MTZ}\), with \(x_{ij}\ge0\). If
then \((x,u)\) is feasible for \(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) after setting \(u_i=1\) for every \(i\neq1\).
Proof
With \(u_i=u_j=1\), each constraint \(\eqref{MTZ:LP-MTZ}\) becomes
which is exactly the assumed upper bound. The bounds \(\eqref{pos:LP-MTZ}\) on the position variables also hold. □
- The proposition shows why the compact MTZ formulation can have a weak lower bound: many fractional solutions of the assignment relaxation already satisfy the ordering constraints.
Example 13.5: \(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) model
The \(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) model for the TSP instance of Example 13.1 is:
An optimal solution \((\tilde{\vet x},\tilde{\vet u})(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{MTZ}})\) is:
All the arcs between the cities \(2,3,4,5\) have value at most \(\frac{3}{4}=\frac{n-2}{n-1}\), as in Proposition 13.3. The optimal value \(z(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{MTZ}})\) is \(17\). Accordingly we have the lower bound:
13.5.3 The relaxation of the DFJ model¶
To obtain an LP relaxation of the \(\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) model, we relax constraints \(\eqref{bin:TSP-DFJ}\) into non-negativity constraints. The obtained LP model reads as follows:
This LP model is referred to as the \(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) model.
- The MTZ model is valuable because it has only \(O(n^2)\) variables and constraints. The DFJ model has a stronger relaxation, but exponentially many constraints: in practice, the subtour elimination constraints are added only when they are violated by the current solution of the relaxation.
Example 13.6: \(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) model
The \(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) model for the TSP instance of Example 13.1 is:
An optimal solution \(\tilde{\vet x}(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{DFJ}})\) is the tour \(\tilde\sigma=(1,3,5,2,4)\):
The optimal value \(z(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{DFJ}})\) is \(18\): on this instance the relaxation closes the gap.
Example 13.7: comparing the relaxations
For the TSP instance of Example 13.1, the three relaxations give the following lower bounds on the optimal value \(18\):
| Relaxation | Optimal value |
|---|---|
| \(\mathrm{LP}\text{-}0_{\mathrm{TSP}}\) (assignment relaxation) | \(16\) |
| \(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{MTZ}}\) | \(17\) |
| \(\mathrm{LP}_{\mathrm{TSP}}^{\mathrm{DFJ}}\) | \(18\) |
The ordering constraints raise the bound from \(16\) to \(17\); the subtour elimination constraints close the gap on this instance.