# Travelling salesman, DFJ subtour elimination
#
# The same tours as the MTZ formulation, described a different way. DFJ
# needs exponentially many constraints — one per subset — where MTZ needs a
# polynomial number of potentials, but DFJ's relaxation is strictly
# stronger. In practice the subsets are separated lazily; here they are all
# written out, which is only tractable because the instance is small.
#
# Technique: One constraint per proper subset: sum of arcs inside S is at
# most |S| - 1, so no subset can close a tour of its own.
#
# On this instance the optimum is 33 (minimisation), confirmed
# independently by exhaustive enumeration before publication.
#
# Reference: Dantzig, G., Fulkerson, R. and Johnson, S. (1954). Solution of
# a large-scale traveling-salesman problem. Journal of the Operations
# Research Society of America 2(4), 393–410.
model m
set V = {1, 2, 3, 4}
set K = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
const c = {{0, 9, 5, 6},
{9, 0, 11, 14},
{5, 11, 0, 7},
{6, 14, 7, 0}}, forall i in V, forall j in V
const inS = {{1, 1, 0, 0},
{1, 0, 1, 0},
{0, 1, 1, 0},
{1, 1, 1, 0},
{1, 0, 0, 1},
{0, 1, 0, 1},
{1, 1, 0, 1},
{0, 0, 1, 1},
{1, 0, 1, 1},
{0, 1, 1, 1}}, forall k in K, forall v in V
const sz = {2, 2, 2, 3, 2, 2, 3, 2, 3, 3}, forall k in K
bin x, forall i in V, forall j 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
# no proper subset may carry enough arcs to close its own tour
constr sum_{i in V}{sum_{j in V setminus {i}}{inS_{k,i} * inS_{k,j} * x_{i,j}}} <= sz_{k} - 1, forall k in K
end
import elytica
Read this through MCP: read with path: "formulations/tsp-dfj-subtour", or resource hlpl://formulations/tsp-dfj-subtour.