The assignment problem is a relaxation of the travelling salesman problem: it forces one departure and one arrival per city and permits several disjoint subtours. The constraints that would forbid them are exponentially many, so they are added only when a solution actually violates one. Relaxation, cut, branch, repeat solves small instances exactly — and a heuristic tour is only as good as the bound you can measure it against.
Core ideas
One hard idea: the relaxation here is not “drop integrality” but “drop one requirement”, and the requirement it drops is the one that makes a tour a tour.
Choose, for each city, one city to leave for and one to arrive from, at minimum total cost. Every tour satisfies that; so does a set of disjoint subtours, which is not a tour at all. So the assignment optimum is a lower bound on the tour, and the subtours it returns are the exact way in which it failed to be an answer.
There is one subtour-elimination constraint for every proper subset of the cities, which is exponentially many and cannot be written down. They are also almost all slack at the optimum, so they are added when a solution violates one: solve, find the shortest subtour, forbid an arc of it, re-solve. That is the branching, and it is a cut in the sense of the previous lesson.
A nearest-neighbour tour on the lab's six-city instance costs 96. Whether that is good is not a question the tour can answer. Against the optimum of 88 it is 8 worse, a measured 1/12 of the tour in hand; and improving it by 2-opt gives 88 exactly, which is optimal — a fact that only the bound could have established.
The material
How many tours there actually are, where the bound comes from, and why a measured gap and a proved ratio are different kinds of knowledge.
Before any method, the count — because three different numbers are in circulation and each is correct for something else. On n cities there are n! orderings of the cities; (n − 1)! tours from a fixed start, counting each once per direction; and (n − 1)!/2 distinct undirected tours, which is what you are choosing among when the cost from one city to another is the same both ways.
Those 360 at seven cities are why the lab stops at seven: 360 tours can be enumerated instantly, so an exact answer is available to check every bound against, and that is worth more at this size than another city. The cap is this lab's own and it is a consequence of (n − 1)!/2 — nothing to do with the n! orderings that Discrete Mathematics’ Hamilton lab enumerates, which is a different quantity on a different object.
The claim “the number of tours is n!” is therefore an overcount by a factor of 2n: at seven cities 5040 against 360, and 5040 ÷ 360 = 14 = 2 × 7. The factor n is the arbitrary choice of starting city and the factor 2 is the direction, neither of which changes the tour or its length.
For a proper non-empty subset S of the cities, the constraint says that the chosen arcs may not form a closed cycle inside S: at least one arc must leave S. There is one such constraint per subset, so there are exponentially many, and a formulation that wrote them all down could not be built for a moderate n.
On the lab's opening instance the assignment relaxation is worth 80, and it returns three two-city subtours: cities 1 and 5 shuttling between each other, 2 and 3, and 4 and 6. That is a bound and not a route. Forbid one arc of the shortest subtour and re-solve; two of the children come back with a four-city subtour and a two-city one, still not a tour; forbid an arc again and the next child is a genuine tour worth 88. Five nodes in total, and the answer 88 is the route 1 → 2 → 4 → 6 → 3 → 5 → 1.
Nearest neighbour from city 1 gives 1 → 5 → 3 → 4 → 6 → 2 → 1, costing 96. Against the optimum of 88 that is 8 worse, which is 8/96 = 1/12 of the tour in hand — a measured gap, on this instance, for this heuristic, which the panel shows as 8.3%. with a gap of zero. That happens, and it is worth knowing rather than assuming, which takes a bound.
A measured gap and a proved ratio are different kinds of knowledge and the difference is worth a paragraph. The Algorithms path’s “Metric TSP by MST Doubling” proves a factor of two for every metric instance there is, for ever, without solving any of them. This lesson measures 1/12 on one instance, exactly, and claims nothing about the next one. The first is a theorem about a class; the second is a fact about a case — and on your own data, the fact is often what you need and is the only one of the two you can compute.
Three results are used here and proved elsewhere. The other exact method is the dynamic programme over subsets of “DP over Subsets: Held–Karp”, which runs in n² 2ⁿ time — a different trade, since it beats (n − 1)! badly and still grows exponentially. Why the problem is hard at all is “Reductions and Their Direction”, in the same subject. And the two-approximation above is that path's as well. None of the three is derived here.
The apparent tension between “hard” and “solved exactly in five nodes” is not one. Hardness is a statement about every instance of every size; a certificate is a statement about the instance in front of you. Branch and cut solves small and structured instances routinely, and the gap it reports on the ones it cannot close is exactly the honest form of the same fact — which is what this course has been building toward since the first rounded point failed.
Every cost in the lab is an integer or a fraction, so every tour length, every bound and every gap on the page is exact. That is deliberate: the one place this problem could produce an irrational number is a Euclidean distance, and a comparison between two tours that differs in the sixth decimal place is not a comparison anybody should be making on a rounded value.
Interactive
A relaxation that leaves subtours, the cuts that forbid them, and a heuristic with a number attached
Method
Five steps, and the count in the first one is what keeps the last one honest.
(n − 1)!/2 distinct undirected tours: 60 at six cities, 360 at seven, 2 520 at eight. Enumeration is the right method for exactly as long as that number is small, and knowing where that stops is why the other four steps exist.
One departure and one arrival per city, at minimum cost. Its value is a lower bound on every tour. If it happens to return a single cycle, that cycle is the optimal tour and you are finished.
The shortest subtour is the cheapest one to break and gives the fewest children. Forbidding one arc is a cut: no tour is lost, because a tour cannot contain that subtour anyway. The panel names the banned arc by its raw index, so the city drawn as 1 appears in that column as 0.
Each child is another assignment problem with one arc forbidden, so the bound rises as arcs are banned. Close a node the moment its bound cannot beat the best tour in hand — the three closing reasons are the ones from the search lesson.
A tour of 96 is a number. A tour of 96 against a proved optimum of 88 is a result: 8 worse, 1/12 of it. Without the second number, “near-optimal” has nothing behind it.
The lab's opening instance at six cities, with the costs symmetric. Every figure is exact and every one can be checked against the panel.
Node 0's three two-city subtours are the clearest possible picture of what the relaxation dropped. Shuttling between two plants satisfies “one departure and one arrival each” perfectly, costs very little, and visits nothing. The 8 between 80 and 88 is the price of the requirement that the route be one cycle.
Node 2 is closed by the bound at 88, equal to the best tour in hand, which is the same closure the search lesson used: nothing in a node beats the node's bound. And node 3 is a reminder that a node returning a tour does not return the best one — 96 is a genuine tour and it is beaten two nodes later.
For a faded rehearsal, raise the lab to seven cities. The supplied first move is the count: (7 − 1)!/2 = 360 distinct undirected tours, six times the sixty at six cities. Predict whether the root bound rises or falls when a city is added, then read the optimum, the node count, and the measured gap of the 2-opt tour — which this time is not zero.
You should be able to say how many distinct undirected tours a size has and why the other two counts are counts of something else, solve the assignment relaxation and name the subtours it leaves, add a subtour cut and branch to an optimal tour with its certificate, and report a heuristic tour with its measured gap while distinguishing that from a proved ratio.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.