Skip to the content

Topics Covered

Formulation Hungarian Method Row / Column Reduction Cover Lines Unbalanced AP Maximization AP Restricted AP
On this page
  1. 1. The Assignment Problem
  2. 2. Mathematical Formulation
  3. 3. Why a Specialised Method?
  4. 4. Hungarian Method (Minimization, Balanced AP)
  5. 5. Unbalanced Assignment Problem
  6. 6. Maximization Assignment Problem
  7. 7. Restricted Assignment Problem
  8. 8. Travelling Salesman Problem (an Assignment Variant)
  9. 9. Summary Workflow
  10. Key Take-aways

1. The Assignment Problem

DEFINITION

The Assignment Problem is a special case of the transportation problem in which \(n\) tasks (jobs) must be assigned to \(n\) agents (workers / machines), one-to-one, so as to minimise total cost (or maximise profit). Each agent does exactly one job and each job is done by exactly one agent.

Examples:

2. Mathematical Formulation

Let \(c_{ij}\) = cost of assigning agent \(i\) to job \(j\) (\(i, j = 1, \ldots, n\)) and \(x_{ij} \in \{0, 1\}\) the assignment variable. Then:

\[ \text{Minimise } Z \;=\; \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}\, x_{ij} \]

Subject to:

\[ \sum_{j=1}^{n} x_{ij} = 1, \quad i = 1, 2, \ldots, n \quad \text{(each agent does exactly one job)}, \] \[ \sum_{i=1}^{n} x_{ij} = 1, \quad j = 1, 2, \ldots, n \quad \text{(each job done by exactly one agent)}, \] \[ x_{ij} \in \{0, 1\}. \]

It can be viewed as a balanced TP with all supplies and demands equal to 1.

3. Why a Specialised Method?

Solving an AP through TP/Simplex works but is slow because every BFS has only \(n\) non-zero values (one per row/column) but the TP framework expects \(2n − 1\) — so each AP is heavily degenerate. The Hungarian method (König 1916, Egerváry 1931, Kuhn 1955) exploits the assignment structure to solve the problem in \(O(n^3)\) time using only integer arithmetic.

4. Hungarian Method (Minimization, Balanced AP)

Algorithm

  1. Row reduction: Subtract the smallest element of each row from every element of that row. After this step every row has at least one zero.
  2. Column reduction: From the resulting matrix, subtract the smallest element of each column from every element of that column. After this step every row and every column has at least one zero.
  3. Test for optimum:
    • Try to make assignments to zeros — one per row and one per column.
    • If this is possible with \(n\) zeros (one in each row and column), an optimum assignment has been found. Stop.
  4. Modify the matrix if no optimum yet:
    1. Draw the minimum number of horizontal / vertical lines that cover all zeros. Let the number of lines be \(k\).
    2. If \(k = n\), optimum is reached but assignments need to be made more carefully — go back to step 3.
    3. If \(k < n\), find the smallest uncovered element \(\theta\).
    4. Subtract \(\theta\) from every uncovered element and add \(\theta\) to every element covered by two lines (i.e., at the intersection of horizontal and vertical lines).
    5. Go back to step 3 with the new matrix.

Why It Works

Adding a constant to a row or column does not change the optimum assignment (only shifts the total cost by that constant). Step 4 transforms the matrix while preserving the optimal solution, until the matrix has enough zeros to make a valid assignment.

Detailed Step-by-Step Example

EXAMPLE 1 — 4 × 4 Assignment

Assign jobs J₁..J₄ to workers W₁..W₄ to minimise total time:

J₁J₂J₃J₄
W₁10121911
W₂51078
W₃12141311
W₄815119

Row reduction — subtract row mins (10, 5, 11, 8):

J₁J₂J₃J₄
W₁0291
W₂0523
W₃1320
W₄0731

Column reduction — subtract column mins (0, 2, 2, 0):

J₁J₂J₃J₄
W₁0071
W₂0303
W₃1100
W₄0511

