Solve the assignment problem in Python

The assignment problem is one of the most common optimization problems you hit in practice: you have N workers and N tasks, each worker–task pair has a cost, and you need a one-to-one assignment — every worker gets exactly one task, every task exactly one worker — that minimizes the total cost. Scheduling shifts, matching orders to machines, distributing jobs across servers: all assignment problems. It's also known as the linear sum assignment problem or worker–task matching.

The naive way is to try every possible assignment. The scalable way is to model it and hand it to a solver. With quicopt that is a few lines of Python.

The brute-force trap

The direct translation of "try every assignment" is a loop over all permutations:

from itertools import permutations

cost = [
    [9, 11, 14, 11, 7],
    [6, 15, 13, 13, 10],
    [12, 13, 6, 8, 8],
    [11, 9, 10, 12, 9],
    [7, 12, 14, 10, 14],
]
N = len(cost)

best = min(permutations(range(N)), key=lambda p: sum(cost[w][p[w]] for w in range(N)))
print("cost:", sum(cost[w][best[w]] for w in range(N)))  # -> 38

This returns the right answer — for five workers. The problem is the number of permutations is N!, and factorials explode:

• 5 workers → 120 orderings (instant)
• 12 workers → 479,001,600 (seconds to minutes)
• 15 workers → 1,307,674,368,000 (hopeless)

Enumeration is a dead end the moment the instance is real.

Model it as a MILP

The assignment problem is a mixed-integer linear program (MILP). Introduce a binary variable x[w][t] that is 1 when worker w is given task t. Two sets of constraints enforce the one-to-one structure — each worker takes exactly one task, each task goes to exactly one worker — and the objective sums the cost of the chosen pairs:

from ortools.math_opt.python import mathopt
from quicopt import Client

# Assignment problem: assign N workers to N tasks, one-to-one, at minimum total
# cost. cost[w][t] = cost of giving task t to worker w.
cost = [
    [9, 11, 14, 11, 7],
    [6, 15, 13, 13, 10],
    [12, 13, 6, 8, 8],
    [11, 9, 10, 12, 9],
    [7, 12, 14, 10, 14],
]
N = len(cost)

model = mathopt.Model(name="assignment")
x = [[model.add_binary_variable(name=f"x_{w}_{t}") for t in range(N)] for w in range(N)]

# Each worker gets exactly one task; each task goes to exactly one worker.
for w in range(N):
    model.add_linear_constraint(sum(x[w][t] for t in range(N)) == 1)
for t in range(N):
    model.add_linear_constraint(sum(x[w][t] for w in range(N)) == 1)

model.minimize(sum(cost[w][t] * x[w][t] for w in range(N) for t in range(N)))

client = Client("https://try.quicoptapi.pgi.fz-juelich.de")
result = client.solve(model)
print(result.display)

├── status:     optimal
├── feasible:   true
├── objective:  38.0
├── x:          x_0_0=0, x_0_1=0, x_0_2=0, x_0_3=0, x_0_4=1, x_1_0=1, …  (25 variables)
└── solve_time: 0.0117 s

What you get

status: optimal means the solver proved this is the best assignment — not a good guess, the optimum. It matches the brute-force answer (cost 38) and corresponds to the assignment worker→task 0→4, 1→0, 2→2, 3→1, 4→3. The solver returned it in about a hundredth of a second.

The difference is scaling. Brute force is O(n!); the assignment problem is solvable in polynomial time (the Hungarian method, Kuhn 1955), and a MILP solver exploits exactly that structure. The same eleven-line model that solves five workers solves five hundred — you change the data, not the approach.

Next

• The problem class behind this: MILP
• Related guides: Scheduling · Vehicle routing · Facility location
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: H. W. Kuhn, The Hungarian Method for the assignment problem, Naval Research Logistics Quarterly, 1955.