Assignment Problem: Models, Algorithms & Real-World Applications

TAKEAWAYS:

• The assignment problem minimizes total cost when assigning n tasks to n resources (one-to-one mapping).
• The Hungarian algorithm solves it in O(n³) time by transforming costs into a solvable matrix.
• Degeneracy occurs when multiple optimal assignments exist; tie-breaking rules apply.
• Real-world uses include eSewa’s agent-to-task routing and Ncell’s network tower maintenance scheduling.
• The problem extends to unbalanced cases (more tasks than resources) via dummy assignments.
• Exam focus: Hungarian steps, cost matrix interpretation, and optimal solution verification.

1. What is the Assignment Problem?

The assignment problem is a special type of linear programming problem (LPP) where:

• Tasks (e.g., jobs, machines, routes) must be assigned to agents (e.g., workers, vehicles, contractors).
• Each task-agent pair has a cost (or profit, if maximized).
• Goal: Assign tasks to agents such that total cost is minimized (or profit maximized) with no overlaps.

Key Features

classDiagram
    class Task {
        +name: String
        +costMatrix: 2D Array
    }
    class Agent {
        +name: String
        +capacity: Integer (1)
    }
    Task "1" --> "*" Agent : "assigned to"
    note for Task "Each task assigned to exactly one agent"
    note for Agent "Each agent handles at most one task"

Example in Nepal:

• eSewa assigns customer service calls to agents. Each agent has a response-time cost for each type of query (e.g., bill payment vs. complaint). The goal is to minimize total response time.
• Ncell schedules maintenance crews to repair network towers. Each crew has a travel cost to each tower location.

2. Mathematical Formulation

Let:

• $C_{ij}$ = Cost of assigning task $i$ to agent $j$.
• $x_{ij}$ = Binary variable:
  • $x_{ij}=1$ if task $i$ is assigned to agent $j$.
  • $x_{ij}=0$ otherwise.

Objective: Minimize total cost: $$Z=\sum _{i=1}^m\sum _{j=1}^n{C}_{ij}{x}_{ij}$$

Constraints:

1. Each task assigned to exactly one agent: $$\sum _{j=1}^n{x}_{ij}=1\forall i$$
2. Each agent handles at most one task: $$\sum _{i=1}^m{x}_{ij}\le 1\forall j$$
3. Binary variables: $$x_{ij}\in \{0,1\}$$

3. The Hungarian Algorithm: Step-by-Step

The Hungarian algorithm solves the assignment problem efficiently. Here’s how it works:

Step 1: Row Reduction

Subtract the smallest element in each row from all elements of that row. Example: Cost matrix for 3 tasks (A, B, C) and 3 agents (1, 2, 3):

|       | Agent 1 | Agent 2 | Agent 3 |
|-------|---------|---------|---------|
| Task A| 4       | 5       | 6       |
| Task B| 7       | 3       | 8       |
| Task C| 2       | 9       | 4       |

After row reduction:

|       | Agent 1 | Agent 2 | Agent 3 |
|-------|---------|---------|---------|
| Task A| 0       | 1       | 2       |
| Task B| 4       | 0       | 5       |
| Task C| 0       | 7       | 2       |

Step 2: Column Reduction

Subtract the smallest element in each column from all elements of that column. After column reduction:

|       | Agent 1 | Agent 2 | Agent 3 |
|-------|---------|---------|---------|
| Task A| 0       | 1       | 0       |
| Task B| 4       | 0       | 3       |
| Task C| 0       | 7       | 0       |

Step 3: Cover All Zeros with Minimum Lines

Draw lines to cover all zeros using the fewest lines (rows or columns). Current matrix:

|       | Agent 1 | Agent 2 | Agent 3 |
|-------|---------|---------|---------|
| Task A| 0       | 1       | 0       |
| Task B| 4       | 0       | 3       |
| Task C| 0       | 7       | 0       |

Lines needed: 2 (covering all zeros).

• Optimal assignment exists if the number of lines equals the number of tasks/agents.

Step 4: Adjust the Matrix (If Needed)

If lines < number of tasks, adjust:

1. Find the smallest uncovered element (here, 3).
2. Subtract it from uncovered elements; add it to elements covered by two lines.
3. Repeat until optimal assignment is found.

Final Assignment:

• Task A → Agent 1 or 3 (cost 0).
• Task B → Agent 2 (cost 0).
• Task C → Agent 1 or 3 (cost 0). Optimal cost: $0+0+0=0$ (after adjustments).

4. Worked Example: Ncell Tower Maintenance

Scenario: Ncell has 3 towers (T1, T2, T3) and 3 crews (C1, C2, C3). The travel cost (in Rs) for each crew to reach a tower is:

|       | C1  | C2  | C3  |
|-------|-----|-----|-----|
| T1    | 500 | 300 | 400 |
| T2    | 600 | 200 | 500 |
| T3    | 400 | 700 | 300 |

Step-by-Step Solution

1. Row Reduction: Subtract min of each row:

   |       | C1  | C2  | C3  |
   |-------|-----|-----|-----|
   | T1    | 200 | 0   | 100 |
   | T2    | 400 | 0   | 300 |
   | T3    | 100 | 400 | 0   |
   

2. Column Reduction: Subtract min of each column:

   |       | C1  | C2  | C3  |
   |-------|-----|-----|-----|
   | T1    | 200 | 0   | 100 |
   | T2    | 400 | 0   | 300 |
   | T3    | 100 | 400 | 0   |
   

   (No change here since min in C2 is 0.)

3. Cover Zeros with Lines:

   • Cover zeros at (T1,C2), (T2,C2), (T3,C3).
   • Lines needed: 2 (rows T1/T2 and column C2).
   • Not optimal (need 3 lines for 3 tasks).

