Skip to content

Assignment Problem

Optimally assign workers to tasks minimizing total cost. The Hungarian algorithm solves this in O(n³), making it practical for thousands of workers.

The Problem

n workers, n tasks, a cost for each pairing. Assign each worker to exactly one task and vice versa. Minimize total cost. Unlike general matching, this is one of the few combinatorial problems with a fast exact algorithm.

Example

from solvor import solve_hungarian

# Cost matrix: cost[worker][task]
costs = [
    [9, 2, 7, 8],   # Worker 0
    [6, 4, 3, 7],   # Worker 1
    [5, 8, 1, 8],   # Worker 2
    [7, 6, 9, 4]    # Worker 3
]

result = solve_hungarian(costs)

print(f"Assignment: {result.solution}")
print(f"Total cost: {result.objective}")

# Decode assignment
for worker, task in enumerate(result.solution):
    cost = costs[worker][task]
    print(f"Worker {worker} -> Task {task} (cost {cost})")

Maximization

For maximization (e.g., profit instead of cost):

result = solve_hungarian(profits, minimize=False)

See Also