Assignment problem
The assignment problem is a fundamental combinatorial optimization problem in operations research and mathematics, which involves finding an optimal one-to-one assignment of n tasks to n agents (such as workers to jobs or resources to activities) to minimize the total cost, given a cost matrix that specifies the cost of assigning each task to each agent.[1] It is a special case of the more general linear programming problem and the transportation problem, where the supply and demand at each source and destination are exactly equal to one unit, ensuring a perfect matching without leftovers.[2] The problem can be modeled as finding a minimum-weight perfect matching in a complete bipartite graph, where one set of vertices represents tasks and the other represents agents, with edge weights corresponding to assignment costs.[1] It was first systematically addressed through the Hungarian algorithm, developed and published in 1955 by Harold W. Kuhn, who named it after the Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, whose earlier works from the 1920s and 1930s on graph theory and matrix properties laid the foundational duality principles for the method.[3] Although the problem has roots in 19th-century mathematics, Kuhn's formulation integrated it with linear programming developments from the 1940s, making it solvable in polynomial time via combinatorial techniques rather than general-purpose solvers.[2][4] The assignment problem has wide-ranging applications across industries, including job scheduling in manufacturing to allocate machines to tasks efficiently, resource allocation in education for assigning projects to students, transportation planning for matching vehicles to routes, and even engineering design for optimizing airfoil parameters in aerodynamics. In agriculture, it aids in assigning land plots to crops or resources to maximize yield while minimizing costs, and in modern contexts like computer networks, it supports tasks such as allocating processors to jobs or optimizing supply chain logistics.[2] These applications highlight its role in decision-making under constraints, often extended to generalized forms that allow unequal numbers of tasks and agents or additional capacities.[1]Definition and Formulation
Informal Description
The assignment problem is a fundamental challenge in optimization that arises when there is a need to pair a set of resources, such as workers or machines, with an equal number of tasks or jobs in a way that achieves the best possible overall outcome. Imagine a scenario where a manager must assign n employees to n projects, ensuring each employee handles exactly one project and each project receives exactly one employee, while aiming to minimize the total time, cost, or effort involved—or equivalently, to maximize efficiency or profit based on individual compatibilities and capabilities. This one-to-one matching ensures fairness and completeness in the allocation, making it a practical tool for decision-making in various real-world settings like scheduling, logistics, and resource distribution.[5][3] At its core, the assignment problem can be viewed as a weighted version of pairing elements from two distinct groups, where the "weight" of each possible pairing reflects a measurable benefit or drawback, such as the cost of assigning a particular worker to a specific task. This distinguishes it from simpler matching problems by incorporating quantitative trade-offs, allowing for optimized solutions that balance individual assignments to favor the collective good. The problem assumes a square setup with equal numbers on both sides, though extensions exist for imbalances, but the classic form emphasizes perfect, balanced pairings.[6] The origins of the assignment problem trace back to the early 20th century, particularly the 1920s and 1930s, when Hungarian mathematicians Dénes Kőnig and Jenő Egerváry laid foundational theorems on matchings in graphs and matrices that directly addressed weighted pairings. Kőnig's 1931 work established key equalities in bipartite structures, while Egerváry's contemporaneous 1931 paper extended these ideas to real-valued weights, providing early insights into optimal assignments. These contributions, though initially theoretical, gained widespread application in operations research following World War II, as computational tools and linear programming advanced, enabling practical solutions for military and industrial planning in the 1950s.[7][8]Formal Mathematical Model
The assignment problem can be formally defined using two finite sets of equal cardinality n: a set of agents I = \{1, 2, \dots, n\} and a set of tasks J = \{1, 2, \dots, n\}. A cost matrix C = (c_{ij}) is given, where c_{ij} \in \mathbb{R} denotes the cost incurred by assigning agent i \in I to task j \in J. The objective is to determine a bijection \pi: I \to J—equivalently, a permutation of the tasks—that minimizes the total assignment cost \sum_{i=1}^n c_{i, \pi(i)}.[3] This minimization formulation assumes non-negative costs, though the model generalizes to arbitrary real-valued costs. The bijection ensures that each agent is assigned to exactly one unique task, and each task is assigned to exactly one unique agent, reflecting the one-to-one matching requirement. In matrix terms, the optimal assignment corresponds to a permutation matrix P = (p_{ij}), where p_{ij} = 1 if agent i is assigned to task j (i.e., \pi(i) = j), and p_{ij} = 0 otherwise, such that P has exactly one 1 in each row and column.[3] An equivalent maximization formulation arises in contexts like profit or score assignment, where one seeks to maximize \sum_{i=1}^n r_{i, \pi(i)} for a reward matrix R = (r_{ij}) with r_{ij} \geq 0. This is obtained by negating the costs, i.e., setting r_{ij} = -c_{ij}, transforming the minimization problem into one of maximizing total reward under the same bijection constraints.[3] The assignment problem admits a natural linear programming (LP) formulation using binary decision variables x_{ij} \in \{0, 1\} for i \in I, j \in J, where x_{ij} = 1 if agent i is assigned to task j, and x_{ij} = 0 otherwise. The optimization problem is then: \begin{align*} \min &\quad \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} \\ \text{s.t.} &\quad \sum_{j=1}^n x_{ij} = 1 \quad \forall i \in I, \\ &\quad \sum_{i=1}^n x_{ij} = 1 \quad \forall j \in J, \\ &\quad x_{ij} \in \{0, 1\} \quad \forall i \in I, j \in J. \end{align*} The row and column sum constraints enforce the exact one-to-one assignment, and the integrality of solutions follows from the totally unimodular constraint matrix, allowing relaxation to x_{ij} \geq 0 without loss of optimality. The assignment problem is a special case of the balanced transportation problem, where there are n sources (agents) each with supply 1 and n sinks (tasks) each with demand 1, and the unit transportation costs are given by the matrix C. This connection embeds the assignment problem within the broader class of minimum-cost flow problems on bipartite networks.Examples
Bipartite Graph Example
The assignment problem can be represented as a weighted bipartite graph G = (V, E), where the vertex set V is partitioned into two disjoint sets X and Y of equal size n, corresponding to n agents and n tasks, respectively, and edges e \in E connect agents to tasks with weights representing assignment costs c_{ij} for agent i \in X and task j \in Y.[9] The objective is to minimize the total cost of assignments by selecting a set of edges that pairs each agent to exactly one task.[9] Consider a small example with three agents A_1, A_2, A_3 in set X and three tasks T_1, T_2, T_3 in set Y. The edges and their costs are as follows: A_1 to T_1 (cost 9), A_1 to T_2 (cost 2), A_1 to T_3 (cost 7); A_2 to T_1 (cost 6), A_2 to T_2 (cost 4), A_2 to T_3 (cost 3); A_3 to T_1 (cost 5), A_3 to T_2 (cost 8), A_3 to T_3 (cost 1). Possible perfect matchings include \{A_1-T_2, A_2-T_1, A_3-T_3\} with total cost 2 + 6 + 1 = 9, and \{A_1-T_2, A_2-T_3, A_3-T_1\} with total cost 2 + 3 + 5 = 10; the former achieves the minimum total cost among perfect matchings.[10] A perfect matching in this bipartite graph is a set of edges with no shared vertices that covers all $2n vertices, ensuring each agent is assigned to exactly one unique task.[9] Such matchings exist if the graph allows a complete pairing without conflicts, which is guaranteed in the complete bipartite graph typical for the assignment problem. König's theorem states that in any bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover, providing a foundational result that underpins the feasibility of perfect matchings in balanced assignment instances.[9] To visualize the optimal matching, imagine the graph drawn with agents on the left partite set and tasks on the right, connected by weighted edges; the optimal solution selects non-adjacent edges (one per vertex) that collectively minimize the sum of edge weights, such as highlighting the edges A_1-T_2, A_2-T_1, and A_3-T_3 in bold to show the minimum-cost perfect matching of total weight 9.[10]Numerical Cost Matrix Example
To illustrate the assignment problem with a numerical cost matrix, consider the scenario of assigning four workers (A, B, C, D) to four jobs (1, 2, 3, 4), where the costs represent the time or expense incurred. The cost matrix is as follows:[11]| Worker \ Job | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| A | 4 | 1 | 0 | 1 |
| B | 1 | 3 | 4 | 0 |
| C | 3 | 2 | 1 | 3 |
| D | 2 | 2 | 3 | 0 |
| Assignment (A, B, C, D) | Total Cost |
|---|---|
| (1, 2, 3, 4) | 8 |
| (1, 2, 4, 3) | 13 |
| (1, 3, 2, 4) | 10 |
| (1, 3, 4, 2) | 13 |
| (1, 4, 2, 3) | 9 |
| (1, 4, 3, 2) | 7 |
| (2, 1, 3, 4) | 3 |
| (2, 1, 4, 3) | 8 |
| (2, 3, 1, 4) | 8 |
| (2, 3, 4, 1) | 10 |
| (2, 4, 1, 3) | 7 |
| (2, 4, 3, 1) | 4 |
| (3, 1, 2, 4) | 3 |
| (3, 1, 4, 2) | 6 |
| (3, 2, 1, 4) | 6 |
| (3, 2, 4, 1) | 8 |
| (3, 4, 1, 2) | 5 |
| (3, 4, 2, 1) | 4 |
| (4, 1, 2, 3) | 7 |
| (4, 1, 3, 2) | 5 |
| (4, 2, 1, 3) | 10 |
| (4, 2, 3, 1) | 7 |
| (4, 3, 1, 2) | 10 |
| (4, 3, 2, 1) | 9 |
Solution Algorithms
Hungarian Algorithm
The Hungarian algorithm, also known as the Kuhn-Munkres algorithm, is a combinatorial optimization method specifically designed to solve the balanced assignment problem of assigning n agents to n tasks with minimum total cost. It was developed by Harold W. Kuhn in 1955 and named the "Hungarian method" to honor the foundational contributions of Hungarian mathematicians Dénes Kőnig and Jenő Egerváry, whose 1930s work on bipartite graphs and the marriage theorem provided key theoretical insights into minimum vertex covers and perfect matchings.[14] The algorithm iteratively reduces the cost matrix to identify an optimal assignment by creating and manipulating zeros, effectively finding a perfect matching in the bipartite graph representation. The algorithm operates on an n × n cost matrix C = (c_{ij}), where c_{ij} represents the cost of assigning agent i to task j, assuming the problem is balanced. The steps are as follows:- Row reduction: For each row i, subtract the minimum value in that row from every entry in the row. This ensures each row has at least one zero.
- Column reduction: For each column j, subtract the minimum value in that column from every entry in the column. This ensures each column also has at least one zero.
- Zero covering: Draw the minimum number of horizontal and vertical lines to cover all zeros in the reduced matrix. If the number of lines equals n, proceed to find the assignment by selecting n independent zeros (one per row and column). Otherwise, continue.
- Matrix adjustment: Identify the smallest uncovered entry δ in the matrix. Subtract δ from all uncovered entries and add δ to all entries covered by the intersection of two lines (i.e., doubly covered). Leave singly covered entries unchanged. This creates additional zeros while preserving the optimal assignment property. Return to step 3 and repeat until n lines cover all zeros.
| M1 | M2 | M3 | |
|---|---|---|---|
| W1 | 25 | 44 | 36 |
| W2 | 28 | 41 | 40 |
| W3 | 23 | 50 | 35 |
| M1 | M2 | M3 | |
|---|---|---|---|
| W1 | 0 | 19 | 11 |
| W2 | 0 | 13 | 12 |
| W3 | 0 | 27 | 12 |
| M1 | M2 | M3 | |
|---|---|---|---|
| W1 | 0 | 6 | 0 |
| W2 | 0 | 0 | 1 |
| W3 | 0 | 14 | 1 |
Linear Programming Formulation
The assignment problem can be formulated as an integer linear program to minimize the total assignment cost \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij}, where c_{ij} denotes the cost of assigning agent i to task j and x_{ij} \in \{0,1\} is a binary decision variable indicating the assignment, subject to the constraints that each agent is assigned to exactly one task \sum_{j=1}^n x_{ij} = 1 for all i = 1, \dots, n, and each task is assigned to exactly one agent \sum_{i=1}^n x_{ij} = 1 for all j = 1, \dots, n.[3] This integer program can be relaxed to a standard linear program by replacing the integrality constraints x_{ij} \in \{0,1\} with non-negativity x_{ij} \geq 0, yielding the transportation polytope defined by the row and column sum equality constraints. Optimal solutions to this linear programming relaxation remain integral (i.e., binary and corresponding to permutation matrices), due to the total unimodularity of the constraint matrix.[3] A proof sketch relies on the Birkhoff-von Neumann theorem, which establishes that the extreme points of the polytope of doubly stochastic matrices (equivalent to the normalized transportation polytope for unit supplies and demands) are precisely the permutation matrices.[18] Thus, any vertex solution to the linear program is integral. The resulting linear program can be solved using general-purpose methods such as the simplex algorithm or interior-point methods, which exhibit practical time complexity of O(n^3) for n \times n instances due to the structured sparsity and bounded number of basic feasible solutions explored.[3] From the perspective of linear programming duality, the assignment problem's dual is to maximize \sum_{i=1}^n u_i + \sum_{j=1}^n v_j subject to u_i + v_j \leq c_{ij} for all i,j (with u_i, v_j \leq 0 for the minimization primal), where u_i and v_j represent agent and task potentials, respectively; strong duality ensures that optimal primal assignments satisfy complementary slackness with these potentials. The Hungarian algorithm operates as a primal-dual method for this linear program, iteratively updating dual variables to maintain feasibility while augmenting the primal matching until optimality is achieved.[3]Auction Algorithm
The auction algorithm, developed by Dimitri P. Bertsekas in 1979, provides an intuitive approach to solving the assignment problem by modeling it as an economic auction process for resource allocation, where "persons" (agents) bid for "objects" (tasks) to maximize total profit.[19] This method draws inspiration from market equilibrium concepts, treating the assignment as a competitive bidding scenario that converges to an optimal matching.[19] In the profit maximization formulation of the assignment problem, where the goal is to maximize the sum of profits a_{ij} for assigned pairs (i,j), the algorithm uses dual prices to guide bids toward an optimal solution. The core mechanism simulates an auction where unassigned agents iteratively bid on tasks based on their perceived value net of current task prices, with prices updated to reflect the highest bids, ensuring that bidding continues until every agent is assigned to a task yielding at least as much profit as any alternative given the prices.[19] To achieve polynomial-time convergence, the algorithm employs \epsilon-scaling, starting with a relatively large \epsilon (a bid increment threshold) and halving it in successive phases until \epsilon is sufficiently small (e.g., less than 1 for integer profits), which bounds the number of bidding rounds and prevents infinite loops. This scaling technique ensures the algorithm finds an exact optimal assignment by maintaining \epsilon-complementary slackness conditions, where each agent's assignment is within \epsilon of the maximum possible profit relative to prices.[19] The algorithm proceeds in phases as follows: initialize task prices to zero and start with no assignments; for each unassigned agent, compute the bid for the most profitable unassigned task as the maximum profit minus the task's current price plus \epsilon, then assign the agent to the task receiving the highest bid and update that task's price to the bid value; repeat bidding and updates for all unassigned agents until none remain, advancing to the next \epsilon-scaling phase if necessary. Bids are calculated to favor the task offering the highest net profit, and price increases by at least \epsilon ensure progress toward equilibrium.[19] In terms of computational complexity, the \epsilon-scaling auction algorithm runs in O(n^3 \log(nC)) time, where n is the problem size and C is the maximum absolute profit value, making it polynomial and suitable for problems with costs up to moderate scales. This complexity arises from O(\log(nC)) scaling phases, each involving O(n^2) bid computations and O(n) assignment updates in the worst case.[19] Key advantages include its inherent parallelizability, as independent agents can bid simultaneously across processors, yielding 4- to 10-fold speedups on large instances compared to sequential methods, and its robustness to perturbations in profit values, maintaining efficiency even with noisy or dynamic data.[20] These properties make it particularly effective for sparse or large-scale assignment problems in distributed computing environments.[19]Other Methods
The Jonker-Volgenant algorithm is a shortest augmenting path method for solving the linear assignment problem, serving as an optimized variant of the Hungarian algorithm with improved practical performance through efficient handling of dense and sparse cost matrices.[21] It achieves O(n^3) worst-case time complexity but features smaller constants than the standard Hungarian implementation, making it particularly effective for medium to large instances where initialization overhead is minimized.[21] This algorithm is widely implemented in software such as the LAPJV library, which provides a fast C-based solver for the linear assignment problem.[22] Another exact method models the assignment problem as a minimum-cost flow in a bipartite flow network, solved via the successive shortest path algorithm, which iteratively augments the matching along reduced-cost shortest paths while using node potentials to maintain efficiency and avoid negative cycles.[23] By applying Dijkstra's algorithm with potentials in each of n iterations, it runs in O(n^2 log n + n m log n) time for sparse graphs, where m is the number of edges, though for dense complete bipartite graphs it aligns with O(n^3) behavior.[23] This approach leverages min-cost flow duality for optimality guarantees.[24] Although the assignment problem admits exact polynomial-time solutions, approximation algorithms are occasionally employed for very large instances where exact methods become computationally prohibitive, a scenario that arises rarely for n below 1000 due to the efficiency of exact solvers.[25] A simple greedy algorithm, which iteratively selects the highest-weight available edge to build the matching, provides a 1/2-approximation for the maximum-weight bipartite matching problem in dense graphs.[26] Implementations of these methods are available in open-source libraries; for instance, SciPy'slinear_sum_assignment function employs a modified Jonker-Volgenant algorithm for efficient solving of dense instances.[25] Similarly, Google's OR-Tools supports assignment problem solving through its mixed-integer programming and constraint programming solvers, which can incorporate specialized heuristics akin to successive shortest path for scalability.[27]
As of 2025, while no reductions in asymptotic complexity have occurred for the standard assignment problem, recent advancements include new auction algorithm variants with cooperative bidding mechanisms, which enhance practical performance by resolving bidding conflicts more efficiently.[28] Additionally, GPU accelerations have enabled efficient solving of large instances (n > 10,000) by parallelizing Hungarian variants, achieving speedups of up to 6× over prior GPU implementations in dense cases.[29]
Variants
Unbalanced Assignment
In the unbalanced assignment problem, the number of agents m and tasks n differ such that m \neq n; without loss of generality, assume m \leq n.[30] The standard approach balances the problem by introducing n - m dummy agents, each assigned zero cost to every task, creating an n \times n square cost matrix. A balanced assignment algorithm, such as the Hungarian algorithm, is then applied to this augmented matrix, with the resulting optimal solution discarding any assignments involving the dummy agents to yield the best one-to-one matching of the original m agents to m of the n tasks.[30][31] For maximization formulations, the dummy agents receive zero profit for all tasks, which ensures the solution maximizes profit over a partial assignment without artificially inflating the objective value.[32]Example
Consider a minimization problem assigning 3 machines to 4 jobs with the following cost matrix (in arbitrary units):| Machine | Job 1 | Job 2 | Job 3 | Job 4 |
|---|---|---|---|---|
| M1 | 5 | 7 | 4 | 6 |
| M2 | 3 | 8 | 9 | 5 |
| M3 | 6 | 4 | 7 | 8 |
| Machine | Job 1 | Job 2 | Job 3 | Job 4 |
|---|---|---|---|---|
| M1 | 5 | 7 | 4 | 6 |
| M2 | 3 | 8 | 9 | 5 |
| M3 | 6 | 4 | 7 | 8 |
| M4 | 0 | 0 | 0 | 0 |
Many-to-Many Assignment
The many-to-many assignment problem relaxes the one-to-one restrictions of the classical assignment problem by permitting each agent to handle multiple tasks and each task to be assigned to multiple agents, up to predefined capacity limits on both sides. This variant arises in scenarios requiring flexible resource allocation, such as team-based operations where individuals or resources have bounded workloads.[34]Mathematical Formulation
Consider a set of m agents and n tasks, where each agent i has a capacity b_i representing the maximum number of task units it can process, and each task j has a capacity a_j indicating the maximum number of agent units that can be allocated to it. A cost c_{ij} is associated with assigning one unit of agent i to one unit of task j. The decision variables x_{ij} denote the integer number of units assigned from agent i to task j. The objective is to minimize the total assignment cost: \min \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij} subject to the capacity constraints: \sum_{j=1}^n x_{ij} \leq b_i \quad \forall i = 1, \dots, m \sum_{i=1}^m x_{ij} \leq a_j \quad \forall j = 1, \dots, n x_{ij} \geq 0, \quad x_{ij} \in \mathbb{Z} \quad \forall i, j. If the total capacity \sum_i b_i = \sum_j a_j, the inequalities can be replaced by equalities for a balanced problem; otherwise, dummy agents or tasks can be introduced to achieve balance without altering the optimal solution.[35] This formulation is equivalent to the transportation problem in operations research, where agents act as sources with supplies b_i and tasks as destinations with demands a_j, with shipments corresponding to assignments at unit cost c_{ij}. The transportation problem generalizes the assignment problem by allowing arbitrary integer supplies and demands, rather than the unit values of the classical case.[35]Solution Approaches
The many-to-many assignment problem can be solved as a minimum-cost flow problem on a bipartite flow network: introduce a source connected to agents with capacities b_i and costs 0, agents connected to tasks with capacities \infty (or large enough) and costs c_{ij}, and tasks connected to a sink with capacities a_j and costs 0; the minimum-cost flow of value \min(\sum b_i, \sum a_j) yields the optimal assignment. Alternatively, it can be formulated as an integer linear program using the constraints above and solved via standard solvers, with the linear programming relaxation often providing tight bounds due to total unimodularity.[34]Example
Consider two agents, each with capacity b_1 = b_2 = 2, and three tasks, each with capacity a_1 = a_2 = a_3 = 1. The total supply is 4 and total demand is 3, making it unbalanced but solvable by satisfying all demands up to available supply. The unit costs are given in the following matrix:| Task 1 | Task 2 | Task 3 | |
|---|---|---|---|
| Agent 1 | 3 | 1 | 4 |
| Agent 2 | 2 | 3 | 1 |
Generalized Assignment Problem
The generalized assignment problem (GAP) extends the classical assignment problem by incorporating resource constraints on the agents. In this formulation, there are m agents, each with a capacity b_i for i = 1, \dots, m, and n tasks, each with a size s_j for j = 1, \dots, n and a cost c_{ij} associated with assigning task j to agent i. The objective is to assign each task to exactly one agent such that the total size of tasks assigned to agent i does not exceed b_i, while minimizing the total assignment cost \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}, where x_{ij} = 1 if task j is assigned to agent i and 0 otherwise.[36] The GAP is NP-hard in the strong sense, as demonstrated by a reduction from the partition problem: given a set of positive integers, the partition problem can be transformed into a GAP instance with m=2 agents each having equal capacity equal to half the total sum, and tasks corresponding to the integers with unit costs, where feasibility equates to a perfect partition.[37] Exact methods for solving the GAP include branch-and-bound algorithms, which enumerate possible assignments while pruning branches based on lower bounds derived from relaxations, as introduced in the original formulation of the problem.[36] Integer programming formulations are also standard, where the problem is modeled as a mixed-integer linear program and solved using solvers like branch-and-cut or branch-and-price techniques for larger instances.[38] For small-scale instances with limited capacities, dynamic programming can be employed by building solutions agent-by-agent, using states that track the remaining capacity and assigned tasks, though the approach is pseudo-polynomial in the capacity values.[39] Approximation algorithms provide efficient near-optimal solutions for larger instances. A notable result is a polynomial-time 2-approximation algorithm obtained via linear programming relaxation and rounding, which guarantees a solution cost at most twice the optimal.[40] Local search heuristics, such as tabu search with ejection chains, are widely used in practice and often yield solutions within 0.5% of optimality on benchmark instances with up to 100 agents and tasks.[37] As a simple illustrative example, consider m=2 agents with capacities b_1 = 5 and b_2 = 3, and n=3 tasks with sizes s_1 = 2, s_2 = 3, s_3 = 1, and the following cost matrix (costs for assigning task j to agent i):| Agent \ Task | Task 1 | Task 2 | Task 3 |
|---|---|---|---|
| Agent 1 | 3 | 4 | 1 |
| Agent 2 | 1 | 2 | 5 |