Relaxation:
solve the easier problem

Plan a road trip. Twenty cities, visit each one exactly once, come home, and drive the shortest total distance. That's the whole spec. It sounds like a puzzle — a rainy-Sunday, back-of-an-envelope, surely-there's-a-trick sort of puzzle.

There isn't a trick. Checking every route means checking every ordering of twenty cities, and there are about 6 × 10¹⁶ distinct ones — more orderings than you have atoms in a fingernail, more than a modern laptop could grind through before your trip is a historical event. And no, you can't just be cleverer. People have been looking for a shortcut since the 1950s. Seventy years, some of the sharpest minds alive, a million-dollar prize sitting on the table. Nothing.

This is the travelling salesman problem, and it belongs to a family of problems we call intractable — or, more precisely, NP-hard. That word gets misused constantly, so let's be exact about it. Intractable doesn't mean “hard.” Hard problems yield to effort. Intractable means: the exact answer costs more than it is worth, and it always will. The cost doesn't shrink when the hardware gets faster — it's exponential, so faster hardware buys you one or two more cities and then the wall is back.

Delivery routing, chip layout, exam timetabling, protein folding, seating a wedding, packing a truck — all of them are this problem wearing a different hat. Which means “just compute the optimum” is off the table for an enormous slice of the things people actually want computed.

Here's the move. You can't solve the real problem, so you don't. You delete one of the rules you were supposed to obey, solve that problem instead, and look hard at the answer you get.

The obvious objection arrives immediately: the answer is wrong. You cheated. It describes a world that doesn't exist — a road trip where you teleport, a wedding where you invite 0.6 of a person, a rule that everyone politely ignores. Of course it's wrong.

But look at what you bought. The cheating version is easier — you removed a rule, so every real answer is still a legal answer in the loosened world. Nothing got ruled out. Which means the fantasy answer is at least as good as the real one, always, with no exceptions. And that is not a guess. That's a fact you can hold onto: whatever the true optimum is, it can't be better than this.

So now you know where the finish line is, without having run the race. Your real, achievable, boring answer sits some distance above it — and you can measure that distance. The gap between the fantasy and the reality is the whole trick. It's the difference between “here's my best shot, fingers crossed” and “here's my answer, and it is provably within 12% of perfect.”

This is relaxation, and it comes in three flavours, in ascending order of subtlety: delete the rule, blur the rule, or put a price on the rule.

The bluntest version: pick a rule, cross it out, and see what falls out.

Back to the road trip. The rules are: visit every city, form one continuous loop, don't revisit anything, come home. Cross out most of them. Say you're allowed to teleport back to any city you've already visited, branch off in any direction, and never bother closing the loop. All you have to do now is touch every city with the cheapest possible set of roads.

That problem is easy. Greedily connect the nearest unconnected city, over and over, and you're done — no cleverness, no backtracking, no exponential anything. The result is a minimum spanning tree, and it drops out in a blink even for a thousand cities.

Now the payoff. Every real tour is, if you squint, a way of connecting all the cities — so no tour can ever be cheaper than the cheapest possible connection. The spanning tree is a floor under the true optimum, and you got it for free. Better still, you can walk the tree — trace it out and skip the cities you've already seen — and you get a genuine, legal tour whose length is provably at most twice the tree. In practice it lands within about 40% of optimal, and Christofides' algorithm — same idea, plus a bit of patching to fix up the odd-degree cities — tightens that guarantee to 50% worst case while typically landing within 10%. For thirty years that was the best guarantee anyone had for the general problem.

Drag the cities around below. Watch the brute-force count detonate as you add them — and watch the tree, which never breaks a sweat, quietly print a floor under an answer nobody can compute.

The everyday translation is a question you can ask out loud in a meeting: “If we had unlimited budget and unlimited time, what would we do?” People treat that as a daydream. It isn't — it's a constraint relaxation, and it does two jobs at once. It bounds the real answer (you now know the ceiling on how good this could ever get, so you know whether the whole project is even worth it). And it shapes the real answer: the fantasy plan and the achievable plan differ in specific places, and those places are exactly where a constraint is costing you.

Nobody's plan survives contact with the real constraints. That was never the point. The fantasy plan's job is to tell you which constraint is actually the problem — because in almost every case it's one, and it isn't the one you've been arguing about.

Here's a strange fact about a huge number of hard problems: they're hard only because the answers have to be whole things.

You can't hire 0.6 of a guard. You can't send half a truck to Rotterdam. You can't seat 40% of your uncle at the family table. That single innocent word — whole — is what turns a smooth, solvable, hundred-lines-of-linear-algebra problem into a combinatorial nightmare where you're fishing through 2ⁿ subsets hoping one of them works. Take the whole-numbers rule away and the same problem is solvable in polynomial time, reliably, at industrial scale, by software that's been battle-tested since the 1940s.

So: take it away. Let the variables go fractional. Solve the smooth version fast. Then round — snap the fractions back to whole numbers — and accept that you've landed a bit above optimal. This is discrete optimisation collapsing into a linear programming relaxation, and it is, quietly, one of the load-bearing beams of the modern economy. Airline crews, warehouse robots, factory schedules.

Below: a building of rooms and corridors. Every corridor needs a guard standing at one end or the other. Fewest guards wins. Grind it out in whole guards and you're enumerating subsets. Allow fractions and the answer arrives instantly — including, absurdly, three half-guards standing around a triangle of corridors, because half a guard at each of three corners covers all three corridors at a total cost of 1.5, which no whole guard can match.

