Hungarian Algorithm in Python (SciPy)
SciPy’s scipy.optimize.linear_sum_assignment solves the linear assignment problem
(Hungarian/Kuhn–Munkres family). You provide a cost matrix and receive an optimal one-to-one assignment (row→column).
For the manual lecture steps (row/column reductions, cover/adjust loop), see Hungarian algorithm explained. For worked sets, see assignment examples.
On this page
Quick takeaway: Create a cost matrix, call linear_sum_assignment, map indices back to labels,
and compute cost[row_ind, col_ind].sum(). For explicit idle/unfilled interpretations, pad with dummy rows/columns first.
Worked examples (solved in code)
Worked example
Example 1: Minimization assignment with labels + expected total
import numpy as np
from scipy.optimize import linear_sum_assignment
workers = ["W1", "W2", "W3"]
jobs = ["J1", "J2", "J3"]
cost = np.array([
[9, 2, 7],
[6, 4, 3],
[5, 8, 1]
])
r, c = linear_sum_assignment(cost)
pairs = [(workers[i], jobs[j], int(cost[i, j])) for i, j in zip(r, c)]
total = int(cost[r, c].sum())
print("Pairs:", pairs)
print("Total:", total)
Expected result
The optimal total cost for this matrix is 9 (see the manual steps in assignment examples). If your pair list differs but total is 9, you likely have a different optimal assignment (multiple optima can occur).
Worked example
Example 2: Maximization (maximize=True vs conversion)
Approach A: direct maximization (if supported):
# r, c = linear_sum_assignment(profit, maximize=True)
Approach B: convert profit to cost:
import numpy as np
from scipy.optimize import linear_sum_assignment
profit = np.array([
[10, 5, 9],
[ 8, 7, 4],
[ 6, 9, 8]
])
Pmax = profit.max()
cost = Pmax - profit
r, c = linear_sum_assignment(cost)
best_profit = int(profit[r, c].sum())
print("Best profit:", best_profit)
Expected result
The maximum total profit here is 26 (manual derivation on assignment examples).
Unbalanced assignment (dummy padding)
SciPy accepts rectangular matrices, but if you want the OR meaning of “unfilled job” or “idle worker,” pad to square with dummy rows/columns. Full concept: unbalanced assignment.
Pad-to-square recipe + interpretation
import numpy as np
from scipy.optimize import linear_sum_assignment
def pad_to_square(cost, pad_value=0):
cost = np.asarray(cost, dtype=float)
n, m = cost.shape
k = max(n, m)
out = np.full((k, k), pad_value, dtype=float)
out[:n, :m] = cost
return out
# 3 workers, 4 jobs -> add 1 dummy worker row
cost_rect = np.array([
[8, 6, 7, 9],
[6, 7, 5, 8],
[7, 8, 6, 7]
])
cost_sq = pad_to_square(cost_rect, pad_value=0) # 0 means "unfilled job has no penalty"
r, c = linear_sum_assignment(cost_sq)
Interpretation: if the chosen assignment uses a padded dummy row, that job is “unfilled.” If unfilled jobs are costly, use a positive pad_value as a penalty.
Forbidden pairs (penalty vs ILP)
If some assignments are impossible (forbidden), a penalty can discourage them—but penalties change meaning. When forbidden constraints are hard rules (not preferences), ILP/MILP constraints are often more appropriate.
Penalty method example (with scaling caution)
import numpy as np
from scipy.optimize import linear_sum_assignment
BIG = 10**6
cost = np.array([
[9, 2, 7],
[6, 4, 3],
[5, 8, 1]
], dtype=float)
# forbid W2->J3
cost[1, 2] = BIG
r, c = linear_sum_assignment(cost)
If the model has many rules (skills, fairness, coverage), switch to ILP/MILP: how to model ILP and ILP/MILP.
Questions people ask
Questions people ask
Why does SciPy return a different pairing than my Hungarian-table solution?
The assignment problem can have multiple optimal solutions. In those cases, the “correct answer” is not a unique pairing, but any feasible pairing achieving the optimal total objective value.
Hungarian steps often involve tie-breaking (which zero to select first, which augmenting structure to use). Different tie-breaking can yield a different optimal pairing with the same total. The right comparison is: (1) feasibility (one per row/column), and (2) optimal total.
Questions people ask
How do I validate an answer programmatically?
Validation has two levels:
- Feasibility: no row repeats and no column repeats in the selected pairs.
- Objective: compute the sum in the original cost matrix. (Don’t validate using reduced matrices from manual steps.)
If your matrix is rectangular but your business meaning requires “idle/unfilled,” pad with dummies before solving.
Questions people ask
When should I use MILP instead of linear_sum_assignment?
Use MILP when you add constraints linking multiple decisions: coverage constraints, fairness as hard limits, multi-shift patterns, time windows, precedence, or prohibited combinations. Those constraints move the problem beyond pure matching.
A good starting point is: how to model ILP and ILP vs MILP.
What to do next
- Manual lecture: Hungarian algorithm explained.
- Practice & verify: assignment examples.
- Unbalanced: dummy rows/columns.
- Beyond assignment: ILP/MILP.
Disclaimer
Educational content only. Real assignment/scheduling often needs constraints beyond one-to-one matching. Penalty methods can distort meaning if chosen poorly. Validate assumptions, scaling, and results for your use case. Read the full disclaimer.