Branch and Bound

The algorithm implicitly enumerates all candidate solutions by constructing a state space tree. The root represents the entire solution space. Each branching step partitions a parent subproblem into smaller, mutually exclusive child subproblems by fixing a discrete decision variable. This recursive decomposition continues until a node represents a single feasible solution or is proven suboptimal. Unlike brute-force enumeration, the tree is never fully materialized; large regions are discarded through bounding.

A bounding function computes an optimistic estimate (lower bound for minimization, upper bound for maximization) of the best achievable objective value within a subproblem. Common bounding techniques include:

• Linear Programming (LP) Relaxation: Relaxing integrality constraints to solve a continuous version quickly.
• Lagrangian Relaxation: Removing complicating constraints and penalizing their violation in the objective.
• Combinatorial Bounds: Exploiting problem-specific structures like minimum spanning trees for the Traveling Salesman Problem. If the bound on a node is worse than the current incumbent (best known feasible solution), the entire subtree is pruned.

The order in which subproblems are explored critically impacts memory consumption and the speed of finding a good incumbent:

• Best-First Search: Always expands the node with the most promising bound. This minimizes total nodes explored but requires storing the entire active frontier, leading to high memory usage.
• Depth-First Search: Descends rapidly to a leaf node to find a feasible solution quickly, then backtracks. This has low memory overhead (linear in tree depth) but may explore more nodes overall.
• Hybrid Strategies: Often combine both, using depth-first to find a strong incumbent early, then switching to best-first for optimality proof.

The incumbent is the best feasible integer solution discovered at any point during the search. Its objective value serves as the global upper bound (for minimization problems). The incumbent is critical because any subproblem whose lower bound exceeds the incumbent's value can be immediately discarded. Heuristics are often applied at nodes to quickly find high-quality feasible solutions and tighten this bound, dramatically accelerating convergence. The algorithm terminates when no active nodes remain with a bound better than the incumbent.

Choosing which fractional variable to branch on at a node significantly affects performance. Common heuristics include:

• Most Infeasible Branching: Select the variable with a fractional value closest to 0.5, aiming to make the largest impact.
• Strong Branching: Test a subset of candidate variables by partially solving both child LPs, then select the one that yields the best combined bound improvement. This is computationally expensive per node but often reduces the total tree size.
• Pseudocost Branching: Uses historical information about the objective change per unit change in a variable to estimate the impact of branching without resolving LPs.

Branch and Bound is an anytime algorithm—it can be stopped early and still provide a feasible solution with a provable quality guarantee. The optimality gap is the relative difference between the incumbent and the best remaining bound. The search terminates when:

• The gap reaches zero (optimality proven).
• A user-specified tolerance (e.g., 0.01%) is achieved.
• A time or node limit is hit. This makes it practical for large-scale industrial Mixed-Integer Linear Programming (MILP) problems where proving strict optimality is computationally prohibitive.