CalcTypes
Guide / Article

Hungarian Algorithm Python (SciPy)

Last updated: β€’ Sources β€’ Methodology

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

  1. Manual lecture: Hungarian algorithm explained.
  2. Practice & verify: assignment examples.
  3. Unbalanced: dummy rows/columns.
  4. 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.

Sources
  1. SciPy β€” linear_sum_assignment documentation
  2. Kuhn (1955) β€” The Hungarian method for the assignment problem
  3. Munkres (1957) β€” Algorithms for the Assignment and Transportation Problems (SIAM)
  4. Wikipedia β€” Hungarian algorithm (overview)

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.