Editing Travelling salesman problem (section)

==Integer linear programming formulations==
The TSP can be formulated as an [[integer programming|integer linear program]].<ref>{{Citation |last1=Papadimitriou|first1=C.H.|last2=Steiglitz |first2=K. |title=Combinatorial optimization: algorithms and complexity|year=1998 |publisher=Dover|location=Mineola, NY}}, pp.308-309.</ref><ref>Tucker, A. W. (1960), "On Directed Graphs and Integer Programs", IBM Mathematical research Project (Princeton University)</ref><ref>Dantzig, George B. (1963), ''Linear Programming and Extensions'', Princeton, NJ: PrincetonUP, pp. 545–7, {{isbn|0-691-08000-3}}, sixth printing, 1974.</ref> Several formulations are known. Two notable formulations are the Miller–Tucker–Zemlin (MTZ) formulation and the Dantzig–Fulkerson–Johnson (DFJ) formulation. The DFJ formulation is stronger, though the MTZ formulation is still useful in certain settings.<ref>{{cite journal |title=Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the Asymmetric Traveling Salesman Problem |journal=Operations Research Letters|volume=45 |issue=4|pages=323–324|doi=10.1016/j.orl.2017.04.010|year=2017|last1=Velednitsky|first1=Mark |arxiv=1805.06997|s2cid=6941484}}</ref><ref>{{cite journal |title=Requiem for the Miller–Tucker–Zemlin subtour elimination constraints? |journal=European Journal of Operational Research|volume=236|issue=3 |pages=820–832 |doi=10.1016/j.ejor.2013.07.038|year=2014|last1=Bektaş|first1=Tolga|last2=Gouveia|first2=Luis}}</ref>

Common to both these formulations is that one labels the cities with the numbers <math>1,\ldots,n</math> and takes <math>c_{ij} > 0</math> to be the cost (distance) from city <math>i</math> to city <math>j</math>. The main variables in the formulations are:

:<math> x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise.} \end{cases}</math>

It is because these are 0/1 variables that the formulations become integer programs; all other constraints are purely linear. In particular, the objective in the program is to minimize the tour length

: <math> \sum_{i=1}^n \sum_{j\ne i,j=1}^n c_{ij}x_{ij}. </math>

Without further constraints, the <math> \{ x_{ij} \}_{i,j} </math> will effectively range over all subsets of the set of edges, which is very far from the sets of edges in a tour, and allows for a trivial minimum where all <math> x_{ij} = 0 </math>. Therefore, both formulations also have the constraints that, at each vertex, there is exactly one incoming edge and one outgoing edge, which may be expressed as the <math> 2n </math> linear equations

: <math> \sum_{i=1,i\ne j}^n x_{ij} = 1 </math> for <math> j=1, \ldots, n </math> and <math> \sum_{j=1,j\ne i}^n x_{ij} = 1 </math> for <math> i=1, \ldots, n. </math>

These ensure that the chosen set of edges locally looks like that of a tour, but still allow for solutions violating the global requirement that there is ''one'' tour which visits all vertices, as the edges chosen could make up several tours, each visiting only a subset of the vertices; arguably, it is this global requirement that makes TSP a hard problem. The MTZ and DFJ formulations differ in how they express this final requirement as linear constraints.

===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.

===Dantzig–Fulkerson–Johnson formulation===
Label the cities with the numbers 1, ..., ''n'' and define:

:<math> x_{ij} = \begin{cases} 1 & \text{the path goes from city } i \text{ to city } j \\ 0 & \text{otherwise.} \end{cases}</math>

Take <math>c_{ij} > 0</math> to be the distance from city ''i'' to city ''j''. Then TSP can be written as 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 &&  \\
     & \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; \\
     & \sum_{i \in Q}{\sum_{j \ne i, j \in Q}{x_{ij}}} \leq |Q|-1 && \forall Q \subsetneq \{1, \ldots, n\}, |Q| \geq 2. \\
\end{align}</math>

The last constraint of the DFJ formulation—called a ''subtour elimination'' constraint—ensures that no proper subset Q can form a sub-tour, so the solution returned is a single tour and not the union of smaller tours. Intuitively, for each proper subset Q of the cities, the constraint requires that there be fewer edges than cities in Q: if there were to be as many edges in Q as cities in Q, that would represent a subtour of the cities of Q. Because this leads to an exponential number of possible constraints, in practice it is solved with [[Branch and cut|row generation]].<ref>{{cite journal|last1=Dantzig|first1=G.|last2=Fulkerson|first2=R.|last3=Johnson|first3=S.|date=November 1954|title=Solution of a Large-Scale Traveling-Salesman Problem|journal=Journal of the Operations Research Society of America|volume=2|issue=4|pages=393–410|doi=10.1287/opre.2.4.393}}</ref>