CoreSource checked

Branch and Bound

Searches solution branches while pruning branches that cannot improve the best result.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Optimization
Difficulty: Advanced
Family: Exact Search
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 6
Code example: Not ready
Visualization: Ready
Aliases: B&B

Overview

Branch and Bound splits a hard problem into subproblems and uses bounds to avoid exploring hopeless branches.

Core Concepts

objective functionbound pruningconstraint propagationexact searchiterative improvementstopping rule

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(1)

Average

O(b^d)

Worst

O(b^d)

Space

O(bd)

When to Use

Use Branch and Bound when you need to branch into smaller decision spaces.
Use it for integer programming with inputs like optimization problem.
Use it when you can define a score, objective, constraint, or feasibility test clearly.
Use it when the Exact Search tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when the objective is noisy or changing and the algorithm assumes stable feedback.
Avoid it when O(b^d) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not best proven solution.

What It Does

Branches into smaller decision spaces
Prunes subproblems using optimistic bounds

Use Cases

Integer programming
Scheduling problems
Combinatorial optimization

Inputs

Optimization problem
Bounding function
Incumbent solution

Outputs

Best proven solution

Key Formulas (1)

Pruning rule

prune node if lower_bound(node) ≥ best_cost

prune node if lower_bound(node) >= best_cost

Skips a minimization branch when its optimistic bound cannot beat the current best solution.

Pseudocode

1.Start with the full problem
2.Compute a bound for a subproblem
3.Prune it if the bound cannot beat the incumbent
4.Otherwise split it into smaller subproblems
5.Update the incumbent when a better complete solution is found

Canonical Example

Input: objective = minimize (x - 3)^2, start = x = 0
Output: x moves toward 3
Explanation: Branch and Bound: The algorithm repeatedly improves a candidate solution according to the objective.

Implementation Notes

Keep the input contract explicit: Optimization problem; Bounding function; Incumbent solution.
Use this step as the implementation spine: Start with the full problem.
Then preserve the next state change: Compute a bound for a subproblem.
Record why candidates are rejected so contradictions are debuggable.
Log objective values across iterations so regressions and stalled progress are visible.

Common Pitfalls

Good bounds are the difference between practical and impossible searches.
Stopping after one good-looking result without checking convergence or constraints.
Returning best proven solution without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show branches being cut off by bound checks.

Step 1 of 5: Start with the full problem

pruned-search-tree

Notes

Branch and Bound operates in O(b^d) time and O(bd) space within the Exact Search family. Key governing relation: prune node if lower_bound(node) >= best_cost. Often compared with Genetic Algorithm and Linear Programming Simplex Method.