Backtracking and Branch and Bound

Backtracking and branch and bound are systematic search paradigms that explore the space of candidate solutions as a tree, pruning subtrees that cannot lead to a valid or optimal solution to make otherwise exponential searches tractable in practice.

Definition

Backtracking is a depth-first search of the tree of partial candidate solutions that prunes a branch the moment the partial candidate cannot be completed to a valid solution; branch and bound augments this with numeric bounds on the objective so that branches whose best possible value cannot beat the incumbent are discarded.

Scope

This topic covers exhaustive-search techniques organized around a search tree: backtracking, which abandons partial candidates as soon as they violate a constraint, and branch and bound, which uses bounds on the best achievable objective to prune subtrees in optimization. It includes constraint-satisfaction examples (N-queens, graph coloring, Sudoku) and combinatorial optimization examples (traveling salesman, integer programming), and discusses why these methods remain valuable for NP-hard problems despite worst-case exponential cost.

Core questions

• How is a problem's solution space modeled as a search tree of partial assignments?
• What constraint checks let backtracking prune infeasible branches early?
• How are lower and upper bounds computed to prune branches in optimization?
• How do branching and bounding order affect practical performance?
• Why are these methods used for NP-hard problems despite exponential worst cases?

Key concepts

• search tree
• depth-first exploration
• constraint propagation
• pruning
• bounding functions
• incumbent solution
• N-queens problem
• integer programming relaxation

Key theories

Pruning of the search tree

Both paradigms organize candidate solutions as a tree explored depth-first; correctness comes from exhaustiveness, while efficiency comes from pruning subtrees that provably cannot contain a valid or improving solution.

Bounding functions in branch and bound

Branch and bound maintains the best solution found so far and a bound (e.g. an LP relaxation) on the best value attainable in each subtree; a subtree is discarded when its bound cannot improve on the incumbent.

Clinical relevance

Branch and bound is the backbone of exact combinatorial optimization in operations research, including integer and mixed-integer programming solvers used for scheduling, routing and planning. Backtracking underlies constraint solvers, SAT-style search, puzzle solvers, and parsers, where systematic search with pruning is the practical route to exact answers.

History

Backtracking was systematized as a general technique in the 1950s and 1960s, notably described by Golomb and Baumert. Branch and bound was introduced by Ailsa Land and Alison Doig in 1960 for integer linear programming and has since become central to combinatorial optimization, powering modern mixed-integer programming solvers.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

What is the difference between backtracking and branch and bound?

Backtracking is typically used for feasibility and constraint-satisfaction problems and prunes branches that violate constraints. Branch and bound targets optimization and additionally prunes using numeric bounds, discarding any subtree whose best possible objective cannot beat the best solution already found.

If these methods are exponential in the worst case, why use them?

For NP-hard problems no polynomial exact algorithm is known, but effective pruning often eliminates the vast majority of the search tree on real instances, so branch-and-bound and backtracking solvers regularly find provably optimal solutions far faster than their worst-case bounds suggest.