Assignment Problem

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

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

An assignment problem is balanced iff the number of agents equals the number of tasks.

Unbalanced

When the problem is not balanced. Dummy agents or tasks are added to rebalance.

• Minimisation problem
  Use 0 as the dummy assignment cost.
• Maximisation problem
  First convert the profit matrix to a minimisation cost matrix. Then use 0 as the dummy assignment cost.

Maximization

A maximization assignment problem is one where the objective is to maximize total cost.

The problem is converted to minimization by subtracting every cost from the largest cost in the matrix, then solve as usual.

Restricted

An assignment problem is restricted iff there are prohibited agent-task pairs.

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

Big $M$ is used for prohibited assignments. It is not required for an ordinary dummy assignment after a maximisation problem has been converted to a minimisation problem.

Hungarian Method

Solves a balanced assignment problem in polynomial time, avoiding the degeneracy the transportation methods would hit.

Steps

• Row reduction
  Subtract the minimum entry of each row from every entry in that row.
• Column reduction
  Subtract the minimum entry of each column from every entry in that column.
• Cover all 0s in the resulting matrix using the minimum number of horizontal and vertical lines.
• If the number of lines equals $n$, an optimal assignment exists among the 0s. Stop.
• Otherwise, find the smallest uncovered entry. Subtract it from every uncovered entry, and add it to every entry covered twice (at a line intersection). Repeat the covering step.

Reading the Assignment

Once $n$ lines are needed, select $n$ independent 0s (1 per row and column) by assigning rows/columns with a unique 0 first, then resolving remaining choices, until every agent is assigned a task.

Worked Examples

Simple Example

3 agents and 3 tasks, with cost matrix:

Adjusting the Matrix

Here the 0s need only 2 lines after reduction, so no assignment exists yet. The matrix is adjusted and covered again.