Assignment problem

Assignment problem — modeling one-to-one allocation of agents to tasks to minimize cost or maximize profit, solved efficiently by the Hungarian method with practical variants (unbalanced, maximization, prohibitions).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Assigning people to jobs, machines to parts, or vehicles to routes is a daily industrial decision. The assignment problem gives a fast, guaranteed-optimal way to make one-to-one allocations that minimize total cost or maximize total profit/time saved.

Key ideas

  • Definition and model

    • An assignment problem allocates each of n agents (machines/operators) to exactly one of n tasks (jobs), with a known cost matrix cᵢⱼ (or profit matrix pᵢⱼ). The goal is to minimize total cost (or maximize total profit) subject to one-to-one matching.
    • The standard LP (binary integer program) for the minimization case is:
      • Decision variables: xᵢⱼ = 1 if agent i is assigned to task j; 0 otherwise.
      • Objective: minimize Σᵢ Σⱼ cᵢⱼ xᵢⱼ.
      • Constraints: Σⱼ xᵢⱼ = 1 for all i (each agent assigned once); Σᵢ xᵢⱼ = 1 for all j (each task done once); xᵢⱼ ∈ {0,1}.
    • Assumptions (basic model):
      • Deterministic, known costs/times; linear additivity of total cost.
      • One agent per task and one task per agent; no splitting.
      • No precedence or interaction effects among assignments.
      • A single time period; no capacitated or multi-skill complications.
  • Structure and optimality

    • The constraints matrix is totally unimodular, so the LP relaxation (xᵢⱼ ≥ 0) yields integral optimal solutions; integer programming is not needed for this basic case.
    • The feasible solutions correspond to permutation matrices; this is linked to the Birkhoff–von Neumann theorem (every doubly stochastic matrix is a convex combination of permutation matrices).
  • The Hungarian method (Kuhn–Munkres algorithm)

    • A polynomial-time algorithm for solving the balanced n×n assignment problem in O(n³) time.
    • Works on a nonnegative cost matrix and preserves optimality through row/column reductions and adjustments that maintain dual feasibility.
    • Algorithm outline for minimization:
      1. Row reduction: subtract the minimum in each row from all elements of that row (creates at least one zero per row).
      2. Column reduction: subtract the minimum in each column from all elements of that column (creates at least one zero per column).
      3. Cover all zeros using the minimum number of horizontal/vertical lines. If the minimum number of covering lines equals n, an optimal assignment exists among the zeros (select a set of n independent zeros — no two in the same row/column). If fewer than n lines are needed, proceed.
      4. Adjustment: find the smallest uncovered element k; subtract k from all uncovered elements; add k to all elements at intersections of covering lines; leave the rest unchanged. Go back to step 3.
    • Duality view (why it works):
      • Row and column reductions construct feasible dual variables uᵢ, vⱼ with reduced costs rᵢⱼ = cᵢⱼ − uᵢ − vⱼ ≥ 0; zeros satisfy complementary slackness. When you can choose n independent zeros, primal and dual are both optimal. The sum of chosen uᵢ and vⱼ gives a valid lower bound on the optimal cost; the total amount subtracted in row/column reductions equals this bound.
  • Variants seen in exams and practice

    • Maximization (profit): convert to minimization by cᵢⱼ = Pmax − pᵢⱼ, where Pmax = max pᵢⱼ over all i, j, to keep costs nonnegative.
    • Unbalanced case (rectangular m×n): add dummy rows or dummy columns with zero cost/profit so that the matrix is square; then solve. A dummy assignment means an agent is idle or a task is left undone (with zero cost/benefit under the modeling assumption).
    • Prohibited assignments: mark forbidden cells by a very large cost M (conceptual ∞) or explicitly forbid selection during the final zero-choice; avoid choosing them.
    • Multiple optimal solutions: occurs when more than one set of n independent zeros exists; any such assignment has the same optimal objective value.
    • Bottleneck assignment: objective is to minimize the maximum assigned cost, min maxᵢⱼ cᵢⱼ xᵢⱼ. Can be solved via thresholding/binary search on a cost level with a feasibility (perfect matching) check on the subgraph of allowed edges.
  • Practical notes

    • Costs should be comparable and on the same scale (e.g., time or money) and nonnegative for the Hungarian method as presented. If some costs are negative, you can add a constant K ≥ −minᵢⱼ cᵢⱼ to all entries to make them nonnegative; this does not change the optimal assignment.
    • Big-M for prohibitions should be chosen “safely large” relative to all real costs to avoid accidental selection; in manual solutions we treat such cells as blocked.
    • Real systems may have learning effects, setup interactions, eligibility constraints, multitasking, or stochastic processing times; these require extensions (e.g., generalized assignment, scheduling, or queuing models).

