Assignment Problem: Hungarian Method, Optimality, and Real-World Applications

Core Concepts

What is an Assignment Problem?

An assignment problem is a special type of linear programming problem where the goal is to assign a set of tasks to a set of agents (e.g., workers, machines, vehicles) such that:

• Each task is assigned to exactly one agent.
• Each agent is assigned at most one task.
• The total cost (or time) of assignments is minimized (or profit maximized).

Key Features:

• Balanced problem: Number of tasks = Number of agents.
• Unbalanced problem: Number of tasks ≠ Number of agents (requires dummy rows/columns).
• Cost matrix: A square matrix where $c_{ij}$ = cost of assigning agent $i$ to task $j$.

---

Mathematical Formulation

For $n$ agents and $n$ tasks, the problem can be written as: Minimize $Z={\sum }_{i=1}^n{\sum }_{j=1}^n{c}_{ij}{x}_{ij}$ Subject to:

• ${\sum }_{j=1}^n{x}_{ij}=1$ for all $i$ (each agent assigned to exactly one task).
• ${\sum }_{i=1}^n{x}_{ij}=1$ for all $j$ (each task assigned to exactly one agent).
• $x_{ij}\in \{0,1\}$ (binary variable: 1 if assigned, 0 otherwise).

| Agents\Tasks | Task 1 | Task 2 | Task 3 |
|--------------|--------|--------|--------|
| Agent 1      | 4      | 6      | 8      |
| Agent 2      | 2      | 3      | 4      |
| Agent 3      | 4      | 8      | 5      |

Cost matrix for 3 agents and 3 tasks (Example 1).

---

Hungarian Method (HAM): Step-by-Step Solution

Step 1: Subtract Row Minima

For each row, subtract the smallest element in that row from all elements of the row. Why? This ensures at least one zero in each row, simplifying the assignment process.

| Agents\Tasks | Task 1 | Task 2 | Task 3 | Row Min |
|--------------|--------|--------|--------|---------|
| Agent 1      | 0      | 2      | 4      | 4       |
| Agent 2      | 0      | 1      | 2      | 2       |
| Agent 3      | 0      | 4      | 1      | 4       |

After subtracting row minima (Example 1).

---

Step 2: Subtract Column Minima

For each column, subtract the smallest element in that column from all elements of the column. Why? This ensures at least one zero in each column, creating a matrix with optimal assignment candidates.

| Agents\Tasks | Task 1 | Task 2 | Task 3 | Col Min |
|--------------|--------|--------|--------|---------|
| Agent 1      | 0      | 1      | 3      | 0       |
| Agent 2      | 0      | 0      | 1      | 0       |
| Agent 3      | 0      | 3      | 0      | 0       |

After subtracting column minima (Example 1).

---

Step 3: Draw Lines to Cover All Zeros

Use the minimum number of lines (horizontal/vertical) to cover all zeros in the matrix.

• If the number of lines = number of agents ($n$), proceed to Step 4.
• If fewer than $n$ lines are needed, adjust the matrix (go to Step 5).

| Agents\Tasks | Task 1 | Task 2 | Task 3 |
|--------------|--------|--------|--------|
| Agent 1      | 0      | 1      | 3      |
| Agent 2      | 0      | 0      | 1      |
| Agent 3      | 0      | 3      | 0      |

Lines covering all zeros (Example 1):

• Line 1: Row 1
• Line 2: Column 1
• Line 3: Column 3 (Total lines = 3 = number of agents → Optimal assignment possible.)

---

Step 4: Optimal Assignment

Select zeros such that no two zeros are in the same row or column. This gives the optimal assignment. For Example 1:

• Assign Agent 1 → Task 1 (cost = 4).
• Assign Agent 2 → Task 2 (cost = 3).
• Assign Agent 3 → Task 3 (cost = 5). Total cost = 4 + 3 + 5 = Rs. 12.

---

Step 5: Adjustment for Non-Optimal Cases (If Lines < $n$)

If fewer than $n$ lines are needed, adjust the matrix:

1. Find the smallest uncovered element.
2. Subtract it from all uncovered elements.
3. Add it to elements covered by two lines.
4. Repeat Step 3 (drawing lines).

---

Dominance Rule

A dominance rule helps reduce the size of the cost matrix by eliminating dominated rows or columns.

• Row dominance: If all elements in Row $i$ are ≥ all elements in Row $j$, eliminate Row $i$.
• Column dominance: If all elements in Column $j$ are ≥ all elements in Column $k$, eliminate Column $j$.

Example: Original cost matrix:

| Agents\Tasks | Task 1 | Task 2 | Task 3 |
|--------------|--------|--------|--------|
| Agent 1      | 5      | 6      | 7      |
| Agent 2      | 4      | 5      | 6      |
| Agent 3      | 3      | 4      | 5      |

• Row dominance: Agent 1 is dominated by Agent 3 (all costs ≥ Agent 3’s costs). Eliminate Agent 1.
• Column dominance: Task 3 is dominated by Task 1 (all costs ≥ Task 1’s costs). Eliminate Task 3. Reduced matrix:

| Agents\Tasks | Task 1 | Task 2 |
|--------------|--------|--------|
| Agent 2      | 4      | 5      |
| Agent 3      | 3      | 4      |

---

MODI Method for Testing Optimality (Transportation Problem Context)

While the Hungarian Method is for assignment problems, the Modified Distribution (MODI) method is used in transportation problems to test the optimality of an initial solution. However, its principles overlap with assignment problems:

1. Calculate $u_i$ (row factors) and $v_j$ (column factors) such that $c_{ij}+u_i+v_j=\text{constant}$ for all assigned cells.
2. For unassigned cells, compute $c_{ij}-(u_i+v_j)$.
   • If all values ≥ 0, the solution is optimal.
   • If any value < 0, the solution is not optimal, and adjustments are needed.

