Mastering the Hungarian Algorithm for Optimal Assignment Problems

Mastering the Hungarian Algorithm for Optimal Assignment Problems

The Hungarian Algorithm, also known as the Kuhn-Munkres algorithm, is a powerful combinatorial optimization algorithm that solves the assignment problem in polynomial time. The assignment problem, in its most basic form, involves finding a minimum-cost (or maximum-profit) assignment of n workers to n jobs, given a cost matrix that describes the cost of assigning each worker to each job. This problem arises in a wide variety of applications, including resource allocation, scheduling, transportation, and data association.

This article provides a detailed explanation of the Hungarian Algorithm, breaking down its steps and illustrating them with examples.

1. Understanding the Assignment Problem

Before diving into the algorithm, let’s solidify our understanding of the problem:

• Input: An n x n cost matrix C, where C_ij represents the cost of assigning worker i to job j. The matrix doesn’t have to be square, but the algorithm is easiest to understand in that context. Non-square matrices can be padded with infinity (or a sufficiently large number) cost entries to make them square, effectively preventing those assignments.
• Goal: Find a one-to-one assignment of workers to jobs (each worker gets exactly one job, and each job gets exactly one worker) such that the total cost of the assignment is minimized.
• Constraints: Each worker is assigned to exactly one job, and each job is assigned to exactly one worker.

2. The Steps of the Hungarian Algorithm

The Hungarian Algorithm can be summarized in the following steps. We’ll use a running example to illustrate each step.

Example Cost Matrix:

| Worker/Job | Job 1 | Job 2 | Job 3 |
|—|—|—|—|
| Worker 1 | 2 | 9 | 7 |
| Worker 2 | 6 | 8 | 5 |
| Worker 3 | 4 | 3 | 1 |

Step 1: Row Reduction

For each row, find the minimum element and subtract it from all elements in that row. This ensures at least one zero in each row.

• Row 1: Min = 2. Subtract 2: [0, 7, 5]
• Row 2: Min = 5. Subtract 5: [1, 3, 0]
• Row 3: Min = 1. Subtract 1: [3, 2, 0]

Resulting Matrix:

| Worker/Job | Job 1 | Job 2 | Job 3 |
|—|—|—|—|
| Worker 1 | 0 | 7 | 5 |
| Worker 2 | 1 | 3 | 0 |
| Worker 3 | 3 | 2 | 0 |

Step 2: Column Reduction

For each column, find the minimum element and subtract it from all elements in that column. This ensures at least one zero in each column.

• Column 1: Min = 0. Subtract 0: [0, 1, 3]
• Column 2: Min = 2. Subtract 2: [5, 1, 0]
• Column 3: Min = 0. Subtract 0: [5, 0, 0]

Resulting Matrix:

| Worker/Job | Job 1 | Job 2 | Job 3 |
|—|—|—|—|
| Worker 1 | 0 | 5 | 5 |
| Worker 2 | 1 | 1 | 0 |
| Worker 3 | 3 | 0 | 0 |

Step 3: Covering Zeros with Minimum Lines

The core of the algorithm lies in this step. We aim to cover all zeros in the matrix with the minimum number of horizontal and vertical lines. This can be done systematically:

1. Mark Rows: If a row has exactly one uncovered zero, mark that row.
2. Mark Columns: If a marked row has a zero in a column, mark that column.
3. Repeat: Repeat steps 1 and 2 until no more rows or columns can be marked.
4. Draw Lines: Draw lines through all unmarked rows and all marked columns.

In our example:

1. Row 1 has one uncovered zero (Job 1). Mark Row 1.
2. Row 1’s zero is in Column 1. Mark Column 1.
3. Row 3 has an uncovered zero (Job 2). Mark Row 3.
4. Row 3’s zero is in Column 2. Mark Column 2.
5. Row 2 and 3 both have one uncovered zero at job 3. Row 2 is not marked, so we will not mark Row 2 and column 3 at this time.

Now, draw lines through unmarked rows (Row 2) and marked columns (Column 1, Column 2):

| Worker/Job | Job 1 | Job 2 | Job 3 |
|—|—|—|—|
| Worker 1 | 0 | 5 | 5 | (Covered by Column 1)
| Worker 2 | 1 | 1 | 0 | (Covered by Row 2)
| Worker 3 | 3 | 0 | 0 | (Covered by Column 2)

We used 3 lines, which is the size of our matrix.

Step 4: Optimality Check

If the minimum number of lines required to cover all zeros is equal to n (the number of rows/columns), then an optimal assignment can be found among the zeros. Go to Step 6. Otherwise, proceed to Step 5.

In our example, we used 3 lines, and n = 3. We have an optimal solution. We can skip Step 5 and proceed to Step 6.

Step 5: Shifting Zeros (If Necessary)

If the number of lines is less than n, we need to create more zeros to find a better assignment.