The rounded answer isn't optimal. It never is. But it comes with a receipt: because every fraction was at most doubled on the way up, the rounded answer is at most twice the fractional one — and the fractional one is a floor under the true optimum. Two lines of reasoning, and you've shipped an answer with a written guarantee attached. Nobody had to find the optimum for you to know how close you are to it.

The same trick has a dozen faces. Colouring a graph so no two neighbours match (which is exam timetabling, and register allocation, and radio frequencies). Choosing which warehouses to open. Seating a wedding so the divorced cousins don't collide. Each one is a nightmare in whole numbers and a Tuesday afternoon in fractions.

The third one is the subtlest, and it's the best. Instead of deleting the rule, you keep it — and make it breakable for a price.

That sounds like a distinction without a difference. It isn't. Delete a rule and the solver forgets it existed; the answer you get back is a fantasy with no memory of what it cost you. Put a price on the rule and the solver still feels it — it will obey the rule everywhere obeying is cheap, and break it only where breaking is genuinely, arithmetically worth more than the fine. “Impossible” becomes “expensive,” and the moment that happens, the entire space of answers is searchable again, because there's nothing left that's off-limits — only things that are dear.

And then comes the part that makes this a diagnostic and not just a solver. You look at where it chose to pay. Those spots — and there are usually very few — are the places your constraint is actually binding. Everywhere else, the rule was free. You've just been handed a map of exactly which part of your problem the rule is costing you, which is a thing no amount of staring at the spec would have told you.

This is how professional sports leagues get scheduled. The NFL, college basketball — thousands of games, stadium availability, TV windows, travel, and the rule that no team plays too many away games back-to-back. Deleting that rule gives you a schedule nobody will accept. Pricing it gives you a schedule that's almost perfect and breaks the rule twice, in the two places where the alternative would have been miserable. It's also how you know a game designer has done their job: nothing in a good game is forbidden, everything just has a cost.

Below, one team's ten-week season. Five home games, five away. Weeks 5 through 7 the stadium is a disaster to play in, so away is worth a fortune — but three aways in a row breaks the rule. Drag λ from “the rule is a suggestion” to “the rule is a law” and watch what the solver does in between.

Watch the middle of that slider. At λ = 0 the solver is a sociopath — it breaks the rule twice because the rule costs nothing. Crank λ to the ceiling and it obeys perfectly, at a cost of ten points of season value. But in the wide band between, it does something no rulebook could have told it to: it breaks the rule exactly once, in week 7, and pays for it happily. That one violation is worth 8 points. Everywhere else, obedience was free.

You now know something you didn't know before you started: this constraint isn't costing you a season. It's costing you week 7. Go argue with the league about week 7.

Let's draw the line that this entire chapter is actually about, because it's easy to miss.

“I couldn't find the best route, so I did my best” and “I couldn't find the best route, so I did this one, which is within 27% of the best” are not two grades of the same answer. They're different kinds of object. The first is a shrug. The second is a bound — a mathematical statement about a thing nobody has ever seen and nobody ever will.

That's the strange, lovely part. You are making a hard claim about the optimal tour. You have not found the optimal tour. You will never find the optimal tour. And yet you can say, with the same confidence you'd say 2 + 2 = 4, that it is not more than 27% better than the thing in your hand. The relaxation didn't approximate the answer. It proved something about the answer.

This is the honest engineer's superpower, and it's a superpower precisely because it changes what you can decide. If your answer is provably within 5%, chasing the rest is a waste of a quarter and you can say so in a meeting with numbers behind you. If the bound is 300%, you have no idea what you're doing and you now know that too — which is worth more than the false comfort of an answer with no error bars. A bound tells you when to stop. Nothing else does.

The whole idea fits in one small function. Compute a tour any way you like — here, greedy nearestNeighbourTour. Then compute the relaxed thing, the spanning tree, with mstLength. Return both. The ratio between them isn't a diagnostic or a heuristic or a confidence score — it's a theorem, holding the answer you actually shipped. Flip between the languages; the shape is identical.

The practical version is a question, and you ask it when you're stuck: which rule am I obeying that I didn't have to?

It's a better question than it looks, because the honest answer is usually embarrassing. A surprising share of the impossible problems in a life or a codebase are only impossible because of a constraint nobody chose and everyone inherited. The deploy has to be atomic — does it? The whole team has to agree — do they? You have to see everyone at the wedding — do you? Somebody, once, had a reason. Then the reason left and the rule stayed, and now it's load-bearing in a structure it was never designed to hold up.

So relax it. Not forever — for one honest minute. Solve the version where the constraint isn't there and look at what you get. Sometimes the fantasy answer is barely better than what you already have, which is genuinely good news: the constraint is free, stop worrying about it, the problem is elsewhere. Sometimes it's wildly better, and you've just found the one thing worth fighting about.

And then — this is the part people drop — you come back and pay the difference. Relaxation isn't an excuse to live in the fantasy version; the fantasy version is a measuring instrument, not a plan. You go back to the real problem carrying a number you didn't have before. That's the whole discipline: cheat, measure, return, pay.

Which leaves an obvious loose end. All three relaxations are still doing something deterministic and thorough — smaller, but thorough. The next chapter takes the last step off the cliff: what if you didn't even try to be systematic? What if you just... guessed?

Relaxation shrank the problem until it fit. The next chapter does something that sounds like giving up entirely and is in fact the opposite: it throws dice. Sampling instead of enumerating, guessing instead of proving — and getting an answer that's better, faster, and more reliable than the thorough one. Randomness isn't what you do when you've run out of ideas. Sometimes it is the idea.