Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 38 ยท Network Flows

The Assignment Problem

Learn the assignment problem: the 0-1 model, why its LP is integral, the Hungarian algorithm steps, maximization and unbalanced cases, solved with SciPy linear_sum_assignment.

You have n workers and n jobs. Worker i doing job j costs c_ij (or earns profit p_ij). Each worker gets exactly one job and each job exactly one worker. Which pairing is cheapest? This is the assignment problem, the simplest and most famous matching problem. Examples include taxis to passengers, tasks to machines, students to projects and employees to shifts.

The model

Use binary variables x_ij = 1 if worker i does job j:

TEXT
minimize    sum c_ij x_ij
subject to  sum_j x_ij = 1   for each worker i
            sum_i x_ij = 1   for each job j
            x_ij in {0, 1}

This is a transportation problem with every supply and demand equal to 1. Even though x is declared binary, you can relax it to 0 <= x <= 1: the constraint matrix is totally unimodular, so the LP has an integer optimum automatically (Network Flow Models). A feasible assignment is a permutation, and there are n! of them, so brute force explodes quickly (20 workers give about 2.4 quintillion), but the problem is solvable in O(n^3) time.

Python Three ways to solve a 5x5 assignment

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three methods report the same minimum cost, and the LP solution is a clean 0/1 matrix with no branching required.

The Hungarian algorithm idea

The Hungarian method (Kuhn and Munkres) rests on a simple observation: subtracting a constant from a row or a column of the cost matrix does not change which assignment is optimal, because every assignment uses exactly one cell of each row and column. So the algorithm creates zeros and tries to find a complete assignment using only zero cells:

  1. Row reduction: subtract each row's minimum from that row.
  2. Column reduction: subtract each column's minimum from that column.
  3. Cover all zeros with the fewest lines. If n lines are needed, a zero-only complete assignment exists: done.
  4. Otherwise find the smallest uncovered value d, subtract it from every uncovered cell and add it to every cell covered twice. Go to step 3.

The reduced costs are the LP dual variables (potentials for rows and columns), and zeros mark arcs with zero reduced cost, so the algorithm is a primal-dual method. Modern implementations (used by linear_sum_assignment) run in O(n^3).

Python The first two Hungarian steps by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If the reduced matrix has a complete assignment of zeros, its reduced cost is 0 and you are done; otherwise step 4 would continue. Whatever the case, the assignment found on the reduced matrix has the same original cost as the optimal one, because the two problems differ only by constants.

Maximization

To maximize profit, either negate the matrix or subtract every entry from the largest one. SciPy has a flag:

Python Maximize total score and handle a non-square matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Unbalanced and constrained variants

  • More workers than jobs: the extra workers stay unassigned. Add dummy jobs with cost 0 to make the matrix square, if you prefer a formal model.
  • Forbidden pairs: give them a very large cost (1e9) or remove variables. Be careful that a large number does not create round-off trouble.
  • A worker may do several jobs: replace the row sum = 1 by <= k; it becomes a transportation problem, still integral.
  • Side constraints (for example at most two workers from one team, or a budget limit) destroy total unimodularity. Then you need a MILP.
  • Bottleneck assignment: minimize the largest cost rather than the sum. Binary search over a threshold and test if a perfect matching exists using only cells at or below it.
  • Quadratic assignment (costs depend on pairs of assignments, as in facility layout) is NP-hard and a different animal.

Assignments as matchings

The assignment problem is a minimum-weight perfect matching in a complete bipartite graph, and, as in Max Flow and Min Cut, a matching is a flow of unit capacities. Kล‘nig's theorem says the minimum number of lines covering all zeros equals the size of a maximum matching on the zero cells, and that is exactly what step 3 of the Hungarian algorithm uses.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can the assignment LP use 0 <= x <= 1 instead of binary variables?

    The row and column sum constraints form a network matrix, so the LP optimum is attained at an integer vertex.
  2. 2. What operation leaves the optimal assignment unchanged?

    Every assignment uses exactly one cell in each row and column, so every assignment cost shifts by the same constant.
  3. 3. How many possible assignments exist for n workers and n jobs?

    Each assignment is a permutation, so there are n! of them, which is why brute force fails for large n.
  4. 4. How do you solve a maximization assignment problem with a minimizing algorithm?

    Maximizing profit is minimizing negative profit, and the optimal assignment is the same.

Summary

  • The assignment problem pairs each worker with exactly one job at minimum total cost; it is a transportation problem with all supplies and demands equal to 1.
  • The LP relaxation is integral, so a simple LP, network simplex or the Hungarian algorithm (O(n^3)) solves it exactly.
  • Row and column reductions preserve optimal assignments and expose zero-cost pairings.
  • Maximization negates the matrix; unbalanced matrices use dummy rows or columns.
  • Extra side constraints break the integrality and call for integer programming.

Next: Scheduling Basics and Dispatch Rules