Combinatorial Optimisation

At the RAND Corporation in 1955, a study of how much freight the Soviet railway network could carry to Eastern Europe posed a question about flow through a network. Lester Ford and Delbert Fulkerson answered it in 1956: the maximum flow equals the capacity of the narrowest cut. At about the same time Edsger Dijkstra, demonstrating a new computer in Amsterdam, needed a problem the public could understand. He chose finding the shortest route between Dutch cities and designed his algorithm in twenty minutes.

In 1965 Jack Edmonds solved the matching problem for general networks, and in doing so proposed that "efficient" should mean polynomial time. That proposal became the foundation of computational complexity. When Richard Karp showed in 1972 that the travelling salesman problem and many other optimisation problems are NP-complete, the field divided: some problems have fast exact algorithms, and the rest need approximations or careful search.

A small network carries water from a source $s$ to a sink $t$ through two junctions, $a$ and $b$. Each pipe has a capacity:

Pipe	Capacity
$s \to a$	3
$s \to b$	2
$a \to b$	1
$a \to t$	2
$b \to t$	3

How much can flow from $s$ to $t$? Push 2 units along $s \to a \to t$, 2 along $s \to b \to t$, and 1 along $s \to a \to b \to t$. Every pipe stays within its capacity ($s \to a$ carries 3, $b \to t$ carries 3), and 5 units arrive.

Can more get through? Draw a line around $s$ alone. Everything leaving it must pass through $s \to a$ or $s \to b$, whose capacities add to $3 + 2 = 5$. No flow can exceed that. A set of pipes whose removal disconnects $s$ from $t$ is a cut, and no flow can exceed any cut's capacity. Here a flow of 5 matches a cut of 5, so both are optimal, and each proves the other is the best possible.

Ford and Fulkerson proved that this always happens: in every network, the maximum flow equals the minimum cut, and their algorithm finds both. The two are a matching pair of problems, one maximising and one minimising, with the same answer. That duality runs through all of linear programming, and it is what lets optimisation software certify that an answer is optimal rather than just good.

For NP-hard problems, the goal became guaranteed approximation. In 1976 Nicos Christofides, and independently Anatoliy Serdyukov, found a method that finds a travelling-salesman tour at most 50% longer than the shortest. For 44 years that was the best guarantee known, until Anna Karlin, Nathan Klein and Shayan Oveis Gharan improved it in 2020 by a fraction of about $10^{-36}$. In practice, exact methods do much better than the guarantees suggest: in 2006 an optimal tour through 85,900 locations was found and proved optimal.

Linear programming itself was proved efficient in 1979 by Leonid Khachiyan. Whether it can be solved in a number of steps independent of the size of its numbers is still open.