Assignment and Matching Problems
Assignment models connect two sets under exclusivity constraints: each selected worker gets at most one task, and each required task gets exactly one worker. The score matrix is part of the model, not an objective truth.
Prerequisites
Complete integer and binary optimization.
Learning goals
- Formulate one-to-one assignment with binary decision variables.
- Distinguish a complete square assignment from optional or forbidden matches.
- Validate row/column exclusivity and total cost independently.
- Treat solver output as model evidence, not proof that costs are fair or complete.
Formulation before solver choice
Let indicate whether worker receives task . For three workers and three required tasks,
\sum_t x_{wt}=1\ \forall w,\qquad \sum_w x_{wt}=1\ \forall t.$$ Here $c_{wt}$ is minutes of expected setup time. A forbidden pair should be removed from the feasible graph or modeled explicitly, not hidden behind an arbitrary huge cost. Rectangular cases also need a declared rule for unmatched workers or tasks. SciPy's `linear_sum_assignment` implements this special structure directly. The same formulation can be expressed as min-cost flow or a general MILP; choosing a different solver does not change the one-to-one contract. ## Worked example ```python import itertools import numpy as np from scipy.optimize import linear_sum_assignment cost = np.array([[9, 2, 7], [6, 4, 3], [5, 8, 1]]) workers, tasks = linear_sum_assignment(cost) pairs = list(zip(workers.tolist(), tasks.tolist())) total = int(cost[workers, tasks].sum()) enumerated = min( (sum(int(cost[w, t]) for w, t in enumerate(order)), order) for order in itertools.permutations(range(3)) ) print(f"assignment={pairs} setup_minutes={total}") print(f"rows_unique={len(set(workers)) == 3} columns_unique={len(set(tasks)) == 3}") print(f"enumerated_optimum_minutes={enumerated[0]} complete_match=True") ``` Expected output: ```text assignment=[(0, 1), (1, 0), (2, 2)] setup_minutes=9 rows_unique=True columns_unique=True enumerated_optimum_minutes=9 complete_match=True ``` The API returns a complete assignment rather than a status object. For this six-permutation instance, complete independent enumeration supplies the termination and optimality evidence: no feasible assignment costs less than 9 minutes. ## Limitations and common mistakes - A low predicted setup time can encode historical inequity, measurement error, or missing qualifications. - One-to-one constraints are wrong when tasks need teams, workers can take multiple tasks, or matching is optional. - Padding a rectangular matrix with dummy rows or columns changes the model unless dummy penalties have explicit meaning. - A very large cost is not the same as a forbidden edge and can create overflow or scaling problems. - Exact solution of this tiny matrix makes no universal latency or scale claim. ## Practice Forbid worker 1 from task 0 by enumerating only allowed permutations. Recompute the optimum, then state whether an unmatched task is prohibited or allowed at a declared penalty. ## Next steps Generalize matching into balances and capacities in [network-flow problems](./network-flow-problems). ## Primary sources Checked 2026-10-19: SciPy `1.18.1`, [`linear_sum_assignment`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html); Google OR-Tools `9.15`, [assignment overview](https://developers.google.com/optimization/assignment) and [assignment as min-cost flow](https://developers.google.com/optimization/flow/assignment_min_cost_flow).