# Travelling salesman with MTZ subtour elimination
#
# Finds a minimum-cost Hamiltonian tour. Degree constraints alone admit
# disconnected subtours; the MTZ potentials rule them out compactly, at the
# cost of a weaker relaxation than exponential subtour cuts.
#
# Technique: Sequence potentials u_i with u_i − u_j + n·x_ij ≤ n − 1 forbid
# subtours with a polynomial number of constraints.
#
# On this instance the optimum is 25 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Miller, C. E., Tucker, A. W. and Zemlin, R. A. (1960). Integer
# programming formulation of traveling salesman problems. Journal of the ACM
# 7(4), 326–329. doi:10.1145/321043.321046
model m
set V = {1, 2, 3, 4}
const c = {{0, 11, 10, 7},
{11, 0, 1, 7},
{10, 1, 0, 11},
{7, 7, 11, 0}}, forall i in V, forall j in V
bin x, forall i in V, forall j in V
int 1 <= u <= 4, forall i in V
min sum_{i in V}{sum_{j in V setminus {i}}{c_{i,j} * x_{i,j}}}
constr sum_{j in V setminus {i}}{x_{i,j}} = 1, forall i in V
constr sum_{j in V setminus {i}}{x_{j,i}} = 1, forall i in V
# MTZ potentials: no subtour can close without violating the ordering
constr u_{i} - u_{j} + 4 * x_{i,j} <= 3, forall i in V setminus {1}, forall j in V setminus {i, 1}
end
import elytica
Read this through MCP: read with path: "formulations/tsp-mtz", or resource hlpl://formulations/tsp-mtz.