= Compact order formulation of the travelling salesman problem
Use binary directed-edge variables $x_{ij}$, one incoming and one outgoing edge at each city, and integer order variables $1\leq u_i\leq n-1$ for cities other than a distinguished city. The constraints $u_i-u_j+(n-1)x_{ij}\leq n-2$ for distinct nondistinguished cities force order increase along every selected edge away from the distinguished city. Summing around any cycle avoiding that city gives a contradiction, so the degree equations describe a single tour. There are $O(n^2)$ nonzero constraint entries apart from the degree equations, also totaling $O(n^2)$ entries. With costs at most $2^n$, the objective requires $O(n^3)$ bits and the remaining sparse constraint encoding $O(n^2\log n)$ bits. Omitting zero matrix entries is essential for this particular size bound.
Back to article page
