Hungarian algorithm

Forty couriers wait at random intersections in Almaty, and orders are ready in forty cafés and restaurants, whose places are taken from OpenStreetMap. We need to decide who goes for which order, so that together the couriers drive as little as possible along the streets. The first thing that comes to mind is to give each order to the nearest free courier. The second is to take the shortest remaining pair again and again. The first gives 140.6 km, the second 138.6, and the best assignment is 121.5 km. It cannot be found by trying everything: there are 40! assignments, a number of 48 digits. The Hungarian algorithm finds the best in less than a millisecond.

Switch methods. For “shortest pair first” the red line, the longest trip, is 12.9 km across half the city: the short pairs are taken, and the last couriers get the orders that are left, and what is left are exactly the awkward ones. With ten couriers this gives a trip of 15.8 km. Nearest free goes wrong differently: the first orders take couriers who would be more needed by the next ones, and with eighty couriers it drives 256.2 km against 191.7 for the best assignment, a third more.

The idea

The costs are conveniently written as a table: a row is a courier, a column an order, and a cell the length of the route along the streets. An assignment is a choice of one cell in each row and each column, and we need the choice with the smallest sum. This is the assignment problem; in the language of graphs, a minimum-weight matching in a complete bipartite graph, as in the article on matchings, only now the edges have a cost.

Give each courier and each order a number, a potential, so that for any pair the potentials add up to no more than its cost. Call the pairs where the sum of potentials equals the cost tight. If everyone can be assigned using only tight pairs, the assignment is the best, and the potentials prove it. The algorithm adds couriers one at a time, and when there are not enough tight pairs it shifts the potentials so that a new tight pair appears and none of the old ones is spoilt.

Why less is impossible

Let c_ij be the cost of the pair “courier i, order j”, u_i the courier’s potential, v_j the order’s potential, and for all pairs u_i + v_j ≤ c_ij. The difference c_ij − u_i − v_j ≥ 0 is called the reduced cost; for tight pairs it is zero.

The converse also holds: for the best assignment such potentials can always be found. This is a special case of the duality theorem of linear programming, and for this problem it was proved in 1931 by Jenő Egerváry. The Hungarian algorithm proves it once more, constructively: it hands over both the assignment and the potentials. The listing below checks this: for forty couriers the sum of the potentials is the same 121.5 km, 113 of the 1600 pairs are tight, and all 40 pairs of the answer are among them. Anyone who doubts the answer can check it with n² comparisons without repeating the search.

How the potentials move

Start with zero potentials: with non-negative costs all the inequalities hold. Add couriers one at a time. A new courier i looks for an order along tight pairs. If a tight pair leads to a free order, done. If to a taken one, you can try to move its courier: that courier looks for another order along their own tight pairs, and so on. The couriers and orders reached by such a search from i form a tree. If a free order turns up in the tree, all the couriers along the way to it shift to the next order, the path flips, and one more is assigned. This is the same augmenting path as in the algorithm for matchings, only it runs along tight pairs.

If the tree is stuck and there are no free orders in it, find δ, the smallest reduced cost from the couriers of the tree to orders outside it. Add δ to the potentials of all the couriers of the tree and subtract δ from the potentials of all the orders of the tree.

After the shift the tree grows by the new tight pair. If its order is free, the path is found; if taken, its courier joins the tree, and the search continues. Each shift adds an order to the tree, so there are at most n shifts per courier. If for each order outside the tree we keep the smallest reduced cost to it from the tree, a shift costs O(n): find the smallest and update the array. There are n couriers, O(n³) in all.

Look closely and this is Dijkstra’s algorithm in reduced costs: the array of smallest costs is the distances, the tree is the vertices already found, δ is the distance to the next one. The potentials make all the reduced costs non-negative, and that is why Dijkstra works here, the same technique as in Johnson’s algorithm for graphs with negative edges.

Six couriers and six orders from the same map, 25 steps. Couriers 1, 3 and 5 find a free order at once: one shift is enough for them. Courier 2 wants order B, already given to the first, and the first moves over to E. The last, sixth courier passes through three taken orders, D, A and E, the potentials shift four times, and when the path flips two more move over. The sum of the potentials stays a lower bound on the answer the whole time and by the end reaches 37.0 km, the cost of the best assignment. “Nearest free” and “shortest pair first” give 40.1 km each on these same six.

Code

