Editing Travelling salesman problem (section)

===Miller–Tucker–Zemlin formulation===
In addition to the <math> x_{ij} </math> variables as above, there is for each <math>i=1,\ldots,n</math> a dummy variable <math>u_i</math> that keeps track of the order in which the cities are visited, counting from city {{nobr|<math>1</math>;}} the interpretation is that <math> u_i < u_j </math> implies city <math>i</math> is visited before city <math>j.</math> For a given tour (as encoded into values of the <math> x_{ij} </math> variables), one may find satisfying values for the <math> u_i </math> variables by making <math> u_i </math> equal to the number of edges along that tour, when going from city <math>1</math> to city <math>i.</math><ref>C. E. Miller, A. W. Tucker, and R. A. Zemlin. 1960. Integer Programming Formulation of Traveling Salesman Problems. ''J. ACM'' 7, 4 (Oct. 1960), 326–329. DOI:https://doi.org/10.1145/321043.321046</ref>

Because linear programming favors non-strict inequalities (<math> \ge </math>) over strict {{nobr|(<math> > </math>),}} we would like to impose constraints to the effect that

: <math> u_j \ge u_i + 1 </math> if <math> x_{ij} = 1. </math>

Merely requiring <math> u_j \geq u_i + x_{ij} </math> would ''not'' achieve that, because this also requires <math> u_j \geq u_i </math> when <math> x_{ij} = 0, </math> which is not correct. Instead MTZ use the <math> n(n-1) </math> linear constraints

: <math> u_i - u_j + 1 \le (n-1)(1 - x_{ij}) </math> for all distinct <math> i,j \in \{2,\dotsc,n\}, </math>

where the constant term <math> n-1 </math> provides sufficient slack that <math> x_{ij} = 0 </math> does not impose a relation between <math> u_j </math> and <math> u_i. </math>

The way that the <math> u_i </math> variables then enforce that a single tour visits all cities is that they increase by at least <math> 1 </math> for each step along a tour, with a decrease only allowed where the tour passes through city&nbsp;<math> 1. </math> That constraint would be violated by every tour which does not pass through city&nbsp;<math> 1, </math> so the only way to satisfy it is that the tour passing city&nbsp;<math> 1 </math> also passes through all other cities.

The MTZ formulation of TSP is thus the following integer linear programming problem:

:<math>\begin{align}
\min \sum_{i=1}^n \sum_{j\ne i,j=1}^nc_{ij}x_{ij}&\colon &&  \\
     x_{ij} \in{}& \{0,1\}  && i,j=1, \ldots, n; \\
     \sum_{i=1,i\ne j}^n x_{ij} ={}& 1 && j=1, \ldots, n; \\
     \sum_{j=1,j\ne i}^n x_{ij} ={}& 1 && i=1, \ldots, n; \\
     u_i - u_j + 1 \le{}& (n-1)(1 - x_{ij}) && 2 \le i \ne j \le n;  \\
     2 \le u_i \le{}& n && 2 \le i \le n.
\end{align}</math>

The first set of equalities requires that each city is arrived at from exactly one other city, and the second set of equalities requires that from each city there is a departure to exactly one other city. The last constraint enforces that there is only a single tour covering all cities, and not two or more disjointed tours that only collectively cover all cities.