HLPL / VerTeX Modelling Language Documentation

← lessons

TSP — degree constraints (assignment trap)

Force exactly one in and one out per city.

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

---

Force each city to have exactly one outgoing and one incoming edge — the assignment relaxation of TSP. Looks right? Not quite.

Run it. The solver returns cost 12 — cheaper than the true TSP optimum of 16! It found two 2-cycles: 1↔2 (cost 4 + 4 = 8) and 3↔4 (cost 2 + 2 = 4). Two disconnected sub-tours instead of a single Hamiltonian cycle.

This is the classic assignment-relaxation trap. We need extra constraints to forbid subtours — that's the next lesson.

Predict before running

Add degree constraints (one in, one out per city). How does the cost compare to the true TSP optimum?

• Equal. Degree constraints are enough for TSP
• Lower. Relaxations under-estimate the true optimum
• Higher. Degree constraints make things harder

Starter code

model tsp
set C = {1, 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
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
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

Run it. Note the impossibly-low cost — the solver cheated by picking subtours.

What counts as correct

• no-error — Model solves
• numeric-match — Assignment-relaxation cost is 12 — two subtours, not a tour
• code-contains — Reads the objective from the solver (no hardcoding)

Mastery variant

New distance matrix. Spot the subtour trap on a fresh instance.

model tsp_v
set C = {1, 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
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
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-degree", or resource hlpl://lessons/tsp-degree.