Assignment Problem

307. Assignment Problem

The special case of the transportation problem where $𝑛$ agents are assigned to $𝑛$ tasks one-to-one.

307.1. Formulation

Cost $𝑐_{𝑖 𝑗}$ to assign agent $𝑖$ to task $𝑗$ . Decision variable $𝑥_{𝑖 𝑗} \in {0, 1}$ .

min \sum_{𝑖 = 1}^{𝑛} \sum_{𝑗 = 1}^{𝑛} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗}

s.t.:

\sum_{𝑗} 𝑥_{𝑖 𝑗} = 1, 𝑖 = 1, \dots, 𝑛 (each agent gets one task)

\sum_{𝑖} 𝑥_{𝑖 𝑗} = 1, 𝑗 = 1, \dots, 𝑛 (each task gets one agent)

𝑥_{𝑖 𝑗} \in {0, 1}

307.2. Unbalanced (dummy)

When agents and tasks differ in number ( $𝑛$ agents, $𝑚$ tasks, $𝑛 > 𝑚$ ), not everyone can be assigned. Relax the agent constraint to $\leq$ :

\begin{aligned} min & \sum_{𝑖 𝑗} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗} \\ s.t. & \sum_{𝑗} 𝑥_{𝑖 𝑗} \leq 1 \forall 𝑖 (agent does at most one task) \\ \sum_{𝑖} 𝑥_{𝑖 𝑗} = 1 \forall 𝑗 (every task is covered) \\ 𝑥_{𝑖 𝑗} \geq 0 \end{aligned}

Equivalently, restore balance with a dummy task (column $𝑚 + 1$ , zero cost) that absorbs the $𝑛 - 𝑚$ unassigned agents:

\begin{aligned} min & \sum_{𝑖 = 1}^{𝑛} \sum_{𝑗 = 1}^{𝑚 + 1} 𝑐_{𝑖 𝑗} 𝑥_{𝑖 𝑗} \\ s.t. & \sum_{𝑗 = 1}^{𝑚 + 1} 𝑥_{𝑖 𝑗} = 1 \forall 𝑖 \in {1, \dots, 𝑛} \\ \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖 𝑗} = 1 \forall 𝑗 \in {1, \dots, 𝑚} \\ \sum_{𝑖 = 1}^{𝑛} 𝑥_{𝑖, 𝑚 + 1} = 𝑛 - 𝑚 \\ 𝑥_{𝑖 𝑗} \geq 0 \end{aligned}

307.3. LP relaxation gives integer solution

Constraint matrix is totally unimodular → LP relaxation has integer optimum. Can drop the binary constraint and solve as an LP; equivalently use the Hungarian algorithm in $𝑂 (𝑛^{3})$ .

307.4. Applications

Job-machine assignment — minimize total processing time
Crew scheduling — assign pilots to flights
Bipartite matching — pair customers to drivers
Image processing / computer vision — find correspondences between point sets
Subproblem in branch-and-bound for VRP, TSP

307.5. Generalizations

Generalized assignment — costs and capacities, NP-hard
Quadratic assignment problem — cost depends on pairs of assignments, NP-hard
Bottleneck assignment — minimize max assignment cost (minimax variant)

307.6. See also

Hungarian Algorithm — the standard solver
Transportation Problem — the generalization
Unimodularity — why LP relaxation works