Skip to content

Assignment Problem

Definition

The assignment problem pairs nn agents with nn tasks so that each agent receives exactly one task and each task exactly one agent. If cijc_{ij} is the cost of assigning agent ii to task jj, a binary model is

min⁡∑i=1n∑j=1ncijxij,∑jxij=1,∑ixij=1,xij∈{0,1}.\min\sum_{i=1}^n\sum_{j=1}^nc_{ij}x_{ij},\qquad \sum_jx_{ij}=1,\qquad \sum_ix_{ij}=1,\qquad x_{ij}\in\{0,1\}.

Interpretation

The assignment problem asks for the cheapest way to pair two equally large groups one-to-one, such as machines with jobs. The choices are coupled: once a task goes to one agent, it is no longer available for the others, so the pairs cannot be chosen one at a time.

A 3 by 3 cost table of agents and tasks with the chosen cells highlighted, next to a bipartite diagram of agents A1 to A3 and tasks T1 to T3 with the chosen assignment drawn in bold.

The table and the diagram show the same instance. Each green cell of the table is a bold edge in the diagram, and each row and each column of the table contains exactly one green cell. Of the 3!=63!=6 complete assignments, three cost 1212: besides the highlighted one, also (1,2),(2,1),(3,3)(1,2),(2,1),(3,3) and (1,2),(2,3),(3,1)(1,2),(2,3),(3,1). An optimal assignment need not be unique.

In the binary integer program, xij=1x_{ij}=1 means that agent ii performs task jj. The equation ∑jxij=1\displaystyle \sum_jx_{ij}=1 gives agent ii exactly one task, and ∑ixij=1\displaystyle \sum_ix_{ij}=1 gives task jj exactly one agent. Together they describe a perfect matching between agents and tasks, and the objective adds the costs of the chosen pairs. The model is a transportation problem in which every supply and every demand equals 11.

Listing all assignments is hopeless beyond small sizes: there are n!n! of them, already 3,628,8003{,}628{,}800 for n=10n=10. The Hungarian algorithm exploits the one-per-row, one-per-column structure instead, and dummy entries and forbidden pairs adapt the model to unequal group sizes and excluded pairs.

Key Results

  • Costs can represent execution times as well as monetary amounts.
  • Unequal numbers of agents and tasks can be handled with dummy entries.
  • Task quotas can be modelled by duplicating agent rows into separate slots.

Examples

The illustrated three-agent instance has 3!=63!=6 complete assignments. The highlighted pairs have total cost 4+7+1=124+7+1=12, which is optimal. For this assignment formulation with integer data, an integral optimal solution exists even after relaxing the binary restrictions.

  • The main example assigns machines 1, 2, 3, 4 to jobs 1, 4, 2, 3, with cost 20.
  • Machines can be assigned to locations or players to field positions.

Prerequisites

Sources

Aliases: linear assignment problem, linear sum assignment problem Symbols: element of, sum

Last updated: 22 October 2026 19:04