Assignment problem

The assignment problem seeks a minimum-cost matching between agents and tasks, with each agent and task used at most once.

Cost matrix: A rectangular array whose entries give the cost of pairing each agent with each task. It encodes every allowed pairing and its cost for the assignment problem.
Combinatorial optimization: Optimization over a finite set of discrete choices subject to constraints. The assignment problem is a canonical discrete optimization problem.
Job-shop scheduling: A scheduling problem in which jobs require sequences of operations on shared machines. Assignment decisions can allocate jobs to machines before sequencing operations.
Maximum-weight matching: A matching in a weighted graph whose total edge weight is as large as possible. It maximizes selected weights, whereas assignment minimizes pairing costs.
Bipartite graph: A graph whose vertices divide into two sets, with edges only between the sets. Agents and tasks form the two vertex sets; edges represent feasible assignments.
Feasible solution: A choice of variables or decisions that satisfies all constraints of an optimization problem. A feasible assignment never uses an agent or task more than once.
Stable marriage problem: A matching problem with ranked preferences, seeking a matching with no blocking pair. Unlike minimum-cost assignment, it prioritizes preference stability rather than total cost.
Maximum flow problem: The problem of sending as much flow as possible from a source to a sink in a network. Assignment fixes pairing structure and minimizes cost; maximum flow instead maximizes throughput.
Bipartite matching: A set of edges in a bipartite graph that share no endpoints. An assignment is a matching, with costs added to distinguish among possible matchings.
Objective function: A function whose value an optimization problem seeks to minimize or maximize. Summing the selected pairing costs gives the objective to minimize.

Linked from 16 pages