Assignment Problem Explained with Example

Assignment Problem: Complete In-Depth Guide (Beginner to Advanced)

📚 Table of Contents

• Introduction
• Core Intuition
• Mathematical Formulation
• Detailed Example
• Hungarian Algorithm Deep Dive
• Full Step-by-Step Solution
• Mathematical Foundations
• Complexity Analysis
• Real-World Applications
• Comparison with Other Methods
• Conclusion

📘 Introduction

The Assignment Problem is one of the most fundamental optimization problems in operations research. It focuses on assigning tasks to resources efficiently while minimizing total cost.

This problem appears everywhere — from logistics to AI, workforce planning, and scheduling systems.

💡 Key Idea: One task → One resource → Minimum total cost

🧠 Core Intuition

Imagine a situation where multiple workers can perform multiple tasks, but each worker performs each task at a different cost.

The challenge is not just picking the cheapest option for each task independently — because that might assign the same worker multiple tasks.

Instead, we must ensure:

• Each task is assigned exactly once
• Each worker is used exactly once
• Total cost is minimized

📐 Mathematical Formulation

Objective Function:

$$ Z = \sum_{i=1}^{n} \sum_{j=1}^{n} C_{ij} X_{ij} $$

Constraints:

$$ \sum_{j=1}^{n} X_{ij} = 1 \quad \forall i $$ $$ \sum_{i=1}^{n} X_{ij} = 1 \quad \forall j $$

Binary Condition:

$$ X_{ij} \in \{0,1\} $$

📊 Detailed Example

Cost Matrix:

$$ \begin{bmatrix} 4 & 6 & 3 \\ 2 & 8 & 9 \\ 5 & 7 & 2 \end{bmatrix} $$

⚙️ Hungarian Algorithm Deep Dive

The Hungarian Algorithm transforms the matrix step-by-step until an optimal assignment is found.

• Row Reduction
• Column Reduction
• Zero Coverage
• Matrix Adjustment

🧮 Full Step-by-Step Solution

Step 1: Row Reduction

Row minimums:
Row1 = 3
Row2 = 2
Row3 = 2

Step 2: Reduced Matrix

$$ \begin{bmatrix} 1 & 3 & 0 \\ 0 & 6 & 7 \\ 3 & 5 & 0 \end{bmatrix} $$

Step 3: Column Reduction

$$ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 3 & 7 \\ 3 & 2 & 0 \end{bmatrix} $$

Step 4: Optimal Assignment

Job1 → C
Job2 → A
Job3 → B

📊 Mathematical Foundations

Matrix Transformation

$$ A' = A - \min(A_{row}) $$

Optimization Property

Adding/subtracting constants does not change optimal assignment:

$$ Z' = Z - k $$

Graph Theory View

Assignment problem = Bipartite Matching Problem

$$ G = (U, V, E) $$

⏱ Complexity Analysis

Hungarian Algorithm runs in:

$$ O(n^3) $$

This makes it efficient even for moderately large problems.

🌍 Real-World Applications

• Job scheduling
• Machine-task assignment
• Delivery optimization
• Airline crew scheduling
• AI matching systems

⚖️ Comparison with Other Methods

Method	Efficiency	Accuracy
Hungarian	High	Optimal
Greedy	Fast	Suboptimal
Brute Force	Very Slow	Optimal

🎯 Conclusion

✔ Assignment problem is a core optimization concept ✔ Hungarian Algorithm guarantees optimal solution ✔ Widely used in industry and research

How the Hungarian Algorithm Solves Assignment Problems Efficiently

The **Hungarian Algorithm** is a way to solve the assignment problem efficiently. Let’s break down how it works in straightforward terms:

#### What is the Hungarian Algorithm?

Imagine you’re organizing a small event and need to assign three tasks to three volunteers. Each volunteer has a different cost for each task. The Hungarian Algorithm helps you figure out the best way to assign these tasks to volunteers so the total cost is minimized.

#### How Does It Work?

Here’s a simple step-by-step explanation:

1. **Prepare the Cost Matrix**: Start by writing down the cost for each volunteer-task pair in a grid (matrix). Each row represents a volunteer, and each column represents a task.

