Discrete Mathsfor Engineers

6. Classic Problems

Branch & Bound is not tied to a single problem. It is a general framework that applies whenever we have:

• a combinatorial search space,
• an objective function,
• and useful bounds for pruning.

In this part, we examine the classical problems where Branch & Bound is most commonly studied and applied.

6.1 0/1 Knapsack

The 0/1 Knapsack problem is one of the most standard examples of Branch & Bound.

Each item may be either:

• included, or
• excluded.

This naturally creates a binary search tree.

A common bound is obtained from the fractional knapsack relaxation, where items are allowed to be taken fractionally.

6.2 Traveling Salesman Problem (TSP)

In the Traveling Salesman Problem, the goal is to find the shortest Hamiltonian cycle visiting each city exactly once.

Branch & Bound is often used by exploring partial tours and pruning those that cannot lead to an optimal complete tour.

Typical bounds may come from:

• minimum edge estimates,
• reduced cost matrices,
• or relaxations such as assignment-based bounds.

TSP is a classic example of how powerful bounds can dramatically reduce the search space.

6.3 Assignment Problems

Assignment problems ask how to match agents to tasks while minimizing cost or maximizing value.

A Branch & Bound solution typically branches on one assignment decision at a time, while the bound comes from a relaxed version of the remaining subproblem.

These problems are especially useful for understanding how lower bounds can guide minimization.

6.4 Scheduling Problems

Many scheduling problems can also be attacked with Branch & Bound.

Here, nodes usually represent partial schedules, and the bound estimates the best completion time or minimum remaining cost.

Scheduling is a good example of how the same framework adapts to domain-specific constraints and objectives.

6.5 Integer Programming

Branch & Bound is one of the foundational techniques behind modern integer programming solvers.

In this setting, the algorithm branches on integer variables and uses relaxations of the linear program to compute bounds.

This shows Branch & Bound at a more advanced level: it becomes a general engine for exact optimization.

6.6 The common pattern across problems

Although these problems look different on the surface, they share the same structural pattern:

1. Represent partial solutions as nodes
2. Branch by refining one decision
3. Compute a bound on the best completion
4. Prune nodes that cannot improve the incumbent

6.7 Why these are called “classic” problems

These examples are considered classic because they clearly illustrate:

• combinatorial explosion,
• the need for exact optimization,
• and the value of intelligent pruning.

They also appear repeatedly in textbooks, optimization research, and real engineering systems.

6.8 Summary

• Knapsack is the standard introductory example
• TSP shows the importance of strong bounds
• Assignment and scheduling problems show minimization use cases
• Integer programming reveals the general power of the framework
• The same three ideas always appear: branch, bound, and prune