Overview of Branch-and-Bound Method, Algorithms, and Examples of Implementations

Overview of the Branch and Bound Method

The Branch and Bound method is an algorithm designed to efficiently find the optimal solution to problems with vast search spaces, such as combinatorial optimization problems and integer programming problems, while avoiding exhaustive enumeration.

The basic idea of Branch and Bound is founded on two main components: branching and bounding.

In the branching step, the solution space is divided into smaller subproblems. Each subproblem represents a subregion of the original search space. By solving these smaller problems sequentially, the algorithm can systematically explore the overall space.

In the bounding step, each subproblem is evaluated to determine whether it may contain an optimal solution. If a subproblem cannot lead to a better solution than one already found, it is pruned, or discarded, from further consideration. This process, called pruning, helps significantly reduce the overall computation by eliminating unnecessary branches.

In this way, Branch and Bound efficiently narrows down the search space through problem decomposition and elimination of unpromising paths, making it a powerful method for finding optimal solutions.

Branch and Bound is particularly effective in combinatorial optimization, and it has been widely applied to problems such as:

• Integer Linear Programming (ILP): Involves optimizing a linear objective function under the constraint that variables must take integer values. Compared to linear programming with continuous variables, ILP is more complex, and Branch and Bound is a practical approach for solving it.

• Knapsack Problem: Involves selecting items to maximize value without exceeding capacity constraints. As the number of combinations increases exponentially, Branch and Bound helps in reducing the search space efficiently.

• Traveling Salesman Problem (TSP): Aims to find the shortest possible route that visits each city once and returns to the origin. Given the vast number of possible paths, Branch and Bound with pruning is effective in eliminating non-optimal routes early.

• Job Scheduling Problem: Involves assigning multiple jobs to machines efficiently to minimize total completion time or cost. Due to the combinatorial nature of job arrangements, Branch and Bound is useful for reducing the computational burden.

These problems all share the characteristic of having enormous solution spaces, making exhaustive search infeasible. Therefore, Branch and Bound is considered a strong candidate for solving them.

Algorithmic Flow of Branch and Bound

1. Define the Initial State: The original problem is treated as a single root node, serving as the starting point for the search.

2. Bounding (Estimation of Bounds): For each node (subproblem), calculate an upper or lower bound representing the best possible value that could be obtained from that node. If this bound is worse than the current best-known solution, the node is pruned, as it cannot contain the optimal solution.

3. Branching: Promising nodes are expanded into smaller subproblems, which are added to a queue (e.g., a priority queue) for further exploration.

4. Search and Update: Subproblems are taken from the queue, and their solutions are evaluated. If a better solution is found, it becomes the new best solution. This updated best value can be used to prune other subproblems that are unlikely to produce better results.

5. Check for Termination: The process continues until all nodes are either explored or pruned. At this point, the best-known solution is guaranteed to be the global optimum.

Features and Benefits

• Tree-based Decomposition: The problem is mapped into a decision tree structure for exploration.

• Efficient Pruning: Bounding allows large portions of the tree to be discarded early, which leads to faster computations.

• Optimality Guarantee: If the search is thorough, the method guarantees finding the global optimum.

• Heuristic Integration: In practical applications, Branch and Bound is often combined with greedy or local search heuristics to enhance performance.

In summary, the Branch and Bound method is a powerful and efficient approach for solving complex optimization problems by systematically exploring the search space while avoiding unnecessary computations.

Example Algorithm

As a concrete example of the Branch and Bound algorithm, one of the most classic use cases is the 0-1 Knapsack Problem. Below is an explanation of how Branch and Bound can be applied to solve this problem efficiently.

Problem Definition: 0-1 Knapsack Problem

Given:

• A set of n items, each item i has:

  • weight w[i]

  • value v[i]

• A knapsack with a maximum capacity W

Objective:

• Select a subset of items such that the total weight does not exceed W

• Maximize the total value of the selected items

Constraint:

• Each item must be either included (1) or excluded (0) — partial selection is not allowed.

Application of Branch and Bound

① Node Definition

Each node represents a partial solution (i.e., a decision path up to the i-th item).

A node is defined as:

{ level, current_weight, current_value, bound }

• level: Index of the next item to consider

• current_weight: Accumulated weight so far

• current_value: Accumulated value so far

• bound: Estimated upper bound of the maximum value achievable from this node and its descendants

② Bounding Function (Upper Bound Estimation)

To estimate the upper bound of possible value at a given node, a greedy estimation approach can be used.

For example, we calculate the bound by:

• Taking the full values of the next items in order of value-to-weight ratio

• If an item does not fully fit, take the fractional part (as in the fractional knapsack problem) just for the purpose of bounding

This gives an optimistic upper bound on the maximum possible value from that node onward.

def bound(node, W, items):
if node.current_weight >= W:
return 0
result = node.current_value
total_weight = node.current_weight
level = node.levelwhile level < len(items) and total_weight + items[level][0] <= W:
total_weight += items[level][0]
result += items[level][1]
level += 1if level < len(items):
# Partially include the next item (fractional item)
result += (W - total_weight) * (items[level][1] / items[level][0])

return result

③ Pseudo code (overall flow)

from queue import PriorityQueue

def knapsack_branch_and_bound(items, W):
# 品物を価値密度（v/w）で降順にソート
items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)

Node = lambda l, w, v: {'level': l, 'current_weight': w, 'current_value': v, 'bound': 0}

# 初期ノード
root = Node(0, 0, 0)
root['bound'] = bound(root, W, items)

