4. Bounding Functions
- What a bounding function must do
- The difference between tight and loose bounds
- Upper bounds vs. lower bounds
- Trade-offs between bound quality and computation cost
- Why bounding functions determine practical performance
In Branch & Bound, the search is not guided by brute force alone. It is guided by estimates.
Those estimates come from bounding functions, which tell us how promising a partial solution is and whether it is still worth exploring.
4.1 What is a bounding function?
A bounding function maps a partial solution to a numerical estimate of its best possible completion.
The exact interpretation depends on the optimization problem:
- in maximization, it is often an upper bound
- in minimization, it is often a lower bound
In both cases, the purpose is the same: determine whether the node can still produce a better solution than the incumbent.
4.2 Safe bounds
A bounding function must be safe.
That means it must never underestimate what is possible in maximization, and never overestimate what is possible in minimization, if it is used for pruning.
Otherwise, the algorithm may incorrectly discard a branch that actually contains the optimal solution.
4.3 Tight vs. loose bounds
Not all valid bounds are equally useful.
- A tight bound stays close to the true best achievable value.
- A loose bound is valid, but too optimistic or too conservative.
Tight bounds enable more pruning because they distinguish promising nodes from weak ones more precisely.
Loose bounds preserve correctness, but often leave too many branches alive.
4.4 Bound quality vs. computation cost
A better bound is not always better in practice.
There is a trade-off:
- a cheap bound may be weak but fast to compute
- a strong bound may prune more, but cost more per node
Practical Branch & Bound design often depends on balancing these two effects.
4.5 Bounding in maximization and minimization
The pruning rule depends on the optimization direction.
In maximization:
In minimization:
These rules express the same principle: discard nodes that cannot improve the best known solution.
4.6 Where bounds come from
Bounding functions are problem-specific.
They are often derived from:
- relaxations of the original problem
- greedy approximations
- simplified subproblems
- mathematical inequalities
For example, in 0/1 Knapsack, a common upper bound comes from allowing fractional items, which makes the problem easier and gives a safe optimistic estimate.
4.7 Why bounding functions matter so much
In theory, Branch & Bound is defined by branching, bounding, and pruning. In practice, its performance is often dominated by the quality of the bound.
Two algorithms with the same branching structure can behave very differently if one uses a strong bound and the other uses a weak one.
This is why bounding functions are often the most important design decision in a Branch & Bound implementation.
4.8 Summary
- Bounds estimate the best possible completion of a partial solution
- They must be safe to preserve correctness
- Tight bounds improve pruning
- Strong bounds may cost more to compute
- Practical performance depends heavily on bound design
Next: Part 5 — Node Selection Strategies
Once bounds are available, the next question is not only which nodes are still alive, but also which live node should be explored first.
In Part 5, we will study the main node selection strategies and how they affect memory usage, incumbent discovery, and overall pruning effectiveness.