2. **Subtract Row Minimums**: For each row, find the smallest cost and subtract it from every number in that row. This step makes sure that each row has at least one zero, which simplifies finding the best matches.

3. **Subtract Column Minimums**: After adjusting the rows, do the same thing for each column. Find the smallest number in each column and subtract it from every number in that column. This ensures that each column also has at least one zero.

4. **Cover All Zeros**: Now, you need to cover all the zeros in the matrix using the fewest number of horizontal and vertical lines. Think of it as drawing lines on a piece of paper to cover all the zeros.

5. **Adjust the Matrix**: If you haven’t covered all the zeros with the minimum number of lines, you need to make some adjustments. Find the smallest number that isn’t covered by a line, subtract it from all uncovered numbers, and add it to the numbers where lines intersect. This step helps create more zeros.

6. **Find the Best Assignment**: Once you’ve covered all the zeros with the minimum number of lines, you can determine the best way to assign tasks. Look for a way to assign each task to a volunteer where each line is covered, and you get the lowest total cost.

#### Example in Simple Terms

We have the following cost matrix:

4 2 5

6 8 7

3 9 2

### Step 1: Subtract Row Minimums

- For the first row, the smallest number is 2. Subtract 2 from each number in the first row:

  

  4 - 2 = 2

  2 - 2 = 0

  5 - 2 = 3

  

  Resulting first row: `2 0 3`

- For the second row, the smallest number is 6. Subtract 6 from each number in the second row:

  

  6 - 6 = 0

  8 - 6 = 2

  7 - 6 = 1

  

  Resulting second row: `0 2 1`

- For the third row, the smallest number is 2. Subtract 2 from each number in the third row:

  

  3 - 2 = 1

  9 - 2 = 7

  2 - 2 = 0

  

  Resulting third row: `1 7 0`

The matrix after subtracting row minimums:

2 0 3

0 2 1

1 7 0

### Step 2: Subtract Column Minimums

- For the first column, the smallest number is 0. Subtract 0 from each number in the first column (no change needed):

  

  2 - 0 = 2

  0 - 0 = 0

  1 - 0 = 1

  

  Resulting first column: `2 0 1`

- For the second column, the smallest number is 0. Subtract 0 from each number in the second column (no change needed):

  

  0 - 0 = 0

  2 - 0 = 2

  7 - 0 = 7

  

  Resulting second column: `0 2 7`

- For the third column, the smallest number is 0. Subtract 0 from each number in the third column (no change needed):

  

  3 - 0 = 3

  1 - 0 = 1

  0 - 0 = 0

  

  Resulting third column: `3 1 0`

The matrix after subtracting column minimums:

2 0 3

0 2 1

1 7 0

### Step 3: Cover All Zeros

To cover all zeros with the minimum number of horizontal and vertical lines:

- Cover the first column with a vertical line.

- Cover the second row with a horizontal line.

- Cover the third column with a vertical line.

We use 3 lines, which is the number of rows (or columns), so the assignment is possible.

### Step 4: Find the Optimal Assignment

Using the covered zeros:

- **Zero at (1,2)**: Assign Task 2 to Volunteer 1.

- **Zero at (2,1)**: Assign Task 1 to Volunteer 2.

- **Zero at (3,3)**: Assign Task 3 to Volunteer 3.

### Solution

The optimal assignment is:

- **Task 1** to **Volunteer 2** (cost = 6)

- **Task 2** to **Volunteer 1** (cost = 2)

- **Task 3** to **Volunteer 3** (cost = 2)

**Total Minimum Cost** = 6 + 2 + 2 = 10

### Summary

- **Hungarian Algorithm**: A method to solve the assignment problem by making the cost matrix simpler and then finding the best way to assign tasks.

- **Steps**: Adjust the cost matrix, cover zeros with lines, adjust again if necessary, and find the optimal assignments.

- **Purpose**: Helps minimize the total cost when assigning tasks to people or resources.

By following these steps, the Hungarian Algorithm efficiently finds the best assignments and helps save time and money.