## Definition **Branch and Bound (B&B)** is an exact algorithm framework for combinatorial and integer optimisation problems. It systematically enumerates candidate solutions by *branching* into subproblems, *bounding* their optimal values, and *pruning* subproblems that cannot improve on the best known solution. ## The Algorithm ``` best_solution ← any feasible solution (initialise upper bound) queue ← {original problem} while queue non-empty: P ← pop subproblem from queue lower_bound ← solve relaxation of P if lower_bound ≥ best objective: prune if relaxation solution is feasible for P: if its value < best objective: update best else: branch P into subproblems by adding constraints push subproblems to queue return best_solution ``` (For minimisation. Flip inequalities for maximisation.) ## The Three Operations ### Branching Partition the feasibility region of subproblem $P$ into smaller subproblems. For ILP, branch on a fractional variable $x_j = 2.7$ by adding either $x_j \leq 2$ or $x_j \geq 3$. ### Bounding Compute a bound on the best possible objective value within subproblem $P$. For ILP, the LP relaxation gives a valid lower bound. Tighter bounds prune more aggressively. ### Pruning Discard a subproblem when its bound proves no solution within it can beat the current best. Three reasons to prune: 1. **Infeasibility.** Subproblem has no feasible solutions. 2. **Bound dominance.** Relaxation's bound is worse than best known. 3. **Integer feasibility.** Relaxation solution is already feasible; updates the best, no need to branch further. ## Branching Strategies Choosing *which* fractional variable to branch on matters enormously: - **Most fractional.** Pick the variable furthest from integer. - **Pseudo-cost branching.** Track how much each variable's branching has improved the bound historically. - **Strong branching.** Test branching on each candidate; pick the best. Expensive but effective. - **Reliability branching.** Hybrid of strong and pseudo-cost. ## Node Selection Which subproblem to process next: - **Best-bound (best-first).** Pick the node with the best LP bound. Often finds optima faster. - **Depth-first.** Quickly find feasible solutions for early upper-bound improvement; lower memory footprint. - **Hybrid.** Modern solvers switch strategies dynamically. ## Why B&B Is the Workhorse Modern MILP solvers are essentially sophisticated B&B implementations with: - LP relaxation as bounding (very fast, very tight). - Cutting planes added at each node ([[Branch and Cut]]). - Smart branching variable selection. - Heuristics for finding good upper bounds quickly. - Parallel exploration of subtrees. Combined, they routinely solve problems that pure enumeration would never finish. ## Complexity Worst case: exponential (the entire enumeration tree). Best case: polynomial when pruning is aggressive. In practice, B&B for MILP solves real-world instances with hundreds of thousands of variables in seconds to minutes. ## When B&B Wins - Combinatorial / ILP problems with strong relaxations. - Branch-and-bound for [[Travelling Salesman]] (via Held-Karp bound, branch-and-cut). - Knapsack variants. - Scheduling with bound-providing relaxations. ## When It Struggles - Problems with very weak relaxations (gap between LP optimum and IP optimum is huge). - Symmetric problems (multiple equivalent branches multiply work). - Very large problems with deep optimality requirements. ## Related - [[Branch and Cut]] - [[Integer Linear Programming]] - [[Linear Programming]] - [[Combinatorial Optimization]]