Formulas

Minimize Z = Σᵢ Σⱼ cᵢⱼ xᵢⱼ

  • Z: total cost (units depend on cᵢⱼ; e.g., rupees, s)
  • cᵢⱼ: cost of assigning agent i to task j (Rs or s)
  • xᵢⱼ ∈ {0,1}; model applies to balanced assignment with one-to-one matching.

Subject to Σⱼ xᵢⱼ = 1 for all i

  • Each agent i is assigned exactly one task.

Subject to Σᵢ xᵢⱼ = 1 for all j

  • Each task j is assigned to exactly one agent.

Maximization conversion: cᵢⱼ = Pmax − pᵢⱼ

  • pᵢⱼ: profit (Rs or other benefit units)
  • Pmax: maximum pᵢⱼ over all i, j (same unit as pᵢⱼ)
  • Use when converting a profit maximization assignment to a cost minimization with nonnegative costs.

Unbalanced case balancing: add dummy rows/columns with cᵢⱼ = 0 (or pᵢⱼ = 0)

  • Applies when number of agents ≠ number of tasks; units of cᵢⱼ unchanged.

Bottleneck objective: minimize B subject to cᵢⱼ xᵢⱼ ≤ B for all i, j; Σⱼ xᵢⱼ = 1; Σᵢ xᵢⱼ = 1; xᵢⱼ ∈ {0,1}

  • B: maximum assigned cost (Rs or s)
  • Applies to bottleneck assignment problems.

Worked examples

Example 1 — Direct minimization by Hungarian method (balanced 4×4) Given: Cost matrix cᵢⱼ (Rs)

  • A1: [9, 2, 7, 8]
  • A2: [6, 4, 3, 7]
  • A3: [5, 8, 1, 8]
  • A4: [7, 6, 9, 4] Objective: Minimize total cost.

Steps:

  1. Row reduction: subtract row minima.
  • Row minima: r₁=2, r₂=3, r₃=1, r₄=4.
  • Reduced matrix R₁:
    • A1: [7, 0, 5, 6]
    • A2: [3, 1, 0, 4]
    • A3: [4, 7, 0, 7]
    • A4: [3, 2, 5, 0]
  1. Column reduction: subtract column minima.
  • Column minima after step 1: c₁=3, c₂=0, c₃=0, c₄=0.
  • Reduced matrix R₂:
    • A1: [4, 0, 5, 6]
    • A2: [0, 1, 0, 4]
    • A3: [1, 7, 0, 7]
    • A4: [0, 2, 5, 0]
  1. Cover zeros with minimum lines and find independent zeros.
  • We can select zeros: (A1,T2), (A2, T1), (A3, T3), (A4, T4) — all in distinct rows/columns.
  • Since 4 independent zeros are found, optimal assignment exists.
  1. Read off optimal assignment and compute total cost (original matrix):
  • A1→T2: 2 Rs; A2→T1: 6 Rs; A3→T3: 1 Rs; A4→T4: 4 Rs.
  • Total cost = 2 + 6 + 1 + 4 = 13 Rs.

Answer: Optimal assignment is (1,2), (2,1), (3,3), (4,4) with total cost = 13 Rs.

