304. Assignment Problem

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

304.1. Formulation

Cost to assign agent to task . Decision variable .

s.t.:

304.2. 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 .

304.3. 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

304.4. 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)

304.5. See also

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