Branch and Bound Method vs Backtracking: Basic Description and Comparison

Original article reposted from the blog of “Red‑faced Student”. Click “Read original” at the bottom for more content.

1. Basic Description

The branch and bound method is similar to backtracking in that it searches the solution space tree T, but its goal differs: backtracking seeks all solutions that satisfy constraints, whereas branch and bound aims to find a single feasible solution or the optimal one that maximizes or minimizes a given objective function.

(1) Branch Search Algorithm

A “branch” uses a breadth‑first strategy to explore all adjacent nodes (E‑nodes), discarding those that violate constraints and adding the rest to the active node list. The next node is then selected from this list for further expansion.

Different ways of selecting the next E‑node lead to several branch‑search variants:

FIFO search

LIFO search

Priority‑queue‑based search

(2) Branch‑and‑Bound Search Algorithm

2. General Process of Branch‑and‑Bound

Because the solving goal differs, branch‑and‑bound searches the solution‑space tree differently from backtracking. Backtracking uses depth‑first search, while branch‑and‑bound uses breadth‑first or minimum‑cost‑first search.

The search strategy of branch‑and‑bound is: at an expanding node, generate all its child nodes (branches), then choose the next node to expand from the current active node list. To select the most promising node efficiently, a bound function is computed for each active node; the node with the best bound is chosen, steering the search toward branches that may contain the optimal solution.

Branch‑and‑bound typically searches the solution‑space tree either breadth‑first or by smallest cost (largest benefit) first. The solution‑space tree represents the ordered set of possible solutions, commonly a subset tree or permutation tree. In branch‑and‑bound, each active node gets only one chance to become an expanding node, generating all its children at once. Children leading to infeasible or non‑optimal solutions are discarded, while the rest are added back to the active list. The process repeats until a solution is found or the active list becomes empty.

3. Some Differences Between Backtracking and Branch‑and‑Bound

Both methods can solve many problems, but they differ in several aspects, such as the search order of the solution‑space tree, the data structures used to store nodes, and typical application scenarios.

Search order: backtracking uses depth‑first, branch‑and‑bound uses breadth‑first or minimum‑cost‑first.

Node storage: backtracking relies on a stack, while branch‑and‑bound uses a queue or priority queue.

Application: backtracking enumerates all feasible solutions; branch‑and‑bound seeks a feasible or optimal solution efficiently.

Original source: Red‑faced Student’s blog (http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741378.html)