Travelling salesman problem
Integer linear programming formulations

The TSP can be formulated as an integer linear program. 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.

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

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

Without further constraints, the { x i j } i, j {\displaystyle \{x_{ij}\}_{i,j}} 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 x i j = 0 {\displaystyle x_{ij}=0}. 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 2 n {\displaystyle 2n} linear equations

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.
keywords:letter_frequency, language:response_language[German]