Branch and Bound: Optimization Problem Solving
Branch and bound (B&B) is an algorithmic paradigm for solving combinatorial optimization problems where you need the provably optimal solution, not just a good one. It's the workhorse behind integer...
Key Insights
- Branch and bound transforms intractable optimization problems into manageable ones by systematically eliminating large portions of the search space through intelligent bounding
- The quality of your bound function determines everything—a tight bound can reduce exponential search to near-polynomial time, while a loose bound offers little improvement over brute force
- Branch and bound excels when you need guaranteed optimal solutions and can derive meaningful bounds; switch to heuristics when you need speed over optimality or can’t compute useful bounds
Introduction to Branch and Bound
Branch and bound (B&B) is an algorithmic paradigm for solving combinatorial optimization problems where you need the provably optimal solution, not just a good one. It’s the workhorse behind integer programming solvers, scheduling systems, and any application where “close enough” isn’t acceptable.
The core insight is simple: instead of examining every possible solution (which is often computationally impossible), we organize the search space as a tree and use mathematical bounds to prove that entire subtrees cannot contain the optimal solution. This lets us prune massive portions of the search space without examining them.
When should you reach for B&B instead of alternatives? Use greedy algorithms when you need speed and can accept approximations. Use dynamic programming when the problem has optimal substructure and overlapping subproblems with manageable state space. Use B&B when you need guaranteed optimality, the search space is too large for exhaustive enumeration, and you can compute meaningful bounds efficiently.
Core Concepts: Branching, Bounding, and Pruning
Branch and bound rests on three operations that work together to explore the solution space efficiently.
Branching divides a problem into smaller subproblems. For a binary decision problem, you might branch on whether to include item 1 or not, creating two child nodes. The branching strategy defines how you decompose the problem—good branching creates balanced subtrees and exposes pruning opportunities early.
Bounding computes estimates of the best solution achievable within a subtree. For minimization problems, you compute lower bounds; for maximization, upper bounds. The bound must be optimistic—it should never underestimate (for max) or overestimate (for min) the true optimal value in that subtree.
Pruning eliminates subtrees that provably cannot contain the optimal solution. If you’re maximizing and a node’s upper bound is worse than your current best solution, that entire subtree is worthless. This is where the exponential savings come from.
from dataclasses import dataclass, field
from typing import Any, Optional
@dataclass
class BBNode:
"""Represents a node in the branch and bound search tree."""
level: int # Depth in the search tree
bound: float # Optimistic bound for this subtree
value: float # Current objective value
solution: list = field(default_factory=list) # Partial solution
is_complete: bool = False # Whether this is a complete solution
def __lt__(self, other: 'BBNode') -> bool:
# For max problems: higher bound = higher priority
return self.bound > other.bound
@dataclass
class BBState:
"""Tracks global state during branch and bound search."""
best_value: float = float('-inf') # Best complete solution found
best_solution: Optional[list] = None
nodes_explored: int = 0
nodes_pruned: int = 0
The Algorithm Step-by-Step
The general B&B framework follows a consistent pattern regardless of the specific problem. You maintain a pool of unexplored nodes, repeatedly select the most promising one, check if it can be pruned, and if not, branch to create children.
Node selection strategy significantly impacts performance:
- Best-first: Always expand the node with the best bound. Finds optimal solution quickly but uses more memory since you keep many nodes alive.
- Depth-first: Explore deeply before backtracking. Uses less memory and finds complete solutions faster, enabling earlier pruning.
- Hybrid: Start depth-first to find a good solution quickly, then switch to best-first.
import heapq
from typing import Callable, TypeVar, Generic
T = TypeVar('T')
def branch_and_bound(
root: BBNode,
branch_fn: Callable[[BBNode], list[BBNode]],
bound_fn: Callable[[BBNode], float],
is_complete_fn: Callable[[BBNode], bool],
get_value_fn: Callable[[BBNode], float],
maximize: bool = True
) -> tuple[float, list, dict]:
"""
Generic branch and bound solver.
Args:
root: Initial node representing the full problem
branch_fn: Creates child nodes from a parent
bound_fn: Computes optimistic bound for a node
is_complete_fn: Checks if node represents complete solution
get_value_fn: Gets objective value for complete solutions
maximize: True for maximization, False for minimization
"""
state = BBState()
if not maximize:
state.best_value = float('inf')
# Priority queue: for max problems, we negate bounds
# Python's heapq is a min-heap
heap = []
root.bound = bound_fn(root)
heapq.heappush(heap, root)
while heap:
node = heapq.heappop(heap)
state.nodes_explored += 1
# Pruning check
if maximize and node.bound <= state.best_value:
state.nodes_pruned += 1
continue
if not maximize and node.bound >= state.best_value:
state.nodes_pruned += 1
continue
# Check if this is a complete solution
if is_complete_fn(node):
value = get_value_fn(node)
if maximize and value > state.best_value:
state.best_value = value
state.best_solution = node.solution.copy()
elif not maximize and value < state.best_value:
state.best_value = value
state.best_solution = node.solution.copy()
continue
# Branch: create children
children = branch_fn(node)
for child in children:
child.bound = bound_fn(child)
# Pre-pruning: don't even add hopeless nodes
if maximize and child.bound > state.best_value:
heapq.heappush(heap, child)
elif not maximize and child.bound < state.best_value:
heapq.heappush(heap, child)
else:
state.nodes_pruned += 1
stats = {
'nodes_explored': state.nodes_explored,
'nodes_pruned': state.nodes_pruned
}
return state.best_value, state.best_solution, stats
Designing Effective Bound Functions
The bound function is the heart of B&B performance. A perfect bound equals the true optimal value in the subtree—but computing that is exactly the hard problem you’re trying to solve. The art is finding bounds that are tight enough to enable pruning but cheap enough to compute.
Relaxation methods are the standard approach:
- LP Relaxation: For integer programs, solve the continuous relaxation. Fast with modern solvers and often tight.
- Constraint dropping: Remove difficult constraints to get an easier problem. The solution to the easier problem bounds the original.
- Lagrangian relaxation: Move constraints into the objective with penalty terms.
For the 0/1 knapsack problem, the fractional relaxation provides an excellent bound:
def knapsack_bound(
items: list[tuple[int, int]], # (value, weight) pairs
capacity: int,
included: list[int], # Indices of items already included
excluded: set[int] # Indices of items excluded
) -> float:
"""
Compute upper bound for knapsack using fractional relaxation.
For remaining items, we can take fractions—this is always >=
the true integer optimum.
"""
current_value = sum(items[i][0] for i in included)
current_weight = sum(items[i][1] for i in included)
if current_weight > capacity:
return float('-inf') # Infeasible
remaining_capacity = capacity - current_weight
# Get remaining items, sorted by value density
remaining = []
decided = set(included) | excluded
for i, (value, weight) in enumerate(items):
if i not in decided and weight > 0:
remaining.append((value / weight, value, weight, i))
remaining.sort(reverse=True) # Highest density first
bound = current_value
for density, value, weight, idx in remaining:
if weight <= remaining_capacity:
bound += value
remaining_capacity -= weight
else:
# Take fraction of this item
bound += density * remaining_capacity
break
return bound
Classic Application: Traveling Salesman Problem
The Traveling Salesman Problem asks for the shortest tour visiting all cities exactly once. B&B works well here because we can compute tight lower bounds using minimum spanning trees.
The key insight: any tour is a spanning structure, so the MST weight (which is the minimum spanning structure) provides a lower bound. We can improve this by considering that each vertex needs exactly two edges in a tour.
import heapq
from typing import Optional
def tsp_branch_and_bound(distances: list[list[float]]) -> tuple[float, list[int]]:
"""
Solve TSP using branch and bound with MST-based lower bounds.
Args:
distances: n x n matrix of distances between cities
Returns:
(tour_length, tour) where tour is list of city indices
"""
n = len(distances)
def mst_cost(nodes: set[int]) -> float:
"""Compute MST cost for a subset of nodes using Prim's algorithm."""
if len(nodes) <= 1:
return 0
nodes_list = list(nodes)
in_mst = {nodes_list[0]}
total = 0
while len(in_mst) < len(nodes):
best_edge = float('inf')
best_node = None
for u in in_mst:
for v in nodes:
if v not in in_mst and distances[u][v] < best_edge:
best_edge = distances[u][v]
best_node = v
if best_node is None:
return float('inf')
in_mst.add(best_node)
total += best_edge
return total
def compute_bound(path: list[int], path_cost: float) -> float:
"""
Lower bound = current path cost + MST of remaining nodes
+ min edges to connect path ends to remaining nodes
"""
if len(path) == n:
return path_cost + distances[path[-1]][path[0]]
remaining = set(range(n)) - set(path)
# MST of remaining nodes
bound = path_cost + mst_cost(remaining)
# Minimum edge from last node in path to remaining
if remaining:
min_out = min(distances[path[-1]][j] for j in remaining)
bound += min_out
# Minimum edge from remaining back to start
min_back = min(distances[j][path[0]] for j in remaining)
bound += min_back
return bound
# State: (bound, path_cost, path)
# Negate bound for min-heap behavior (we want lowest bound first)
initial_bound = compute_bound([0], 0)
heap = [(initial_bound, 0, [0])]
best_tour = None
best_cost = float('inf')
nodes_explored = 0
while heap:
bound, cost, path = heapq.heappop(heap)
nodes_explored += 1
# Prune if bound exceeds best known solution
if bound >= best_cost:
continue
# Complete tour found
if len(path) == n:
tour_cost = cost + distances[path[-1]][path[0]]
if tour_cost < best_cost:
best_cost = tour_cost
best_tour = path + [path[0]]
continue
# Branch: try each unvisited city next
visited = set(path)
for next_city in range(n):
if next_city in visited:
continue
new_path = path + [next_city]
new_cost = cost + distances[path[-1]][next_city]
new_bound = compute_bound(new_path, new_cost)
if new_bound < best_cost:
heapq.heappush(heap, (new_bound, new_cost, new_path))
print(f"Explored {nodes_explored} nodes")
return best_cost, best_tour
Performance Optimization Techniques
Real-world B&B implementations need additional optimizations beyond the basic algorithm:
Variable ordering determines which decision to make first. For knapsack, sorting items by value density and branching on high-density items first tends to find good solutions quickly. For TSP, starting from a hub city with many short edges helps.
Symmetry breaking eliminates equivalent solutions. In TSP, we can fix the starting city without loss of generality—this immediately reduces the search space by a factor of n.
Early termination with incumbent solutions means finding any good complete solution quickly. Running a greedy heuristic before B&B gives you a starting bound that enables pruning from the very first iteration.
def optimized_knapsack_bb(
items: list[tuple[int, int]],
capacity: int
) -> tuple[int, list[int]]:
"""Knapsack with practical optimizations."""
# Optimization 1: Sort by value density for better branching order
indexed_items = [(v, w, i) for i, (v, w) in enumerate(items)]
indexed_items.sort(key=lambda x: x[0]/x[1] if x[1] > 0 else float('inf'),
reverse=True)
# Optimization 2: Greedy solution for initial bound
greedy_value = 0
greedy_weight = 0
greedy_solution = []
for v, w, i in indexed_items:
if greedy_weight + w <= capacity:
greedy_value += v
greedy_weight += w
greedy_solution.append(i)
best_value = greedy_value
best_solution = greedy_solution.copy()
# Optimization 3: Iterative DFS with pruning (memory efficient)
stack = [(0, 0, 0, [])] # (level, value, weight, chosen)
while stack:
level, value, weight, chosen = stack.pop()
if level == len(items):
if value > best_value:
best_value = value
best_solution = chosen.copy()
continue
v, w, original_idx = indexed_items[level]
# Compute bound for this subtree
bound = knapsack_bound(
[(indexed_items[j][0], indexed_items[j][1])
for j in range(len(items))],
capacity,
[j for j in range(level) if j in {indexed_items.index(indexed_items[k])
for k in range(len(chosen))}],
set()
)
if bound <= best_value:
continue
# Branch: exclude item (try first for DFS)
stack.append((level + 1, value, weight, chosen))
# Branch: include item (if feasible)
if weight + w <= capacity:
stack.append((level + 1, value + v, weight + w,
chosen + [original_idx]))
return best_value, best_solution
When to Use (and Avoid) Branch and Bound
Use B&B when:
- You need a provably optimal solution, not an approximation
- The problem has structure that enables computing tight bounds
- The search space, while large, can be effectively pruned
- You can tolerate potentially long runtimes for hard instances
Avoid B&B when:
- Good-enough solutions are acceptable—use metaheuristics like simulated annealing or genetic algorithms
- You can’t compute meaningful bounds—B&B degenerates to exhaustive search
- The problem is small enough for brute force or has polynomial-time algorithms
- You need real-time responses—B&B runtime is unpredictable
For integer programming problems specifically, consider using established solvers like CPLEX, Gurobi, or the open-source CBC. These implement sophisticated B&B with decades of optimizations including cutting planes, presolve techniques, and parallel search. Rolling your own makes sense for learning or when you have problem-specific structure to exploit.
Branch and bound remains one of the most powerful exact optimization techniques available. Master the fundamentals—tight bounds, smart branching, aggressive pruning—and you’ll have a tool that can crack problems that seem computationally hopeless.