Assignment Problem (Branch & Bound)

Assignment Problem — Branch and Bound

Most articles on this topic throw a cost matrix at you and expect you to magically follow along. This one won't do that. Let's actually understand why this algorithm works before we touch any numbers.

What Even Is the Assignment Problem?

Imagine you're a manager. You have N workers and N tasks. Each worker has a different cost (or efficiency) for each task — maybe Ravi is great at coding but slow at testing, and Priya is the opposite. You want to assign tasks to workers so that the total cost is minimum, with one rule: one worker per task, one task per worker.

That's it. That's the assignment problem.

Formally:

• We have a cost matrix C[i][j] — the cost of assigning job j to worker i

• Objective: Minimize total assignment cost

• Constraints:

  • Each job is assigned to exactly one facility

  • Each facility handles exactly one job

Why Not Just Use Brute Force?

For N workers and N jobs, the total number of possible assignments = N! (N factorial).

Yeah. Brute force dies at N=15. We need something smarter.

This is the real reason we study Branch and Bound. It's not just an exam topic — it's a survival strategy when the search space explodes.

Why Branch and Bound? (The Honest Answer)

You've probably seen Branch and Bound explained with a tree diagram and some hand-wavy explanation about "pruning". Let me be more direct.

Branch and Bound works because of one insight:

If the lower bound of a partial assignment is already worse than our best known solution, there's zero reason to explore it further.

It's like searching for a cheap flight. If you're already at ₹15,000 for just the first leg, and your best complete route so far costs ₹12,000 total — you abandon this path immediately. You don't check the hotels. You don't check the return flight. You move on.

Branch and Bound does the exact same thing, systematically.

The Algorithm — Step by Step

Step 1: Build the State Space Tree

Each node in the tree represents a partial assignment — "Worker 1 is assigned Job 2, Worker 2 is assigned Job 3, ...and we haven't decided the rest yet."

At the root: nobody is assigned anything. At depth k: the first k workers have been assigned jobs. At the leaves: all N workers have complete assignments.

Step 2: Calculate the Lower Bound at Each Node

This is the heart of the algorithm. At every node, we compute the minimum possible cost this partial assignment can lead to.

The most common approach:

1. Take the already-assigned costs (fixed)

2. For remaining unassigned workers, take the minimum cost available in their row (from unassigned columns only)

3. Lower Bound = fixed costs + sum of those row minimums

This bound is optimistic — it assumes the best possible future from here. If even the best-case future is worse than our current best solution, we prune this branch.

Step 3: Branch (Explore the Most Promising Node First)

From each node, create child nodes by assigning the next worker to each remaining unassigned job. Use a priority queue (min-heap) ordered by lower bound — always explore the node with the smallest lower bound first. This is the "Best-First Search" variant.

Step 4: Prune

If a node's lower bound ≥ current best complete solution → kill it. Don't expand. Move on.

Step 5: Update Best Solution

When you reach a leaf node (complete assignment), compare its cost to the best solution found so far. Update if it's better.

Worked Example

Let's take a 4×4 cost matrix:

Row Reduction (subtract row minimum from each row):

Sum of row mins = 2 + 3 + 1 + 4 = 10 → This is the initial lower bound.

Column Reduction (subtract column minimum from each column):

After row reduction, check each column — if any column has no zero, subtract its minimum.

In this case, all columns already have at least one zero → no further reduction needed.

Root node lower bound = 10

Now we branch. Assign Worker 1 to each job and compute the lower bound for each child node. The child with the smallest lower bound gets explored first, and so on recursively.

The complete expansion of this tree would result in the optimal assignment: W1→J2, W2→J3, W3→J1... and so on — with total cost = 13 (for this example).

The Bounding Function — Why Row/Column Reduction Works

When we reduce rows and columns, we're not changing which assignment is optimal — we're just shifting the cost scale. Any valid assignment will "collect" at least one cost from each row and one from each column. So the sum of row minimums is a valid lower bound — no complete assignment can cost less than this.

This is the same idea used in the Hungarian Algorithm, but Branch and Bound uses it more dynamically, recalculating at each node.

Complexity

The worst case is still factorial — Branch and Bound doesn't escape that theoretically. But in practice, good bounding functions prune most branches early, making it far faster than pure brute force.

Common Mistakes Students Make

1. Forgetting to exclude already-assigned columns when computing the lower bound
When computing the bound for a partial assignment, only consider rows and columns that are still free.

2. Using cost directly instead of reduced cost
Always apply row+column reduction. Computing bounds on the raw matrix gives loose bounds and reduces pruning effectiveness.

3. Confusing minimization with maximization
For maximization (e.g., profit matrix), negate the matrix values to convert it to a minimization problem, or adjust the bounding logic accordingly.

Branch and Bound vs Other Approaches

For exams: Branch and Bound is important because it's a general technique — it applies to TSP, 0/1 Knapsack, and many other NP-Hard problems. The Assignment Problem is just a clean way to learn it.

Real-World Applications

• Job scheduling in manufacturing plants

• Task allocation in distributed systems

• Vehicle routing (simplified)

• Exam timetabling in universities

• Hospital staff rostering

Quick Revision Summary

1. Represent problem as a cost matrix C[i][j]
2. Compute lower bound using row + column reduction
3. Build state space tree — each level assigns one worker
4. Use Best-First Search with a min-heap (priority queue)
5. At each node:
   a. Compute lower bound
   b. If LB >= best solution → PRUNE
   c. Else → expand children
6. At leaf nodes → update best solution
7. Return the optimal assignment

Related Notes

Explore more topics from the same series:

• Branch and Bound Technique — Exact optimization through intelligent pruning

• Traveling Salesman Problem — Exact Solution via Branch and Bound

• Fraction Knapsack (Greedy) — a greedy alternative for similar optimization

• Dynamic Programming – 0/1 Knapsack — DP approach to optimization problems

• Greedy Approach for Algorithm Design — understand when greedy is enough

• Dijkstra's Algorithm — another classic "best-first" search idea

• Graph Theory — the foundation behind state space trees

• MST – Kruskal's & Prim's Algorithm — more greedy optimization strategies

• Binary Search Tree — tree structures and traversal logic

• DAA PYQ (Previous Year Questions) — practice questions on this topic

External References

• CLRS — Introduction to Algorithms, Chapter on Branch and Bound

• GeeksForGeeks — Assignment Problem using Branch and Bound

• CP-Algorithms — Hungarian Algorithm (alternative optimal approach)

• Wikipedia — Branch and Bound

Written as part of the DAA (Design and Analysis of Algorithms) series. If something's unclear or you spot an error, open a note and fix it — that's the spirit of this platform.