Branch and Bound

Optimization · Axiom Academy

A systematic enumeration method for solving integer optimization problems Branch and Bound explores the solution space as a tree. Each node represents a subproblem obtained by fixing certain decision variables. The root node is the original problem with no variables fixed. The algorithm maintains an incumbent (best feasible solution found so far) and a bound (best possible objective value in each subproblem). 2. Branching: Splitting into Subproblems When a subproblem has fractional solutions, we branch by selecting a fractional variable and creating two child subproblems: one where the variable is rounded down, and one where it's rounded up. For example, if x = 2.7 in a relaxation, we create two branches: x 2 and x 3. At each node, we solve the LP relaxation (ignore integrality constraints). This gives a bound on the best possible objective in this subproblem. For a minimization problem, the LP relaxation provides a lower bound . If this bound is worse than the current incumbent, we can prune this node. 4. Pruning: Eliminating Subproblems A node can be pruned (not explored further) in three cases: Pruning dramatically reduces the search space, making branch and bound practical for large problems. 5. The Complete Search Process The algorithm continues until all nodes are either pruned or explored. The search tree grows dynamically, with promising branches explored first (best-first search) or depth-first for memory efficiency.

This is the written version of the interactive lesson above. See the full Optimization course.