Branch and Bound Method

The Principle of "Intelligent Enumeration"

A complete enumeration of all options is impossible for large n. But we can be smarter: if at some step we know that "nothing good will come further," we can cut off an entire branch of the search tree. The Branch and Bound (B&B) method systematizes this idea. This is the foundation of all industrial MILP solvers. When Gurobi “solves” a problem with a million variables, B&B is working inside with many heuristics.

Structure of the Algorithm

Search tree: each node is a subproblem with additional constraints. The root is the original problem without any additional constraints.

Lower bound (LB) for a node: the minimally possible value of the objective function in this node. Usually this is the optimum of the LP relaxation of the subproblem.

Best found solution (incumbent): the best integer solution found so far.

Pruning rule: if LB(node) ≥ incumbent, this node is useless — we prune (cut off) it along with all descendants.

Branch and Bound Algorithm

1. Initialization: the root node = original LP relaxation. incumbent = ∞.

2. Node selection: select an active (non-pruned) node for processing.

3. Computing the lower bound: solve the LP relaxation at this node.

   • If the LP has no solution: prune (the problem is infeasible).
   • If LB ≥ incumbent: prune (not better than the current solution).
   • If the LP optimum is integer: update incumbent.

4. Branching: take a fractional variable $x_i = \alpha$ ($\alpha \notin \mathbb{Z}$). Create two child subproblems:

   • Down branch: add $x_i \leq \lfloor \alpha \rfloor$
   • Up branch: add $x_i \geq \lceil \alpha \rceil$

5. Add child nodes to the queue of active nodes. Repeat from step 2.

Branching Strategies

Choice of variable for branching:

• Most Fractional: select $x_i$ closest to 0.5 (the most “fractional”)
• Strong Branching: solve LP relaxations of both branches for several candidates and select the best. Expensive, but leads to fewer nodes.
• Pseudocost Branching: use the history of previous branchings to predict “usefulness”

Tree traversal strategies:

• Best-First Search: choose the node with the minimum lower bound. Quickly reaches the optimum, but requires a lot of memory.
• Depth-First Search: go deep along one branch. Quickly finds feasible solutions (updates incumbent), saves memory.
• Combination: depth-first until finding an incumbent, then best-first.

Lower Bounds: LP and Lagrangian Relaxation

LP bound: solve the LP relaxation. Good bound, but computationally expensive.

Lagrangian relaxation: “soften” some constraints by adding them to the objective with penalties $\lambda$.

MILP problem: $\min c^\top x$ subject to $Ax \geq b$, $Bx \leq d$, $x \in {0,1}^n$.

Lagrangian subproblem: $L_\lambda(\lambda) = \min_{x \in {0,1}^n,\ Bx \leq d} \left{ c^\top x + \lambda^\top (b - Ax) \right}$.

If $Bx \leq d$ is a “simple” structure (for example, an assignment problem), $L_\lambda(\lambda)$ is easy to solve!

$L_\lambda(\lambda)$ is a lower bound for any $\lambda \geq 0$. The best bound: $\max_{\lambda \geq 0} L_\lambda(\lambda)$ — Lagrangian dual problem, solved by the subgradient method.

Full Analysis: Knapsack Problem via B&B

Task: $W=10$, items $(c,w)$: (6,4), (5,3), (4,2), (3,1).

Root node: LP relaxation. Greedy strategy by $c/w$ ratio: take 4 ($c=3$, $w=1$), 3 ($c=4$, $w=2$), 2 ($c=5$, $w=3$). Remaining 4 kg → take $6/4 = 1.5$ units of item 1: $x_1=1$, $x_2=1$, $x_3=1$, $x_4=1$, value = $3+4+5+6=18$. $LB = 18$ (integer!).

incumbent = 18. The answer is found at the root without branching. Optimum = 18!

(In more complex cases with non-integer LP optimum, one needs to branch.)

Performance in Practice

TSP record: 85,900 cities (USA) solved optimally in 2006 (Applegate, Bixby, Chvátal, Cook). Time: several months on a computer cluster. Used: B&B + cutting planes + powerful heuristics.

Gurobi 10.0: problems with $10^6$ variables and $10^5$ constraints are solved in seconds to minutes (for well-structured problems). Used by: Boeing (scheduling), Google (ad optimization), banks (portfolio management).

Search Heuristics in B&B

Modern MILP solvers (Gurobi, CPLEX) accelerate B&B with dozens of heuristics:

• Variable selection heuristics for branching: pseudocost branching, strong branching, reliability branching
• Node selection heuristics: best-first, depth-first, best-estimate
• Presolve: simplifying the problem before search starts (fixing variables, aggregating constraints)
• Simple heuristics for integer solution search: feasibility pump, RINS, local branching — allow one to quickly find an incumbent for aggressive pruning

Parallelization

B&B parallelizes well: different tree nodes can be processed by independent threads or machines. Industrial solvers support multithreading with hundreds of cores. Challenges: load balancing (some branches are deeper than others), incumbent synchronization (so all threads use the current best solution).

Applications

B&B solves real-world problems of airline scheduling (American Airlines, more than a million variables), delivery network optimization (UPS, FedEx), school timetable creation, portfolio optimization with discrete decisions (number of shares), VLSI design problems.