Data Pattern Pro

Mathematical programming / Routing and scheduling

Assignment Problem

Match a set of agents to a set of tasks one-to-one at minimum total cost — the simplest combinatorial optimization pattern, and a building block for much bigger ones.

Note Beginner

Short note. A compact reference, correct as far as it goes. It will be expanded into a full guide with a worked example and an interactive demonstration.

Problem

You have n agents and n tasks, a cost for every possible agent-task pairing, and you need a one-to-one matching that minimizes total cost (or maximizes total value).

When to use it

Assigning workers to shifts, orders to warehouses, or students to project teams when it’s a clean one-to-one (or one-to-many with capacity) match. It’s also the inner loop of more complex problems — e.g. matching vehicles to routes inside a larger VRP heuristic.

Formulation

Binary x_ij = 1 if agent i is assigned to task j:

minimize   sum(c_ij * x_ij)
subject to:
  sum_j(x_ij) = 1   for all i     # each agent gets exactly one task
  sum_i(x_ij) = 1   for all j     # each task gets exactly one agent
  x_ij in {0, 1}

The elegant part: this MILP’s LP relaxation is already integral — the constraint matrix is totally unimodular, so you don’t even need a MILP solver. A dedicated algorithm (Hungarian algorithm) solves it in polynomial time.

Code sketch

import numpy as np
from scipy.optimize import linear_sum_assignment

cost = np.array([
    [4, 1, 3],
    [2, 0, 5],
    [3, 2, 2],
])
row_idx, col_idx = linear_sum_assignment(cost)
# row_idx[k] is assigned to col_idx[k]

Pitfalls

  • Don’t reach for a general MILP solver here — scipy.optimize.linear_sum_assignment or any Hungarian-algorithm implementation is faster and simpler for the pure one-to-one case.
  • The moment you need capacities greater than 1 per task (many-to-one) or partial assignments, you’re really solving a transportation problem instead — structurally similar but a different named pattern with different standard tooling.