Modeling the TSP as an ILP — Interactive Chapter

Symmetric TSP

Decision variables

In the symmetric TSP, the cost of traveling from city i to city j is the same as the cost of traveling from j to i. So the model can use one binary variable for each undirected segment:

x_ij = 1 if segment {i,j} is used in the tour,

x_ij = 0 otherwise.

The objective is linear because each selected segment contributes its cost exactly once.

minimize ∑_{i,j} c(i,j)x_ij

Degree constraints

Every city has degree 2

A valid tour enters and leaves every city. In the undirected model, this becomes exactly two selected segments incident to each city:

∑_j=1ⁿ x_ij = 2 for every city i.

These constraints are necessary but not sufficient. They describe a 2-factor: one Hamiltonian cycle, or several disconnected cycles that each give degree 2 at every city.

Subtour elimination

Cut constraints rule out disconnected cycles

For any nonempty strict subset S of cities, a real tour must leave S and later return. Therefore at least two selected segments cross between S and its complement.

∑_i∈S ∑_j∉S x_ij ≥ 2

for every strict nonempty S ⊂ {1,2,…,n}.

If the current 2-factor has a component C with no selected edges leaving it, then the left-hand side is 0. Adding the constraint for C cuts off exactly that subtour solution.

Complete formulation

Subtour-elimination ILP

minimize  ∑{i,j} c(i,j)xij
subject to  ∑jxij = 2 for every city i
    ∑i∈S∑j∉Sxij ≥ 2 for every strict nonempty S
    0 ≤ xij ≤ 1, integer, for every segment {i,j}.

Once the degree constraints and all subtour constraints hold, following selected edges from any city cannot close early. The selected edges must form one tour through all cities.

Interactive ILP workbench

Solve the relaxation, find subtours, add cuts

The solver is exact for small instances: it enumerates all degree-2 binary edge sets and keeps only those satisfying the active subtour cuts. This is meant for teaching, not large TSP instances.

n = 6

Load an instance or solve the current one.

Current relaxation

Objective

—

Active cuts

0

Components

—

Selected edges

—

No selected edge set yet.

Selected subset S

Turn on “select subset S” and click cities.

Active subtour cuts

No subtour-elimination cuts have been added.

Cost matrix and current ILP

Symmetric cost matrix

Edit an upper-triangular entry to change the cost of segment {i,j}. Editing costs turns off “costs follow positions.”

Model generated from this instance

Scale

Why not write every subtour constraint?

For n cities, there are n(n−1)/2 binary edge variables and n degree constraints. But the raw number of nonempty strict subsets is 2ⁿ−2, so the subtour constraints grow exponentially.

cities 27

edge variables

351

degree constraints

27

raw subtour cuts

134,217,726

unique up to complement

67,108,863

At 27 cities, the raw family already has 134,217,726 subtour-elimination constraints. Adding one city roughly doubles this family.

Laziness for the win

Repeatedly adding constraints

Start with 𝒞 = ∅.
Solve the ILP with degree constraints and cuts only for S ∈ 𝒞.
If the selected edges form subtours, add a cut for one subtour and repeat.
If the selected edges form one tour, stop.

The current model is always a relaxation of the full subtour-elimination ILP. Therefore its optimum is a lower bound on the optimal tour length. When the relaxation optimum itself is a tour, the lower bound is achieved by a feasible TSP solution, so the tour is optimal.

Cutting-plane picture

Cut off the current wrong optimum

Ignoring constraints enlarges the feasible region. If the relaxed optimum violates a missing constraint, adding that constraint removes the current solution while preserving every true tour.