Skip to main content

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 xwt∈{0,1}x_{wt}\in\{0,1\} indicate whether worker ww receives task tt. 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).