Make assignments: Row 1: only zero at J₂ (J₁ is shared) → assign W₁→J₂. Row 4: zero at J₁ → assign W₄→J₁. Row 2: zero at J₃ → assign W₂→J₃. Row 3: zero at J₄ → assign W₃→J₄.

All 4 rows assigned ⇒ optimum found.

Total cost (read from the original matrix): W₁→J₂ = 12, W₂→J₃ = 7, W₃→J₄ = 11, W₄→J₁ = 8. Sum = 12 + 7 + 11 + 8 = 38.

EXAMPLE 2 — When step 4 modification is needed

Consider:

J₁J₂J₃
W₁354
W₂532
W₃445

Row mins: 3, 2, 4. After row reduction:

J₁J₂J₃
W₁021
W₂310
W₃001

Column mins: 0, 0, 0 — no further reduction needed. Assignments: W₁→J₁ (only zero in row 1), W₂→J₃ (only zero in row 2), W₃→J₂. All distinct columns ⇒ optimum.

Cost = 3 + 2 + 4 = 9.

5. Unbalanced Assignment Problem

If the number of agents ≠ number of jobs, add dummy rows or columns with zero costs to make the matrix square. Then apply the Hungarian method as usual.

Dummy assignments mean the corresponding agent (or job) is not used.

EXAMPLE 1 (more agents than jobs)

4 workers and 3 jobs. Add a dummy job J₄ with cost 0 for all workers:

J₁J₂J₃J₄ (dummy)
W₁914190
W₂717200
W₃918210
W₄1012180

One worker will be assigned to the dummy job — that worker remains idle.

EXAMPLE 2 (more jobs than agents)

3 workers and 4 jobs. Add a dummy worker W₄ with cost 0 for all jobs. One job will go to the dummy and stay unfinished.

6. Maximization Assignment Problem

If \(c_{ij}\) represents profit and we want to maximise:

  1. Find \(M = \max_{ij} c_{ij}\).
  2. Replace each entry by \(M - c_{ij}\) (resulting matrix has all non-negative entries with the largest profit becoming 0).
  3. Apply the Hungarian method to the new minimisation problem.
  4. The optimum assignment is the same; total profit = \(\sum c_{ij}^{\text{original}} x_{ij}\).
EXAMPLE

Profit matrix:

R₁R₂R₃
S₁405249
S₂324658
S₃565447

M = 58. Transformed (loss) matrix:

R₁R₂R₃
S₁1869
S₂26120
S₃2411

Apply Hungarian to this matrix.

7. Restricted Assignment Problem

Sometimes certain assignments are forbidden (a worker cannot do a specific job, an item cannot be shipped via a certain route).

Handling Restrictions

Assign a very large cost \(M\) (often denoted ∞ or 10⁹) to the forbidden cells before running the Hungarian method. The optimum solution will avoid these cells.

EXAMPLE

4 workers × 4 jobs but W₃ cannot do J₂ and W₁ cannot do J₄. Set those cells to M:

J₁J₂J₃J₄
W₁427M
W₂3564
W₃5M43
W₄6485

Apply Hungarian; the algorithm naturally avoids cells with M.

8. Travelling Salesman Problem (an Assignment Variant)

The classical Travelling Salesman Problem (TSP) asks for the shortest cyclic route visiting each city exactly once and returning to the origin. It can be formulated as an assignment problem with the extra constraint that the solution must form a single cycle (no sub-tours).

Pure Hungarian may yield sub-tours; specialised branch-and-bound is required for true TSP solutions. (Outside the scope of this course but worth knowing.)

9. Summary Workflow

  1. If unbalanced, add dummy row/column with zero costs.
  2. If maximization, convert to minimization with \(M - c_{ij}\).
  3. For forbidden assignments, use very large \(M\).
  4. Apply Hungarian: row reduction → column reduction → cover lines → make assignments.
  5. Report the assignment and total cost (or profit).

Key Take-aways

← Previous: Unit 1 Next: Unit 3 — Sequencing →