D2 2.1 - The Hungarian algorithm

D2 2.1 - The Hungarian algorithm

You will reduce cost matrices, obtain an optimal one-to-one allocation, adapt the table for idle workers and forbidden assignments, and convert maximum profit into minimum cost.

One worker, one task, one independent choice

How can an algorithm turn a table of positive costs into a table of zeros without making any real job free? The zeros will measure costs after common adjustments. We will use them to identify a cheapest assignment, then return to the original bill.

You already know

A table has rows and columns. Choosing one entry in every row and every column selects one item from each group, and the total cost is the sum of the selected costs.

An allocation problem might assign workers to tasks, machines to jobs or drivers to vehicles. Here each worker can do at most one task, and each task must be done by exactly one worker.

Complete allocation and independent zeros

In a square nn-by-nn cost matrix, a complete allocation chooses nn entries, exactly one in every row and every column. Zeros are independent when no two chosen zeros share a row or a column.

A complete allocation of independent zeros in a valid reduced cost matrix identifies an optimal allocation for the original problem.

A zero in every row is not enough. Two workers may have their only zero in the same task column, and both cannot take that task.

There is a useful reason that matrix reduction can work. If 100100 pounds is added to every entry in worker A's row, every complete allocation becomes 100100 pounds dearer: it chooses exactly one of those entries. The order of the allocations from cheapest to dearest is unchanged. The same idea works for any whole column and for subtraction.

Key idea

The Hungarian algorithm changes costs in ways that preserve which complete allocation is best. It seeks enough independent zeros, not simply as many zeros as possible.

Test the difference between “every row has a zero” and “a complete zero allocation exists”.

Reduce rows first, then columns

Keep the worker and task order fixed. Pearson's procedure reduces rows first: subtract the smallest entry in each row from every entry of that row. Then subtract the smallest entry in each column of the row-reduced matrix from every entry of that column.

Cost matrix reduction

Row reduction subtracts one row minimum from that entire row. Column reduction then subtracts one column minimum from that entire column. The reduced entries are non-negative.

If a complete allocation of independent zeros is available, select it and calculate the total from the original table.

Every complete allocation loses the same sum of row minima and column minima. Therefore its comparison with every other complete allocation is preserved. If an allocation now totals zero, no other reduced allocation can be cheaper.

Not in the formula booklet: learn it.

Worked example 1: a zero allocation after reduction

Question. Workers A, B, C must do tasks P, Q, R, one each. Costs in pounds are

PQRA738B486C279\begin{array}{c|rrr} &\mathrm P&\mathrm Q&\mathrm R\\\hline \mathrm A&7&3&8\\ \mathrm B&4&8&6\\ \mathrm C&2&7&9 \end{array}

Use the Hungarian algorithm to find a minimum-cost allocation.

Plan. Reduce rows, reduce columns, then seek three independent zeros.

The row minima are 3,4,23,4,2. Subtract them to obtain

(405042057)\begin{pmatrix} 4&0&5\\ 0&4&2\\ 0&5&7 \end{pmatrix}

The column minima are now 0,0,20,0,2. Column reduction gives

(403040055)\begin{pmatrix} 4&0&3\\ 0&4&0\\ 0&5&5 \end{pmatrix}

Choose zeros AQ,BR,CPAQ,BR,CP.

Why choose BRBR, rather than BPBP? C needs P for its only zero, so using BP would block a complete zero allocation.

Answer. Assign A to Q, B to R and C to P. The original total cost is 3+6+2=113+6+2=11 pounds, and it is minimal.

Check. Every worker and task is used once. The sum removed was 3+4+2+2=113+4+2+2=11, and the selected reduced entries total zero, consistent with original cost 1111.

Worked example 2 adds 22 pounds to every original cost in A's row, changing it to 9,5,109,5,10. All other entries stay fixed.

Worked example 2: a common row change preserves the choice

Question. Find a minimum-cost allocation for

(9510486279)\begin{pmatrix} 9&5&10\\ 4&8&6\\ 2&7&9 \end{pmatrix}

with the same worker and task order.

Plan. Repeat row-first reduction and compare the resulting zeros.

Subtract row minima 5,4,25,4,2:

(405042057)\begin{pmatrix} 4&0&5\\ 0&4&2\\ 0&5&7 \end{pmatrix}

Subtract column minima 0,0,20,0,2:

(403040055)\begin{pmatrix} 4&0&3\\ 0&4&0\\ 0&5&5 \end{pmatrix}

The independent zeros again give AQ,BR,CPAQ,BR,CP.

Why did the reduced table stay the same? Every entry in A's row and its row minimum rose by the same amount, so subtracting the minimum cancelled that common change.

Answer. A to Q, B to R, C to P, with original cost 5+6+2=135+6+2=13 pounds.

Check. Every complete allocation uses A once, so all original totals have risen by 22; the old minimum 1111 becomes 1313.

Several zero choices can look promising. Reserve columns needed by rows with only one available zero, and reconsider a tentative choice if it blocks completion.

Watch out

