we sum all the inequalities corresponding to for any subtour of k steps not passing through city 1, we obtain: which is a contradiction. It now must be shown that for every single tour covering all cities, there are values for the dummy variables that satisfy the constraints. Without loss of generality, define the tour as originating (and ending) at city 1. Choose if city is visited in step . Then since can be no greater than and can be no less than 2; hence the constraints are satisfied whenever For , we have: satisfying the constraint. Dantzig–Fulkerson–Johnson formulation Label the cities with the numbers 1, …, n and define: Take to be the distance from city i to city j. Then TSP can be written as the following integer linear programming problem: The last constraint of the DFJ formulation—called a subtour elimination constraint—ensures no proper subset Q can form a sub-tour, so the solution returned is a single tour and not the union of smaller tours. Because this leads to an exponential number of possible constraints, in practice it is solved with row generation. Computing a solution The traditional lines of attack for the NP-hard problems are the following: Devising exact algorithms, which work reasonably fast only for small problem sizes. Devising "suboptimal" or heuristic algorithms, i.e., algorithms that deliver approximated solutions in a reasonable time. Finding special cases for the problem ("subproblems") for which either better or exact heuristics are possible. Exact algorithms The most direct solution would be to try all permutations (ordered combinations) and see which one is cheapest (using brute-force search). The running time for this approach lies within a polynomial factor of , the factorial of the number of cities, so this solution becomes impractical even for only 20 cities. One of the earliest applications of dynamic programming is the Held–Karp algorithm that solves the problem in time . This bound has also been reached by Exclusion-Inclusion in an attempt preceding the dynamic programming approach. Improving these time bounds seems to be difficult. For example, it has not been determined whether a classical exact algorithm for TSP that runs in time exists. The currently best quantum exact algorithm for TSP due to Ambainis et al. runs in time . Other approaches include: Various branch-and-bound algorithms, which can be used to process TSPs containing 40–60 cities. Progressive improvement algorithms which use techniques reminiscent of linear