Editing Travelling salesman problem (section)

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