1. Find the smallest uncovered element.
2. Subtract this element from all uncovered elements.
3. Add this element to all elements covered by two lines (i.e., at the intersections of the lines). Elements covered by only one line remain unchanged.
4. Go back to Step 3.

(We will illustrate this step with a different, more complex, example later)

Step 6: Finding the Optimal Assignment

Once the optimality check (Step 4) passes, we can find the optimal assignment. We need to select n zeros such that no two zeros are in the same row or column. There may be multiple optimal solutions.

A systematic approach is:

1. Find a row or column with only one zero. Assign the corresponding worker to that job.
2. Remove that row and column from consideration.
3. Repeat until all workers are assigned.

In our example:

1. Row 1 has only one zero (Job 1). Assign Worker 1 to Job 1.
2. Remove Row 1 and Column 1.
3. Row 3 has only one remaining zero (Job 2). Assign Worker 3 to Job 2.
4. Remove Row 3 and Column 2.
5. Row 2 has only one remaining zero (Job 3). Assign Worker 2 to Job 3.

Optimal Assignment:

• Worker 1 -> Job 1 (Cost = 2)
• Worker 2 -> Job 3 (Cost = 5)
• Worker 3 -> Job 2 (Cost = 3)

Total Cost: 2 + 5 + 3 = 10

3. A More Complex Example (Illustrating Step 5)

Let’s consider a 4×4 example where Step 5 is necessary:

| Worker/Job | Job 1 | Job 2 | Job 3 | Job 4|
|—|—|—|—|—|
| Worker 1 | 4 | 1 | 3 | 2|
| Worker 2 | 2 | 3 | 5 | 1|
| Worker 3 | 3 | 2 | 4 | 1|
| Worker 4 | 1 | 4 | 2 | 3|

After Row and Column Reduction (Steps 1 & 2), we might get:

| Worker/Job | Job 1 | Job 2 | Job 3 | Job 4|
|—|—|—|—|—|
| Worker 1 | 3 | 0 | 2 | 1|
| Worker 2 | 1 | 2 | 4 | 0|
| Worker 3 | 2 | 1 | 3 | 0|
| Worker 4 | 0 | 3 | 1 | 2|

Covering Zeros (Step 3): We can cover all zeros with only 3 lines (e.g., rows 2, 3, and column 1).

Optimality Check (Step 4): 3 lines < 4 (n), so we need Step 5.

Shifting Zeros (Step 5):

1. Smallest uncovered element: 1.
2. Subtract 1 from uncovered: [2, , 1, ], [, 1, 3, ], [1, 0, 2, ], [, 2, 0, ] (Empty spaces indicate covered elements).
3. Add 1 to double-covered (intersections): No double covered elements in this configuration.

New Matrix:

| Worker/Job | Job 1 | Job 2 | Job 3 | Job 4|
|—|—|—|—|—|
| Worker 1 | 3 | 0 | 2 | 1|
| Worker 2 | 1 | 2 | 4 | 0|
| Worker 3 | 2 | 1 | 3 | 0|
| Worker 4 | 0 | 3 | 1 | 2|

We should have had Column 4 marked, and Row 1. Leaving our covered rows and columns as Row 1, Column 1 and Column 4.

| Worker/Job | Job 1 | Job 2 | Job 3 | Job 4|
|—|—|—|—|—|
| Worker 1 | 3 | 0 | 2 | 1|
| Worker 2 | 1 | 1 | 3 | 0|
| Worker 3 | 2 | 0 | 2 | 0|
| Worker 4 | 0 | 2 | 0 | 2|

The new matrix after step 5:

| Worker/Job | Job 1 | Job 2 | Job 3 | Job 4|
|—|—|—|—|—|
| Worker 1 | 2 | 0 | 1 | 1|
| Worker 2 | 0 | 1 | 2 | 0|
| Worker 3 | 1 | 0 | 1 | 0|
| Worker 4 | 0 | 3 | 0 | 3|
Now, we can cover all zeros with 4 lines, allowing us to find the optimal assignment.

4. Key Considerations and Extensions

• Maximization Problems: To solve a maximization problem (e.g., maximizing profit), simply negate all the elements in the cost matrix and then apply the Hungarian Algorithm as if it were a minimization problem.
• Non-Square Matrices: If the number of workers and jobs is unequal, add dummy workers or jobs with sufficiently large (for minimization) or small (for maximization) costs to make the matrix square.
• Forbidden Assignments: If certain assignments are not allowed, assign them a very high cost (for minimization) or a very low cost (for maximization).
• Computational Complexity: The Hungarian Algorithm has a time complexity of O(n³), making it efficient for moderately sized problems.

5. Conclusion

The Hungarian Algorithm is an elegant and efficient method for solving the assignment problem. By understanding the steps involved and practicing with examples, you can master this powerful tool for optimal resource allocation and various other optimization challenges. The systematic approach of row/column reduction, zero covering, and zero shifting ensures that the algorithm converges to an optimal solution. It’s a fundamental algorithm in combinatorial optimization and a valuable addition to any problem-solver’s toolkit.