Assignment problem

The assignment model, the Hungarian method with row and column reduction, line covering and the improvement step, and maximisation, unbalanced and prohibited cases.

Drafted with Aria, reviewed by the AiCanCode.org team. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Assigning jobs to machines, operators to work-stations, or salesmen to territories one-to-one is an everyday shop-floor decision. With n jobs there are n! possible assignments (24 for 4 jobs, 3.6 million for 10), so trial is hopeless. The Hungarian method finds the best assignment in a few matrix reductions by hand, and is a favourite GATE numerical.

Key ideas

Model. n jobs, n facilities, cost (or time) cᵢⱼ if job i goes to facility j. Each job goes to exactly one facility and each facility gets exactly one job; minimise total cost. It is a transportation problem with every supply and demand equal to 1 — so it is highly degenerate (only n of the 2n − 1 basic cells are positive), which is why MODI is inefficient and the Hungarian method is used instead.

Why reduction works. Subtracting a constant from every element of a row (or column) changes the cost of every complete assignment by the same constant, because each assignment uses exactly one cell per row and per column. So the optimal assignment is unchanged. Reduce until an assignment can be made entirely on zeros; since all entries are ≥ 0, that assignment is optimal.

Hungarian method (minimisation).

  1. Row reduction: subtract the smallest element of each row from that row.
  2. Column reduction: subtract the smallest element of each column from that column.
  3. Assign: look for a row (or column) with exactly one unmarked zero; assign it and cross out the other zeros in its column (row). Repeat. If n assignments are made, stop — optimal.
  4. Cover: otherwise draw the minimum number of horizontal and vertical lines covering all zeros. If the number of lines equals n, an optimal assignment exists among the zeros (break remaining ties arbitrarily).
  5. Improve: if lines < n, find the smallest uncovered element k; subtract k from every uncovered element, add k to every element at the intersection of two lines, leave singly covered elements unchanged. Go to step 3.

Variations.

  • Maximisation (profit, efficiency): convert to a loss matrix by subtracting every element from the largest element (or multiply by −1), then minimise.
  • Unbalanced (rows ≠ columns): add dummy rows or columns of zeros to make it square; a job assigned to a dummy facility is simply not done.
  • Prohibited assignment: put a very large cost M in that cell.
  • Alternative optima: when ties remain after step 3, more than one optimal assignment exists with the same total.

Travelling-salesman link. The TSP is an assignment problem with an extra no-subtour condition; the Hungarian solution gives a lower bound but may contain subtours.

Formulas

  • Objective: Min Z = Σᵢ Σⱼ cᵢⱼ · xᵢⱼ
  • Constraints: Σⱼ xᵢⱼ = 1 for each i; Σᵢ xᵢⱼ = 1 for each j; xᵢⱼ ∈ {0, 1}
  • Number of possible assignments: n!
  • Loss matrix for maximisation: lᵢⱼ = c_max − cᵢⱼ
  • Lower bound from reductions: Z* ≥ Σ (row minima) + Σ (column minima of the row-reduced matrix)

Symbols: cᵢⱼ = cost, time or profit of job i on facility j (₹, h); xᵢⱼ = 1 if job i is given to facility j, else 0; n = size of the square matrix; c_max = largest element of the profit matrix.

Worked examples

Example 1 (standard minimisation). Times (h) of operators A–D on jobs 1–4: A [10, 12, 19, 11], B [5, 10, 7, 8], C [12, 14, 13, 11], D [8, 15, 11, 9].

  1. Row minima 10, 5, 11, 8 → rows become A [0, 2, 9, 1], B [0, 5, 2, 3], C [1, 3, 2, 0], D [0, 7, 3, 1].
  2. Column minima 0, 2, 2, 0 → A [0, 0, 7, 1], B [0, 3, 0, 3], C [1, 1, 0, 0], D [0, 5, 1, 1].
  3. Row D has a single zero (job 1): assign D–1 and cross column 1. Row A now has one zero (job 2): A–2. Row B: B–3. Row C: column 3 is taken, so C–4.
  4. Four assignments on zeros → optimal. Z = 12 + 7 + 11 + 8.
  5. Minimum total time = 38 h (A–2, B–3, C–4, D–1). The reductions sum to 10 + 5 + 11 + 8 + 2 + 2 = 38, which confirms it.

