 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\le u_i\le n-1$ for cities other than a distinguished city. The constraints $u_i-u_j+(n-1)x_{ij}\le 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.