HLPL / VerTeX Modelling Language Documentation

← lessons

TSP — MTZ subtour elimination

Forbid the cheating subtours.

Chapter: XIV — Travelling salesman · lesson id tsp-mtz · practice lesson

---

The Miller-Tucker-Zemlin (MTZ) formulation adds order variables u_i (one per city except the start) and a constraint that effectively says "if you go from i to j, then i comes before j in the tour order". This rules out any cycle that doesn't include the start node — kills the sub-tours.

u_i − u_j + n · x_{i,j} ≤ n − 1 for all i, j ∈ {2, …, n}

For our 4-city instance (n = 4), u_i lives in [1, 3]. The constraint is tight when x_{i,j} = 1 (forcing u_j ≥ u_i + 1) and slack otherwise. Run it — the true TSP optimum is 16, achieved by the tour 1 → 2 → 3 → 4 → 1.

Predict before running

Distance matrix is symmetric. What's the true TSP optimum for cities 1, 2, 3, 4?

• 12 (the assignment-relaxation answer)
• 16 (tour 1 → 2 → 3 → 4 → 1)
• 22 (the worst-case tour)

Starter code

model tsp
set C  = {1, 2, 3, 4}
set CB = {2, 3, 4}
const d = {{0, 4, 5, 7}, {4, 0, 3, 6}, {5, 3, 0, 2}, {7, 6, 2, 0}}, forall i in C, forall j in C
bin x, forall i in C, forall j in C
var 1 <= u <= 3, forall i in CB
constr x_{i,i} = 0, forall i in C
constr sum_{j in C}{x_{i,j}} = 1, forall i in C
constr sum_{i in C}{x_{i,j}} = 1, forall j in C
constr u_{i} - u_{j} + 4*x_{i,j} <= 3, forall i in CB, forall j in CB
min sum_{i in C}{sum_{j in C}{d_{i,j} * x_{i,j}}}
end

import elytica
def main():
  elytica.init_model("tsp")
  elytica.run_model("tsp")
  for i in [1,2,3,4]:
    for j in [1,2,3,4]:
      name = "x"+str(i)+","+str(j)
      print(name, "=", elytica.get_variable_value("tsp", name))
  print("obj =", elytica.get_best_primal_bound("tsp"))
  return 0

Hint

MTZ adds u variables and one constraint per ordered pair (i,j) of non-start cities.

What counts as correct

• no-error — Model solves
• numeric-match — True TSP optimum is 16 (tour 1 → 2 → 3 → 4 → 1)
• code-contains — Reads the objective from the solver (no hardcoding)

Mastery variant

Same fresh distances as the degree variant. MTZ now finds the real tour.

model tsp_v
set C  = {1, 2, 3, 4}
set CB = {2, 3, 4}
const d = {{0, 3, 8, 6}, {3, 0, 5, 9}, {8, 5, 0, 2}, {6, 9, 2, 0}}, forall i in C, forall j in C
bin x, forall i in C, forall j in C
var 1 <= u <= 3, forall i in CB
constr x_{i,i} = 0, forall i in C
constr sum_{j in C}{x_{i,j}} = 1, forall i in C
constr sum_{i in C}{x_{i,j}} = 1, forall j in C
constr u_{i} - u_{j} + 4*x_{i,j} <= 3, forall i in CB, forall j in CB
min sum_{i in C}{sum_{j in C}{d_{i,j} * x_{i,j}}}
end

import elytica
def main():
  elytica.init_model("tsp_v")
  elytica.run_model("tsp_v")
  for i in [1,2,3,4]:
    for j in [1,2,3,4]:
      name = "x"+str(i)+","+str(j)
      print(name, "=", elytica.get_variable_value("tsp_v", name))
  print("obj =", elytica.get_best_primal_bound("tsp_v"))
  return 0

Read this through MCP: read with path: "lessons/tsp-mtz", or resource hlpl://lessons/tsp-mtz.