Branch and Bound

The selection rule determines the order in which active subproblems (nodes) in the search tree are explored. This rule significantly impacts memory usage and how quickly a good incumbent solution is found.

• Best-First Search (Best-Bound): Always explores the node with the best (lowest for minimization) bound. This aims to improve the global bound quickly but can use significant memory.
• Depth-First Search: Explores deeply down one branch first. It uses minimal memory (O(tree depth)) and finds feasible solutions quickly, but may explore poor regions if bounds are weak.
• Hybrid Strategies: Modern solvers often use a combination, such as depth-first initially to find a good incumbent, then switching to best-first to prove optimality.

The incumbent is the best feasible solution found so far during the search. Its value provides the global benchmark against which bounds are compared.

• Fathoming (Pruning): A node is fathomed (eliminated from further consideration) if one of three conditions is met:
  1. Bound Pruning: The node's bound is worse than the incumbent's value.
  2. Feasibility Pruning: The subproblem is proven to have no feasible solution (e.g., a constraint is violated).
  3. Optimality Pruning: The node's solution is itself feasible and optimal for that subproblem; it may become the new incumbent.
• The algorithm terminates when no active nodes remain, guaranteeing the incumbent is globally optimal.

A relaxation is a modified version of a subproblem that is easier to solve but whose optimal value provides a bound for the original, harder problem.

• Linear Programming (LP) Relaxation: For an Integer Program, the integrality constraints (x must be integer) are removed, allowing fractional solutions. The LP optimum provides a lower bound for a minimization problem.
• Lagrangian Relaxation: Complicated constraints are moved into the objective function with penalty multipliers. By adjusting these multipliers, a tight bound can be found.
• Combinatorial Relaxation: A related but simpler problem is solved (e.g., a Minimum Spanning Tree relaxation for the TSP). The quality of the bound directly dictates pruning efficiency.

Integer Programming (IP) is a major mathematical optimization paradigm where branch and bound is the principal solution algorithm. An IP problem involves an objective function and constraints (like Linear Programming), but with the critical requirement that some or all variables must take integer values. This discrete nature makes IP NP-hard.

• B&B Application: The 'branch' step creates subproblems by fixing integer variables to specific values. The 'bound' step uses the continuous relaxation (allowing fractional values) to compute a bound on the best possible solution in that branch.
• Industrial Use: IP with B&B solves problems in logistics, scheduling, and resource allocation.

Heuristic search algorithms, like A* or best-first search, share a conceptual lineage with branch and bound. Both use bounds or estimates to guide exploration of a large state space. However, their guarantees differ.

• Branch and Bound: Guarantees an optimal solution upon completion, as it prunes only branches provably worse than the current best.
• *Heuristic Search (e.g., A)**: Uses a heuristic to estimate cost-to-goal; optimal if the heuristic is admissible (never overestimates).
• Synergy: Heuristics are often used within B&B to find a good initial incumbent solution, improving the bounding power early in the search.

Monte Carlo Tree Search (MCTS) is another tree-search algorithm for optimal decision-making, famous for its success in Go. It contrasts with branch and bound's deterministic approach.

• Exploration vs. Pruning: MCTS uses random sampling (Monte Carlo) to estimate the value of tree nodes, balancing exploration of new paths with exploitation of promising ones. B&B uses deterministic bounds to prune suboptimal branches completely.
• Applications: MCTS excels in domains with complex, stochastic state spaces and deep trees (e.g., games, some planning problems). B&B is preferred for deterministic combinatorial optimization with clear bounding functions.

Conflict-Directed Clause Learning (CDCL) is the core algorithm of modern SAT solvers. While designed for Boolean satisfiability (SAT), it shares the high-level 'prune-and-search' philosophy with branch and bound.

• Learning from Failure: When CDCL hits a conflict (a dead-end), it performs clause learning—deriving a new constraint (clause) that explains the conflict and prevents the solver from revisiting the same dead-end. This is analogous to B&B using a bound to prune a region of the search space.
• Search Intelligence: Both algorithms move beyond naive backtracking: B&B uses bounds, CDCL uses learned clauses to guide backtracking intelligently (non-chronological backjumping).