---

Worked Example: Pathao Driver Assignment

Scenario: Pathao has 3 drivers (A, B, C) and 3 ride requests (R1, R2, R3) in Kathmandu. The time (in minutes) each driver takes to reach each request is given below. Assign drivers to minimize total time.

| Drivers\Requests | R1 | R2 | R3 |
|------------------|----|----|----|
| A                | 8  | 6  | 10 |
| B                | 5  | 7  | 9  |
| C                | 6  | 4  | 8  |

Solution:

1. Subtract row minima:

   | A | 2 | 0 | 4 |
   | B | 0 | 2 | 4 |
   | C | 2 | 0 | 4 |
   

2. Subtract column minima:

   | A | 2 | 0 | 0 |
   | B | 0 | 2 | 0 |
   | C | 2 | 0 | 0 |
   

3. Draw lines: 3 lines needed (optimal).
4. Assign:
   • A → R2 (6 min)
   • B → R1 (5 min)
   • C → R3 (8 min) Total time = 6 + 5 + 8 = 19 minutes.

---

In the Real World

1. Pathao/Khalti Ride Assignment:

   • Idea Used: Hungarian Method for optimal driver-ride matching.
   • How? Pathao’s algorithm assigns the nearest available driver to a ride request while minimizing total travel time for all drivers. The cost matrix here is the estimated time each driver takes to reach the ride location.

2. Bank Loan Officer Assignment (Nepal Bank Limited):

   • Idea Used: Assignment problem to match loan officers to pending loan applications.
   • How? Each officer has a different processing speed and expertise. The bank uses an assignment model to pair officers with loans such that the total processing time is minimized, reducing delays for customers.

3. NTC Traffic Route Optimization:

   • Idea Used: Assignment problem for optimizing bus routes.
   • How? NTC assigns buses to routes based on demand and distance to minimize fuel costs and travel time. For example, assigning a bus to a high-demand route (e.g., Kathmandu-Lalitpur) reduces congestion on alternative routes.

4. Daraz Order Fulfillment:

   • Idea Used: Assignment of warehouse staff to order picking tasks.
   • How? Daraz’s warehouses use assignment models to assign pickers to orders such that the total time to fulfill orders is minimized, improving delivery speed.

5. NEPSE Stock Trading Assignment:

   • Idea Used: Assigning brokers to client trades.
   • How? Stock brokers use assignment problems to match trades to brokers based on urgency and commission rates, ensuring the fastest execution for clients.

---

Comparison Table: Assignment Problem vs. Transportation Problem

---

Advantages and Disadvantages

Advantages:

1. Efficiency: The Hungarian Method guarantees an optimal solution in polynomial time ($O(n^3)$).
2. Flexibility: Works for both minimization and maximization problems (convert maximization to minimization by subtracting costs from a large number).
3. Real-World Applicability: Used in logistics, scheduling, and resource allocation across industries.

Disadvantages:

1. Limited to Square Matrices: Requires equal number of agents and tasks (dummy rows/columns needed otherwise).
2. Computational Complexity: For large $n$ (e.g., $n>50$), the method becomes computationally intensive.
3. Assumption of Independence: Assumes tasks are independent; dependencies require more complex models (e.g., network flow).

---

Common Mistakes to Avoid

1. Ignoring Dummy Rows/Columns: For unbalanced problems, adding dummy agents/tasks with zero cost is essential.
2. Incorrect Line Drawing: In Step 3, ensure the minimum number of lines covers all zeros. Overlooking this leads to suboptimal solutions.
3. Forgetting to Adjust Matrix: If lines < $n$, failing to adjust the matrix (Step 5) results in incorrect optimality checks.
4. Misapplying Dominance Rules: Only eliminate rows/columns if they are strictly dominated (all elements ≥ another row/column).

---

Exam Tip

1. Understand the Hungarian Method Steps:

   • Examiners often ask for a step-by-step trace of the method. Practice solving problems by showing all intermediate matrices (row/column reductions, line drawing).
   • Example question: "Solve the following assignment problem using the Hungarian Method. Show all steps."

2. Recognize Problem Types:

   • Assignment problems are distinct from transportation problems. Know when to use the Hungarian Method vs. MODI or Vogel’s Approximation.
   • Tip: If the problem involves "matching" agents to tasks with a cost matrix, it’s an assignment problem.

3. Handle Unbalanced Problems:

   • Always check if the number of agents equals the number of tasks. If not, add dummy rows/columns with zero cost.
   • Example: If 4 agents and 3 tasks, add 1 dummy task with all costs = 0.

4. Interpret Results:

   • After finding the optimal assignment, always state the total cost/time and list the pairings (e.g., "Agent 1 → Task 2").
   • Example answer: "The optimal assignment yields a total cost of Rs. 12 with the following pairs: (A, Task 1), (B, Task 2), (C, Task 3)."

5. Dominance Rule Shortcuts:

   • In exams, use dominance rules to reduce the problem size before applying the Hungarian Method. This saves time and reduces errors.
   • Example: If a row/column is dominated, eliminate it and adjust the matrix accordingly.

6. Real-World Applications:

   • Questions may ask for applications of assignment problems. Be ready to cite examples like:
     • Driver-ride matching (Pathao).
     • Loan officer assignment (banks).
     • Traffic route optimization (NTC).
   • Tip: Relate numerical examples to these scenarios (e.g., "This is similar to assigning Pathao drivers to rides in Kathmandu").

7. MODI Method Clarity:

   • While MODI is primarily for transportation problems, understand its principle of testing optimality using $u_i$ and $v_j$. Some exams may link it to assignment problems indirectly.

---