---

📘 Branch-and-Bound: Assignment Problem

1️⃣ Introduction to Branch-and-Bound

Branch-and-Bound is an algorithm design technique used to solve optimization problems by:

• Systematically exploring solution space (branching)
• Eliminating suboptimal solutions using bounds (bounding)

It improves upon brute force by pruning paths that cannot lead to an optimal solution.

---

2️⃣ What is the Assignment Problem?

The Assignment Problem is a fundamental combinatorial optimization problem.

🔹 Problem Statement

Given:

• n jobs and n persons
• A cost matrix C, where
  C[i][j] = cost of assigning job j to person i

Objective:

Assign exactly one job to each person such that the total assignment cost is minimum.

---

3️⃣ Why Branch-and-Bound for Assignment Problem?

• Total possible assignments = n!
• Brute force becomes impractical for large n
• Branch-and-Bound reduces search space by:
  • Calculating lower bounds
  • Eliminating costly partial solutions early

---

4️⃣ Key Concepts Used

🔹 1. State Space Tree

• Each node represents a partial assignment
• Level i corresponds to assigning job to person i
• Leaf node → complete assignment

---

🔹 2. Branching

• Assign one of the remaining jobs to the next person
• Each branch represents a possible choice

---

🔹 3. Bounding

• Calculate a lower bound (LB) on the cost of a partial solution
• If LB ≥ best known solution → prune branch

---

5️⃣ Lower Bound Calculation

For a node:

Lower Bound = cost so far
             + minimum cost of unassigned jobs

This bound helps decide whether further exploration is worthwhile.

---

6️⃣ Algorithm Steps (Assignment Problem)

1. Start with root node (no assignment)
2. Calculate lower bound
3. Select node with least lower bound (Best-First Search)
4. Branch by assigning a job
5. Update cost and bound
6. Prune nodes with higher cost than current best
7. Continue until optimal solution is found

---

7️⃣ Pseudocode (Simplified)

BranchAndBound_Assignment():
   initialize priority queue Q
   best_cost = ∞
   insert root node into Q

   while Q is not empty:
       node = extract node with least lower bound
       if node is a complete solution:
           update best_cost
       else:
           for each possible job assignment:
               create child node
               compute lower bound
               if lower bound < best_cost:
                   insert child into Q

---

8️⃣ Example (3×3 Assignment Problem)

Cost Matrix:

Person / Job	J1	J2	J3
P1	9	2	7
P2	6	4	3
P3	5	8	1

🔹 Optimal Assignment:

• P1 → J2 (2)
• P2 → J1 (6)
• P3 → J3 (1)

Minimum Cost = 9

Branch-and-Bound avoids checking all 6 permutations.

---

9️⃣ Time and Space Complexity

🔹 Time Complexity

• Worst case: O(n!)
• Practical performance is much better due to pruning

🔹 Space Complexity

• Stores nodes in priority queue
• O(n!) in worst case

---

🔟 Advantages of Branch-and-Bound

✔ Eliminates unnecessary computations
✔ Guarantees optimal solution
✔ More efficient than brute force
✔ Suitable for optimization problems

---

1️⃣1️⃣ Limitations

✖ High memory usage
✖ Worst-case still exponential
✖ Complex to implement

---

1️⃣2️⃣ Applications

• Assignment Problem
• Traveling Salesman Problem (TSP)
• Scheduling
• Integer programming
• Resource allocation

---

🔚 Conclusion

The Branch-and-Bound technique is a powerful method for solving the Assignment Problem efficiently by combining systematic search and intelligent pruning.

Branch-and-Bound explores only promising solutions while guaranteeing optimality.

---