Is the assignment problem always difficult to solve exactly?

The classic linear sum assignment problem has efficient exact algorithms. Added constraints or interaction terms can change the problem substantially.

Can the objective be maximized?

Yes. Some implementations support maximization directly, or benefits can be transformed consistently into minimization costs.

Must every worker be assigned in a rectangular problem?

Not necessarily. Coverage depends on the formulation and which side has fewer items; state the intended rules explicitly.

AI Glossary / Mathematics and optimization / Intermediate

Assignment problems

Definition

Assignment problems allocate items from one set to items in another while optimizing an objective and satisfying matching constraints. In the classic linear sum assignment problem, each selected pair has a fixed cost, and the goal is a one-to-one assignment with minimum total cost. Examples include assigning workers to tasks or matching detections between observations.

What it means

The difficulty is that attractive individual choices can conflict. Two tasks may both be cheapest for the same worker, but that worker may be allowed to take only one task. The model evaluates the combined assignment rather than choosing the cheapest pair independently for each task.

The classic square problem assigns every item on each side exactly once. Rectangular versions match all items on the smaller side while some items on the larger side remain unmatched. More general variants add capacities, interactions, or other constraints and may require different algorithms and complexity assumptions.

How it works

Create a cost matrix C, with rows representing one set and columns representing the other. Let binary variable Xij equal one when row i is assigned to column j. Minimize the sum of CijXij over all allowed pairs.

For a square complete assignment, require each row sum and each column sum to equal one. These constraints prevent omissions and duplicate use. Specialized polynomial-time methods exploit this structure rather than enumerating every permutation.

For rectangular or incomplete matching, define which side must be covered and how unavailable pairs or unmatched items are handled. If choosing one pair changes another pair's cost, the simple additive model may no longer be appropriate. Validate the selected pairs against the original operational constraints after solving.

Three practical examples

1. Task allocation: assign available machines to jobs when each machine takes one job and processing costs are known for every permitted pair.

2. Computer vision: match current detections with previous tracks using a defined association cost and explicit handling of unmatched objects.

3. Scheduling preparation: match sessions to distinct rooms for one time period, provided eligibility and capacity are represented in the allowed pairings.

Think of it this way

Think of seating guests in distinct numbered seats. Each guest has a preference cost for each seat, but no seat can be given to two guests. The best arrangement considers everyone's placement together.

The analogy assumes preferences are independent of who sits nearby. If neighboring guests change each other's experience, pairwise seat costs alone are insufficient, and the problem becomes a different, richer assignment model.

Worked example

Three workers A, B, and C must each receive one of three tasks. Their costs for tasks 1, 2, and 3 are A:(2,4,7), B:(3,6,4), and C:(5,2,3).

Choosing each row's minimum independently suggests A1, B1, and C2, costing 7. This is infeasible because task 1 is used twice and task 3 is unassigned.

There are six feasible permutations. Listed by the task numbers assigned to A, B, and C, their totals are (1,2,3):11; (1,3,2):8; (2,1,3):10; (2,3,1):13; (3,1,2):12; and (3,2,1):18.

The optimum is A1, B3, C2, with total cost 2+4+2=8. B takes its second-cheapest task so that the full assignment is feasible and collectively best.

If task 3 becomes unavailable to B, that solution is excluded, and the best remaining listed assignment costs 10. The original optimum does not remain valid after the feasible set changes. This exhaustive check is practical only because the example is tiny; specialized algorithms handle larger classic assignment problems without listing every permutation.

Illustrative case study

Fictional case: a workshop allocates three machines to three jobs. Its previous procedure assigns each job to its individually fastest machine and then resolves conflicts manually.

An analyst builds a one-to-one assignment model using processing-time estimates and machine eligibility. The resulting plan avoids duplicate allocations and gives an auditable total. Before accepting it, the supervisor checks whether setup changes or shared tooling introduce interactions omitted from the matrix.

Where those interactions matter, the team revises the model instead of treating the simple assignment result as a complete production schedule. This fictional example claims no measured efficiency gain or actual workshop deployment.

Common misconceptions and mistakes

The cheapest pair for every row may not form a feasible matching. One-to-one constraints create competition for columns.

Do not assume a square cost matrix is always required. Rectangular assignment is possible, but its coverage convention must match the task.

An extremely large artificial cost is not automatically equivalent to a forbidden pair if the solver must select a complete assignment. The model must still represent feasibility correctly.

Linear assignment is different from generalized assignment, where agents may receive multiple tasks subject to capacities, and quadratic assignment, where interactions between assignments contribute to the objective.

Business use

Assignment models help organizations make allocation decisions consistent, explainable, and reproducible when pair costs and constraints are well defined. They also appear as internal components in tracking, matching, and data-processing systems.

Confirm that the cost matrix reflects the actual decision objective and that all mandatory eligibility rules are represented. Record how unmatched items and ties are handled. If costs are predictions, test sensitivity to their uncertainty; a mathematically optimal assignment can still perform poorly when the underlying estimates are wrong.

Check your understanding

Why is the apparent cost-7 choice in the worked example invalid?

Answer: It assigns both A and B to task 1 and leaves task 3 uncovered. A low objective value is irrelevant if the assignment constraints are violated.

Related terms

Hungarian algorithm
Linear sum assignment
bipartite matching
cost matrix
integer programming
generalized assignment
quadratic assignment
data association
feasibility

Learn next

Enumerate all assignments for a three-by-three matrix and compare the optimum with independent row minima. Then add one extra worker and specify which items must be matched. Study bipartite matching next to understand the graph structure behind the cost-matrix formulation.

Sources

Official tutorial assignment section read: SciPy optimization tutorial: https://docs.scipy.org/doc/scipy/tutorial/optimize.html#assignment-problems . The article adopts the classic additive one-to-one setting and distinguishes richer variants. All worker costs and permutation totals are original hand-checked examples; no solver execution or runtime claim is made.

Previous: Assignment Next: Associative classifier