Hungarian Algorithm Python (SciPy)
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)
Expected result (checked with SciPy 1.18): minimum total cost 18. SciPy returns W1βJ2 (6), W2βJ3 (5), W3βJ1 (7) and the dummy row on J4, so J4 is the unfilled job. This matrix has ties: W1βJ2, W2βJ1, W3βJ3 (6 + 6 + 6) and W1βJ2, W2βJ3, W3βJ4 (6 + 5 + 7) also total 18 and leave J4 or J1 unfilled. If it matters which job stays open, give the dummy row different penalties.
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)
Expected result: total cost 9 (W1βJ2, W2βJ1, W3βJ3), the same as Example 1, because the best assignment never used W2βJ3. After solving, always check that no chosen pair has cost BIG; if one does, no assignment exists without a forbidden pair.
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?
Check that no row or column repeats in the chosen pairs, then confirm that the total cost from the original matrix equals the solverβs reported optimum.
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.
Methodology: How This Guide Works
This guide explains implementing the Hungarian algorithm in Python using the standard textbook treatment found in operations-research courses (for example Hillier & Lieberman, Introduction to Operations Research, and Taha, Operations Research: An Introduction). Each step is written so you can repeat it by hand, and the worked examples use the same steps as the CalcTypes Hungarian method solver, so you can reproduce them there.
Assumptions and Limitations
Assumptions
- Each worker is assigned to at most one task and each task to at most one worker.
- Code examples use Python 3 and standard libraries such as SciPyβs linear_sum_assignment.
- Input matrices contain numeric costs.
Limitations
- Library behaviour and function names can change between versions.
- Example code is for learning; add input validation before production use.
- Software uses floating-point arithmetic, so tiny rounding differences from hand calculations are normal.
Disclaimer
Please read before relying on this page. This page on Hungarian Algorithm Python (SciPy) explains optimisation methods for study. Worked examples use simplified models; real problems usually need extra constraints and careful validation. Check methods against your course, and validate any model before using it for real decisions.
Your responsibility. Results are estimates for general information and education only, and nothing here is professional advice. You use this page at your own risk; to the fullest extent permitted by law, CalcTypes, its authors and reviewers accept no liability for loss, injury or damage arising from reliance on it. Spotted an error? Use βReport an issueβ or our contact page. Full terms: Disclaimer Β· Terms of use.