Example 2 (GATE-type maximisation with an improvement step). Profit (₹ thousand) of salesmen P–S in territories 1–4: P [5, 11, 10, 12], Q [2, 4, 6, 3], R [3, 12, 5, 14], S [6, 14, 4, 11].

  1. Loss matrix = 14 − profit: P [9, 3, 4, 2], Q [12, 10, 8, 11], R [11, 2, 9, 0], S [8, 0, 10, 3].
  2. Row minima 2, 8, 0, 0 → P [7, 1, 2, 0], Q [4, 2, 0, 3], R [11, 2, 9, 0], S [8, 0, 10, 3].
  3. Column minima 4, 0, 0, 0 → P [3, 1, 2, 0], Q [0, 2, 0, 3], R [7, 2, 9, 0], S [4, 0, 10, 3].
  4. Zeros can be covered by 3 lines (row Q, column 2, column 4) < 4, so improve. Smallest uncovered element k = 2 (P, territory 3).
  5. Subtract 2 from uncovered cells, add 2 at the intersections (Q-2, Q-4): P [1, 1, 0, 0], Q [0, 4, 0, 5], R [5, 2, 7, 0], S [2, 0, 8, 3].
  6. Assign: R–4 (single zero), S–2 (single zero), then P–3, Q–1.
  7. Maximum profit = 10 + 2 + 14 + 14 = ₹40 thousand (P–3, Q–1, R–4, S–2). A check of all 24 assignments confirms it is the unique optimum.

Common mistakes

  • Doing only row reduction and forgetting column reduction.
  • Applying the method directly to a profit matrix without converting it to losses.
  • Drawing more lines than necessary; the test is the minimum number of covering lines.
  • In the improvement step, subtracting k from covered cells or forgetting to add k at intersections.
  • Reporting the reduced-matrix total (zero) or the loss total instead of the original cost or profit of the chosen cells.
  • Leaving an unbalanced matrix non-square.

For GATE PI

  • 3×3 or 4×4 minimum-cost or maximum-profit assignment by the Hungarian method (NAT).
  • Unbalanced problems with a dummy row or column, and prohibited cells.
  • Concept questions: why reductions keep the optimum, number of possible assignments, relation to transportation.
  • Practise doing the reduction, line cover and one improvement step quickly and then checking the total with the original matrix.

Quick check

  1. How many complete assignments exist for 5 jobs and 5 machines?
  2. A 3 × 4 cost matrix (3 jobs, 4 machines) is given. What do you add?
  3. After reductions, the zeros of a 4 × 4 matrix are covered by 4 lines. What next?
  4. Why is the assignment problem degenerate as a transportation problem?

Answers: 1. 5! = 120. 2. A dummy job row of zeros. 3. Make the assignment on zeros — it is optimal. 4. Only n cells are positive, but a basic solution needs 2n − 1.

Interview questions

All Operations Research interview questions

Try answering each one aloud before you open it.

  1. 1.What is the assignment problem and how is it different from the transportation problem?Concept

    It assigns n jobs to n facilities one-to-one to minimise total cost or time (or maximise profit). It is a special transportation problem in which every supply and demand equals 1 and every xᵢⱼ is 0 or 1. Because only n of the 2n − 1 basic cells are positive, it is extremely degenerate, so instead of MODI it is solved by the Hungarian method, which works directly on the cost matrix.

  2. 2.Why does subtracting a row or column minimum not change the optimal assignment?Concept

    Every feasible assignment picks exactly one element from each row and each column. Subtracting a constant k from a row therefore reduces the total cost of every assignment by the same k, so their ranking is unchanged. The reduced matrix has no negative entries, so an assignment made entirely on zeros has the least possible reduced cost and is optimal for the original matrix too.

  3. 3.Walk me through the Hungarian method.Concept

    Reduce each row by its minimum, then each column by its minimum. Try to make assignments on zeros, starting with rows or columns that have a single zero. If you cannot make n assignments, cover all zeros with the minimum number of lines; if lines are fewer than n, subtract the smallest uncovered element from all uncovered cells and add it to the cells where two lines cross, then try again. When n independent zeros exist, that assignment is optimal; report its total from the original matrix.

  4. 4.How do you handle a maximisation assignment problem?Concept

    Convert profits to opportunity losses by subtracting every element from the largest element of the matrix (or by multiplying by −1), then apply the minimisation Hungarian method. The optimal cells are the same, but the objective must be computed from the original profit matrix, not from the loss matrix.

  5. 5.How do you solve an unbalanced assignment problem or one with a prohibited assignment?Concept

    If the matrix is not square, add dummy rows or columns with zero cost (or a given idle cost) to make it square; a job assigned to a dummy facility is left undone, and a facility assigned a dummy job stays idle. A prohibited pairing gets a very large cost M so the method never chooses it unless no feasible alternative exists.

  6. 6.What does the minimum number of covering lines tell you?Concept

    It equals the maximum number of independent zeros — zeros with no two in the same row or column (König's theorem). If it equals n, a complete optimal assignment can be made on zeros. If it is less than n, the matrix must be modified by the improvement step, which creates at least one new zero in an uncovered cell while keeping all entries non-negative.

  7. 7.How is the travelling salesman problem related to the assignment problem?Concept

    A TSP is an assignment problem (each city has exactly one successor and one predecessor) with the extra condition that the assignment must form one single tour with no subtours, and with self-assignments (diagonal) prohibited by cost M. Solving it as an assignment problem gives a lower bound; if the result contains subtours, branch and bound is used to eliminate them.

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

Stuck on something here?

PreviousTransportation problemNext Integer programming: branch and bound