Example 2 — GATE-style: Maximization with a prohibition (balanced 4×4) Given: Profit matrix pᵢⱼ (Rs); “X” means prohibited assignment.

  • A1: [16, 15, X, 13]
  • A2: [14, 17, 12, 10]
  • A3: [15, 14, 16, 11]
  • A4: [12, 13, 11, 9] Objective: Maximize total profit. Method: convert to minimization and apply Hungarian, treating the prohibited cell as blocked.
  1. Convert to costs using cᵢⱼ = Pmax − pᵢⱼ, with Pmax = max pᵢⱼ = 17.
  • A1: [1, 2, INF, 4]
  • A2: [3, 0, 5, 7]
  • A3: [2, 3, 1, 6]
  • A4: [5, 4, 6, 8] Note: INF denotes a prohibitively large cost for (A1, T3). We will not select this cell.
  1. Row reduction (subtract each row minimum):
  • Row minima: A1=1, A2=0, A3=1, A4=4.
  • After subtraction:
    • A1: [0, 1, INF, 3]
    • A2: [3, 0, 5, 7]
    • A3: [1, 2, 0, 5]
    • A4: [1, 0, 2, 4]
  1. Column reduction (subtract column minima):
  • Column minima: col1=0, col2=0, col3=0, col4=3.
  • After subtraction from column 4:
    • A1: [0, 1, INF, 0]
    • A2: [3, 0, 5, 4]
    • A3: [1, 2, 0, 2]
    • A4: [1, 0, 2, 1]
  1. Cover zeros with minimum number of lines and adjust if needed.
  • Zeros are at: (1,1), (1,4), (2,2), (3,3), (4,2).
  • A minimal cover uses 3 lines: Row 1, Column 2, Column 3. Since 3 < n=4, adjust.
  • Smallest uncovered element k = 1 (e.g., at (3,1) and (4,1)). Subtract k from all uncovered elements; add k to elements at intersections of the covering lines.
  • After adjustment:
    • A1: [0, 2, INF, 0]
    • A2: [2, 0, 5, 3]
    • A3: [0, 2, 0, 1]
    • A4: [0, 0, 2, 0]
  1. Find independent zeros (n=4 needed):
  • Choose (A1, T1) = 0, (A2, T2) = 0, (A3, T3) = 0, (A4, T4) = 0 — all distinct rows and columns; the prohibited (A1, T3) is not selected.
  1. Convert back to profits and compute total profit from the original pᵢⱼ:
  • Assignments: A1→T1 (16 Rs), A2→T2 (17 Rs), A3→T3 (16 Rs), A4→T4 (9 Rs).
  • Total profit = 16 + 17 + 16 + 9 = 58 Rs.

Answer: Optimal assignment is (1,1), (2,2), (3,3), (4,4) with maximum total profit = 58 Rs.

Common mistakes

  • Converting maximization to minimization incorrectly (e.g., using cᵢⱼ = −pᵢⱼ and creating negative costs, which breaks the standard nonnegative-cost Hungarian steps). Use cᵢⱼ = Pmax − pᵢⱼ.
  • Mishandling prohibitions: either forgetting to block a forbidden cell or using too small a “big-M” that can be selected inadvertently; in hand solutions, mark forbidden cells clearly and never select them.
  • Confusing the adjustment step: the uncovered minimum k must be subtracted from all uncovered elements and added only at intersections of the covering lines; other covered cells remain unchanged.
  • Stopping early when the number of covering lines is less than n; you must perform at least one adjustment.
  • Selecting zeros that are not independent (two in the same row or column); check for independence before finalizing the assignment.

For GATE ME

  • Solve a 3×3 or 4×4 cost/profit assignment by the Hungarian method (full steps expected).
  • Handle maximization via conversion and/or a prohibited assignment.
  • Balance an unbalanced assignment with a dummy row/column and solve.
  • Identify multiple optimal solutions or compute the optimal value directly from a reduced matrix.
  • Formulate the LP for an assignment problem and reason about integrality/duality at a conceptual level.
  • Short conceptuals on the bottleneck assignment objective and feasibility check.
  • Practice focus:
    • Speed and accuracy with row/column reductions, minimal line covering, and the adjustment step.
    • Clean handling of variants: maximization, dummy rows/columns, prohibitions.
    • Quick detection of independent zeros and recognition of degeneracy (multiple optima).
    • Translating a word problem to the correct cost/profit matrix with consistent units.

Quick check

  1. How do you convert a profit maximization assignment to a minimization assignment suitable for the Hungarian method?
  2. What do you do if the number of lines needed to cover all zeros is less than n in a reduced n×n matrix?
  3. In an unbalanced 3×5 assignment, what do you add to balance it before applying the Hungarian method?

Answers: 1) Use cᵢⱼ = Pmax − pᵢⱼ with Pmax = max pᵢⱼ, ensuring nonnegative costs. 2) Subtract the smallest uncovered element from all uncovered elements and add it to elements at intersections of the covering lines, then repeat the covering step. 3) Add two dummy rows (agents) with zero costs to create a 5×5 matrix and then solve.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?