Assignment Problem

A special case of the transportation problem: assign $n$ agents to $n$ tasks one-to-one, minimizing total cost, given a cost $c_{ij}$ for assigning agent $i$ to task $j$.

Subject to $\sum_j x_{ij} = 1$ for every agent, $\sum_i x_{ij} = 1$ for every task, and $x_{ij} \in \{0, 1\}$.

Every supply and demand equals 1, so every basic feasible solution is inherently degenerate ($n$ occupied cells needed for a non-degenerate BFS, but only $n$ assignments exist against $2n - 1$ required).

Balanced and Unbalanced

Balanced when the number of agents equals the number of tasks. If unequal, add dummy agents or tasks with 0 cost to rebalance.

Maximization Assignment Problem

Convert to minimization by subtracting every cost from the largest cost in the matrix, then solve as usual.

Restricted Assignment Problem

A prohibited agent-task pair is assigned a very large cost $M$, driving it out of the optimal assignment.