Wrong: reduce columns first, subtract a different value from different entries of the same row, or quote zero as the real total. Right: reduce rows first, then columns, and return to the original entries to cost the allocation.

Add another 22 pounds to every cost in A's row.

Cover zeros and improve the reduced matrix

When a complete independent zero allocation is impossible, cover every zero using the smallest possible number of horizontal and vertical lines. Lines run along whole rows or columns; they are not arbitrary diagonal strokes.

Hungarian improvement step

For an nn-by-nn matrix, if fewer than nn lines suffice to cover all zeros:

  1. Find the smallest uncovered entry, ee.
  2. Subtract ee from every uncovered entry.
  3. Add ee to each entry covered twice.
  4. Leave entries covered once unchanged.

Cover the new zeros with a minimum number of lines and repeat if necessary. When nn independent zeros can be selected, state that allocation.

The minimum number of covering lines equals the maximum number of independent zeros. In small tables, first try to select independent zeros; when a conflict blocks completion, inspect the rows and columns responsible. To justify that a cover is minimum, exhibit as many independent zeros as there are covering lines: each needs a different line.

Different minimum covers can be valid. If several are available, compare their smallest uncovered entries; a larger adjustment can make the work more efficient. Never cover with extra lines just to reach nn.

Not in the formula booklet: learn it.

Worked example 3: one improvement is needed

Question. Apply the Hungarian algorithm to costs

PQRA738B684C529\begin{array}{c|rrr} &\mathrm P&\mathrm Q&\mathrm R\\\hline \mathrm A&7&3&8\\ \mathrm B&6&8&4\\ \mathrm C&5&2&9 \end{array}

Plan. Reduce rows and columns, show a minimum zero cover, improve the matrix and select independent zeros.

Subtract row minima 3,4,23,4,2, then column minima 2,0,02,0,0:

(405240307)⟶(205040107)\begin{pmatrix}4&0&5\\2&4&0\\3&0&7\end{pmatrix} \quad\longrightarrow\quad \begin{pmatrix}2&0&5\\0&4&0\\1&0&7\end{pmatrix}

Cover row B and column Q. These two lines cover every zero and are minimum, since AQAQ and BRBR are independent zeros. Only two independent zeros are possible: A and C both need Q.

The uncovered entries are 2,5,1,72,5,1,7, so e=1e=1. Subtract 11 there, add 11 at the doubly covered BQBQ, and leave singly covered entries unchanged:

(104050006)\begin{pmatrix}1&0&4\\0&5&0\\0&0&6\end{pmatrix}

Now choose AQ,BR,CPAQ,BR,CP.

Why add at BQ? The improvement can be viewed as subtracting 11 from each uncovered row and adding 11 to each covered column. At BQ only the column addition acts; at a singly covered entry the net change is zero or neither operation acts. Thus assignment comparisons are still preserved.

Answer. A to Q, B to R, C to P, with original minimum cost 3+4+5=123+4+5=12 pounds.

Check. Three independent zeros now require at least three covering lines, and three row lines suffice. The selected original entries total 1212, rather than zero.

[DIAGRAM: asset_name: A minimum cover and one Hungarian improvement; asset_slug: 9fm0-d2-183-cover-and-improve; caption: Cover row B and column Q, adjust by1, then choose AQ, BR and CP.; description: The reduced three-by-three matrix2,0,5;0,4,0;1,0,7 with two covering lines and smallest uncovered1, beside the improved matrix1,0,4;0,5,0;0,0,6 with the three independent allocation zeros marked.]
Cover row B and column Q, adjust by1, then choose AQ, BR and CP.

Worked example 4 changes only the original CP cost, from 55 to 66. It creates two optimal choices after the improvement.

Worked example 4: tied independent allocations

Question. Repeat the Hungarian procedure for

(738684629)\begin{pmatrix}7&3&8\\6&8&4\\6&2&9\end{pmatrix}

Plan. Reduce rows first and use the same minimum cover, then inspect all independent zero choices.

The row minima remain 3,4,23,4,2, and column minima remain 2,0,02,0,0:

(405240407)⟶(205040207)\begin{pmatrix}4&0&5\\2&4&0\\4&0&7\end{pmatrix} \quad\longrightarrow\quad \begin{pmatrix}2&0&5\\0&4&0\\2&0&7\end{pmatrix}

Cover row B and column Q. The smallest uncovered entry is now e=2e=2. The improved table is

(003060005)\begin{pmatrix}0&0&3\\0&6&0\\0&0&5\end{pmatrix}

Both AQ,BR,CPAQ,BR,CP and AP,BR,CQAP,BR,CQ are complete independent zero allocations.

Why keep the choices separate? Choosing AP from one alternative and CP from the other would use column P twice. Each complete allocation must be checked as a whole.

Answer. Two optimal allocations are A to Q, B to R, C to P, costing 3+4+6=133+4+6=13; or A to P, B to R, C to Q, costing 7+4+2=137+4+2=13.

Check. Each choice uses every row and column once. Both have the same original total, as the zero-allocation argument predicts.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account