max_value = 0
Q = PriorityQueue()
Q.put((-root['bound'], root)) # PythonのPQは最小値優先なのでマイナスに

while not Q.empty():
_, node = Q.get()

if node['bound'] <= max_value: continue # 枝刈り # 次のレベル（品物）を試す next_level = node['level'] if next_level >= len(items):
continue

weight, value = items[next_level]

# 子ノード1：品物を入れる
if node['current_weight'] + weight <= W: left = Node( next_level + 1, node['current_weight'] + weight, node['current_value'] + value ) left['bound'] = bound(left, W, items) if left['current_value'] > max_value:
max_value = left['current_value']
if left['bound'] > max_value:
Q.put((-left['bound'], left))

# 子ノード2：品物を入れない
right = Node(next_level + 1, node['current_weight'], node['current_value'])
right['bound'] = bound(right, W, items)
if right['bound'] > max_value:
Q.put((-right['bound'], right))

return max_value

Input and Execution Examples

items = [(2, 40), (3.14, 50), (1.98, 100), (5, 95), (3, 30)]  # (weight, price)
W = 10
print(knapsack_branch_and_bound(items, W))
# output example：235.0

Supplement

This method can be adapted to use either depth-first search or best-first search with a priority queue, depending on the desired traversal strategy.

If the value estimation for partial solutions (i.e., the bounding function) is effective, significant pruning can be achieved, leading to faster computation.

It is important to note that the fractional knapsack is used only for upper bound estimation during the bounding step. In the actual selection process, the strict 0-1 knapsack constraint is strictly enforced — no fractional items are included in the final solution.

Application Examples of Branch and Bound

The Branch and Bound (B&B) method is widely used across various fields for solving complex combinatorial optimization problems. Below are three representative applications, with explanations on how branching and bounding (pruning) are used to achieve efficiency and optimality.

1. Traveling Salesman Problem (TSP)

Problem: Find the shortest possible route that visits each city exactly once and returns to the starting city (NP-hard).

How Branch and Bound is used:

• Branching: From the current city, branch to all unvisited cities.

• Bounding:

  • Calculate the partial tour cost + a lower bound estimate for the remaining path (e.g., using minimum edge costs).

  • Prune the branch if the lower bound exceeds the cost of the best known solution.

Characteristics:

• Accurate lower bounds such as the Held-Karp bound significantly improve pruning.

• Although the state space is O(n!), B&B can eliminate a large number of branches early, making optimal solutions feasible in practice for moderate problem sizes.

2. Integer Linear Programming (ILP)

Problem: Solve a linear optimization problem where variables must take integer values:

maximize   cᵀx
subject to Ax ≤ b
x ∈ ℤⁿ

• Branching: If the LP relaxation gives a non-integer solution, branch into two subproblems:
  x[i] ≤ ⌊x[i]⌋ and x[i] ≥ ⌈x[i]⌉.

• Bounding:

  • Use LP relaxation (ignoring integer constraints) to compute an upper bound.

  • If the bound is less than or equal to the best known integer solution, prune the node.

Characteristics:

• Frequently combined with LP solvers (e.g., Simplex method).

• In practice, the Branch & Bound + Cutting Plane method (also called Branch and Cut) is common.

3. Job Scheduling Problem

Problem: Assign a set of jobs to multiple machines to minimize the makespan (the total time to complete all jobs).

How Branch and Bound is used:

• Branching: Assign jobs to machines one by one.

• Bounding:

  • Estimate the earliest possible makespan based on current assignments and remaining job durations.

  • Prune if this estimated makespan is greater than the best known.

Characteristics:

• Very effective for small to medium-sized instances.

• Often combined with accurate heuristics like the LPT rule (Longest Processing Time first) to guide search.

Other Application Areas

References for Understanding Branch and Bound

To deepen your understanding of the Branch and Bound method, here are recommended references, categorized by level and purpose.

[Theoretical Foundations and Algorithms]

(Undergraduate to Graduate Level)

1. The Algorithm Design Manual

2. Operations Research: An Introduction

• Author: Hamdy A. Taha

• Publisher: Pearson

• Overview: A comprehensive textbook covering all aspects of Operations Research, with practical examples of Branch and Bound applied to ILP, Knapsack problems, and more.

• Audience: Engineering graduate students and practitioners.

3. Introduction to Algorithms (a.k.a. CLRS)

• Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein

• Publisher: MIT Press

• Overview: The definitive guide to algorithms, covering search trees and optimization strategies in depth.

• Audience: Readers seeking rigorous theoretical understanding.

[Applications in Integer Programming and Optimization]

(Practice-Oriented)

4. Integer and Combinatorial Optimization

• Authors: Laurence A. Wolsey, George L. Nemhauser

• Publisher: Wiley-Interscience

• Overview: Covers foundational and advanced techniques in optimization, including Branch and Bound, cutting planes, and column generation—core methods behind commercial solvers.

• Audience: OR professionals and researchers.

5. Introduction to Mathematical Optimization

[Practical Implementations and Solver Tutorials]

6. Google OR-Tools Documentation (Free Web Resource)

• Overview: Provides Python implementations of Knapsack, TSP, and scheduling problems using Branch and Bound.

7. SCIP Optimization Suite Documentation

• Overview: Documentation for SCIP, a research-grade ILP solver based on Branch and Bound. Source code is also available for in-depth exploration.

[Classical Paper]

8. “”The Traveling Salesman Problem and Its Variations“