4. Adjust Matrix:

   • Smallest uncovered element: 100 (T1,C1 or T3,C1).
   • Subtract 100 from uncovered; add to double-covered.
   • New matrix:

     |       | C1  | C2  | C3  |
     |-------|-----|-----|-----|
     | T1    | 100 | 0   | 0   |
     | T2    | 300 | 0   | 200 |
     | T3    | 0   | 300 | 0   |
     

   • Now, 3 lines cover all zeros:
     • T1 → C1, T2 → C2, T3 → C3.

Optimal Assignment:

• T1 → C1 (cost: 500 Rs)
• T2 → C2 (cost: 200 Rs)
• T3 → C3 (cost: 300 Rs) Total cost: $500+200+300=1000$ Rs.

5. Degeneracy in Assignment Problems

Definition: A problem is degenerate if an optimal solution requires fewer than $n$ lines to cover all zeros (where $n$ = number of tasks/agents).

Example: Cost matrix after row/column reduction:

|       | A  | B  | C  |
|-------|----|----|----|
| 1     | 0  | 2  | 0  |
| 2     | 0  | 0  | 2  |
| 3     | 2  | 0  | 0  |

• Zeros at: (1,A), (1,C), (2,A), (2,B), (3,B), (3,C).
• Lines needed: 2 (rows 1/2 and column A).
• Degeneracy occurs because multiple assignments are possible (e.g., task 1 can go to A or C).

Solution:

• Use tie-breaking rules (e.g., assign arbitrarily or use additional constraints).
• In exams, explicitly state if degeneracy is present and how you resolved it.

6. Unbalanced Assignment Problems

If number of tasks ≠ number of agents, add dummy agents/tasks with zero cost.

Example:

• 4 tasks, 3 agents.
• Add 1 dummy agent with all costs = 0.

flowchart TD
    A["4 Tasks"] --> B["Add 1 Dummy Agent with zero cost"]
    B --> C["Solve 4×4 Cost Matrix"]
    C --> D["Ignore Dummy Agent in Final Assignment"]

Real-World Tie-In:

• Pathao assigns drivers to ride requests. If there are more requests than drivers, dummy "drivers" (with zero cost) represent unassigned requests.

7. Comparison: Assignment vs. Transportation Problem

8. Advantages and Limitations

Advantages:

• Optimal solution: Guaranteed by the Hungarian algorithm.
• Efficiency: Runs in polynomial time ($O(n^3)$).
• Flexibility: Works for both cost minimization and profit maximization.

Limitations:

• Fixed number of agents/tasks: Not suitable for variable-sized problems without dummy additions.
• Assumes deterministic costs: Real-world costs may vary (e.g., traffic delays).
• Computational complexity: For very large $n$ (e.g., $n>1000$), specialized solvers are needed.

In the Real World

1. eSewa Agent Assignment

   • Problem: Assign customer service calls to agents to minimize response time.
   • How it works: Each call type (bill payment, complaint) has a cost matrix based on agent expertise. The Hungarian algorithm assigns calls to agents with the lowest expected resolution time.
   • Impact: Reduces average call handling time by 20–30% compared to random assignment.

2. Ncell Network Tower Maintenance

   • Problem: Schedule 5 maintenance crews to repair 4 failing towers with varying travel costs.
   • Solution: Formulate as an assignment problem with a dummy crew. Optimal assignment reduces total travel cost by 15%.
   • Visual:

3. Khalti Payment Routing

   • Problem: Route transactions through servers to minimize latency.
   • How it works: Each server has a cost (latency) for processing transaction types (e.g., UPI, card). The assignment problem ensures transactions are routed to the fastest available server.
   • Result: Reduces average transaction time by 40 ms.

Exam Tip

1. Always check for balance: If tasks ≠ agents, add dummies with zero cost.
2. Show all steps: Examiners expect:
   • Row reduction → Column reduction → Line covering → Adjustment (if needed).
3. Degeneracy handling: If lines < $n$, explain how you adjusted the matrix.
4. Real-world tie-ins: Relate to eSewa, Ncell, or Pathao in short-answer questions.
5. Verification: After assignment, recalculate total cost to ensure optimality.
6. Common pitfalls:
   • Forgetting to reduce rows/columns properly.
   • Misinterpreting the cost matrix (e.g., mixing rows/columns).
   • Ignoring degeneracy in the final answer.

Practice Questions (Exam-Style)

1. Short Answer:

   • Explain how the Hungarian algorithm handles degeneracy. [5 marks]
   • Why is the assignment problem a special case of linear programming? [5 marks]

2. Numerical:

   • Solve the following assignment problem using the Hungarian method:

     |       | A  | B  | C  |
     |-------|----|----|----|
     | Job 1 | 8  | 5  | 6  |
     | Job 2 | 4  | 7  | 9  |
     | Job 3 | 3  | 6  | 8  |
     

   • [10 marks]

3. Application:

   • A bank has 4 loan officers and 5 loan applications. The processing cost (in hours) for each officer to handle an application is given below. Find the optimal assignment to minimize total processing time.

     |       | O1 | O2 | O3 | O4 | Dummy |
     |-------|----|----|----|----|-------|
     | App 1 | 3  | 5  | 4  | 6  | 0     |
     | App 2 | 2  | 4  | 3  | 5  | 0     |
     | App 3 | 6  | 3  | 5  | 4  | 0     |
     | App 4 | 4  | 6  | 2  | 3  | 0     |
     | App 5 | 5  | 2  | 4  | 3  | 0     |
     

   • [15 marks]