Discrete Mathsfor Engineers

2. The Core Idea (Branch + Bound + Pruning)

In Part 1, we modeled the problem as a search tree of partial decisions. That gave us the structure.

Now we study the mechanism that makes Branch & Bound powerful: it does not explore the tree blindly. Instead, it expands promising regions and cuts off regions that cannot improve the current best solution.

2.1 What is “branch”?

The word branch refers to the act of splitting a problem into smaller subproblems by making one additional decision.

In tree form:

• each node is a partial solution,
• each outgoing edge is a possible next choice,
• each child node represents one refinement of the current state.

For example, in 0/1 Knapsack, branching on one item usually means:

• include the item, or
• exclude the item.

2.2 What is a bound?

A bound is an estimate of the best result that could still be obtained from a given partial solution.

Since a node is not yet a complete solution, we usually do not know its final value exactly. Instead, we compute a limit that tells us how promising that node is.

In abstract form, we may write:

where B estimates the best achievable completion of the partial assignment (x₁, …, xᵢ).

2.3 Upper bounds and lower bounds

The meaning of a bound depends on the type of optimization problem.

• In maximization, we often compute an upper bound on what the node could still achieve.
• In minimization, we often compute a lower bound on the best cost still possible.

The general principle is the same: the bound tells us whether the node still has any chance of beating the current best solution.

2.4 The current best solution

Branch & Bound keeps track of the best complete feasible solution found so far. This is often called the incumbent.

The incumbent gives us a concrete threshold for pruning:

• if a node can still beat the incumbent, explore it;
• if it cannot beat the incumbent, discard it.

In maximization problems, if the upper bound of a node is not better than the incumbent value, then that node is useless.

If B(node) ≤ best, then the node can be pruned in maximization.

2.5 What is pruning?

Pruning means stopping the exploration of a branch before it reaches a leaf.

This happens when we can prove that continuing that branch is pointless. In Branch & Bound, this usually occurs for one of two reasons:

• the branch is infeasible, or
• the branch is feasible but cannot improve the incumbent.

The second reason is what distinguishes Branch & Bound from ordinary backtracking.

2.6 The core decision logic

At each node, the algorithm conceptually asks:

• Is this partial solution feasible?
• If completed optimally, could it beat the incumbent?

If the answer to the second question is no, the branch is cut immediately.

So the search follows this pattern:

1. Generate a partial solution
2. Check feasibility
3. Compute its bound
4. Compare with the incumbent
5. Expand or prune

2.7 Why pruning does not break correctness

Branch & Bound is still an exact algorithm. It does not rely on guessing or approximation alone.

Correctness is preserved because pruning is only performed when the bound proves that no completion of that branch can improve the current best known solution.

In other words, the algorithm never discards a branch that could contain a better solution.

2.8 Branch & Bound vs. Backtracking

The two techniques are related, but their goals differ.

• Backtracking mainly prunes branches that violate constraints.
• Branch & Bound also prunes branches that are valid, but not good enough to matter.

So Branch & Bound can be seen as:

That is why it is especially useful when the goal is not merely to find a solution, but to find the optimal one.