The listing computes distances along the streets with forty runs of Dijkstra, then assigns in three ways and checks the answer with the potentials. The hungarian function is the classic short form of the method: column 0 is a dummy where the courier being added is placed, minv holds the smallest reduced costs to orders outside the tree, way where we came from, to flip the path.

The most expensive part here is not the assignment but the cost table: forty runs of Dijkstra over 7909 intersections. The Hungarian algorithm itself for 40 × 40 is tens of thousands of simple operations. The scene above shows the same picture: Dijkstra takes tens of milliseconds, the assignment less than one.

What it costs

For hundreds and thousands of couriers O(n³) is more than enough. When n is in the tens of thousands and each courier has only a few reasonable orders, the full table is not built: only close pairs are kept, and the same shortest augmenting paths are sought over a sparse graph. The variant of Roy Jonker and Ton Volgenant (1987) is also built on shortest augmenting paths; the linear_sum_assignment function in SciPy is its version without the initial placement.

Variants

More couriers than orders. The orders are made the rows and the couriers the columns: the algorithm works with a rectangular table with no more rows than columns, and the extra couriers are simply left without a pair.

The largest sum. If what is needed is not the smallest cost but the largest gain, it is enough to change the sign of all the numbers, or subtract all the numbers from one big one so that the costs stay non-negative.

Forbidden pairs. A pair that is impossible, the courier will not make it in time, the order is not on their route, is replaced with a very large cost, greater than any feasible assignment. If such a pair still ends up in the answer, there is no feasible assignment.

Nobody drives far. The smallest sum may send one courier across the whole city. If the longest trip matters more, it is found by binary search on a threshold: is there an assignment in which all pairs are no longer than the threshold; that is a question about a matching. And among such assignments the smallest sum is found by the Hungarian algorithm with forbidden pairs. That is the second problem below.

Auction. Dimitri Bertsekas proposed in 1979 treating the potentials as prices: a free courier chooses the order most profitable for them and raises the bid on it by as much as that order is more profitable than the second best. Such an auction divides well between processors and runs fast on sparse problems.

Minimum-cost flow. If a courier has several places in the bag and a café several orders, the problem becomes a minimum-cost flow; the Hungarian algorithm is its special case where all capacities are one.

Orders arrive one at a time. The nearest free courier is a “here and now” decision, and the scene shows what it costs. If you wait and collect orders for a few seconds, the assignment problem can be solved on the collected ones: the assignment gets better, and the wait longer. Where the balance lies depends on what is dearer: a customer’s minute or a courier’s kilometre.

History

In the summer of 1953 Harold Kuhn was working on the assignment problem and reading Dénes Kőnig’s 1936 book on graph theory. In it Kuhn found the theorem on matchings, in essence duality for tables of zeros and ones, and a footnote to a 1931 paper by Jenő Egerváry that generalised it to any numbers. The paper was written in Hungarian with a short summary in German. By Kuhn’s own recollection, it took a grammar, a big dictionary and two weeks to learn the language well enough to translate it, and the paper contained an idea that reduces the general problem to a sequence of problems with zeros and ones. Kuhn published the method in 1955 and called it Hungarian, in honour of Kőnig and Egerváry.

In the autumn of 1953 Kuhn solved 12 × 12 problems with three-digit numbers by hand in under two hours each. Kuhn’s claim that no machine in the world had then been programmed for linear programs of that size was later disputed: a 10 × 10 problem had already been solved by the simplex method on the SEAC machine. But in 1956 Ford and Fulkerson reported that on a 20 × 20 problem the simplex method ran for more than an hour, while the Hungarian method took about half an hour by hand. Many thought the Hungarian method a variant of the simplex method; Kuhn won a bet about this with Alan Hoffman, when Hoffman conceded that it was not.

In 1957 James Munkres showed that the method runs in polynomial time, hence the second name, the Kuhn–Munkres algorithm. The O(n³) bound with potentials and shortest paths was obtained in the early 1970s by Jack Edmonds with Richard Karp and independently by Tomizawa. And in 2006 François Ollivier wrote to Kuhn: among the papers of Carl Jacobi, who died in 1851, an algorithm for the same problem had been found, in Kuhn’s words essentially the same Hungarian method, a hundred years earlier.

Problems

The first is the assignment problem itself; the tests include tables of distances along the streets of Almaty. In the second the longest trip must first be made as short as possible, and only then the sum.