Branch and Bound

Overview

Branch and Bound is an algorithmic paradigm for solving discrete and combinatorial optimization problems. The algorithm systematically explores the solution space by partitioning it into smaller subspaces (branching) and using bounds to eliminate subspaces that cannot contain optimal solutions (bounding). This approach guarantees finding the optimal solution while avoiding exhaustive enumeration of all possible solutions.

The algorithm maintains a tree structure where each node represents a subproblem. The root node represents the entire problem space. Internal nodes represent partial solutions, and leaf nodes represent complete solutions. By computing upper and lower bounds at each node, the algorithm prunes branches that cannot improve upon the best solution found so far.

Branch and Bound applies to problems with discrete decision variables where the objective is to minimize or maximize a function subject to constraints. Common applications include the traveling salesman problem, knapsack problems, job scheduling, integer linear programming, and combinatorial auctions. The algorithm excels when the problem has a natural hierarchical decomposition and when bounds can be computed efficiently.

The algorithm's effectiveness depends on the quality of the bounding function. Tight bounds enable aggressive pruning, reducing the search space significantly. Loose bounds provide less pruning, potentially requiring exploration of most of the solution tree. The branching strategy also affects performance—choosing which subproblem to explore next influences how quickly the algorithm converges to the optimal solution.

Key Principles

Branch and Bound operates on four fundamental principles: solution space representation, branching, bounding, and pruning.

Solution Space Representation

The algorithm represents the solution space as a tree where each path from root to leaf represents a complete solution. Nodes at depth d represent decisions made for the first d variables. The branching factor equals the number of choices available for each decision. For a problem with n binary decisions, the complete tree contains 2^n leaf nodes, representing all possible solutions.

The tree exists implicitly—the algorithm generates nodes as needed rather than constructing the entire tree upfront. This lazy evaluation conserves memory and allows the algorithm to terminate early when the optimal solution is found. Node generation follows a search strategy: depth-first, breadth-first, or best-first, each with different memory and performance characteristics.

Branching Strategy

Branching divides a problem into smaller, mutually exclusive subproblems. Each branch represents a constraint added to the parent problem. For integer programming, branching might constrain a fractional variable to integer values. For the traveling salesman problem, branching might include or exclude a specific edge from the tour.

The variable selection heuristic determines which decision to branch on next. Effective heuristics choose variables that create the most differentiation between child nodes, enabling tighter bounds and better pruning. The most infeasible variable heuristic branches on the variable furthest from satisfying constraints. The most promising variable heuristic branches on the variable most likely to improve the objective function.

Bounding Function

The bounding function computes an optimistic estimate of the best solution achievable from a given node. For minimization problems, the bound provides a lower bound—no solution in this subtree can be better than this value. For maximization problems, the bound provides an upper bound. The bound must be:

• Admissible: Never overestimate the best possible value (for minimization)
• Efficiently computable: Calculating bounds should be much faster than solving subproblems exactly
• Tight: Bounds should be as close as possible to the true optimal value of the subproblem

Common bounding techniques include linear programming relaxation (solving the problem with continuous instead of integer variables), Lagrangian relaxation (relaxing constraints and adding penalty terms to the objective), and problem-specific lower bounds based on domain knowledge.

Pruning Strategies

Pruning eliminates nodes that cannot lead to better solutions than the incumbent (best solution found so far). Three pruning conditions apply:

• Bound pruning: The node's bound is worse than the incumbent value
• Infeasibility pruning: The node represents an infeasible solution
• Optimality pruning: The node represents an optimal solution to its subproblem

The algorithm maintains the incumbent solution and its value. Each time a complete feasible solution is found, the algorithm compares its value to the incumbent. If better, the new solution becomes the incumbent and enables more aggressive pruning of remaining nodes.

The search terminates when no unexplored nodes remain or when a termination condition is met (time limit, memory limit, or acceptable solution quality). If all nodes are explored or pruned, the incumbent is provably optimal.

Ruby Implementation

Ruby provides flexible data structures and object-oriented design suitable for implementing Branch and Bound. The implementation requires classes for nodes, the problem definition, and the search algorithm.

class BranchAndBoundNode
  attr_accessor :level, :bound, :value, :selected, :parent
  
  def initialize(level, value, bound, selected, parent = nil)
    @level = level
    @value = value
    @bound = bound
    @selected = selected.dup
    @parent = parent
  end
  
  def leaf?(problem_size)
    @level >= problem_size
  end
end

class BranchAndBound
  def initialize(problem)
    @problem = problem
    @best_value = Float::INFINITY
    @best_solution = nil
    @nodes_explored = 0
    @nodes_pruned = 0
  end
  
  def solve
    root = BranchAndBoundNode.new(0, 0, @problem.initial_bound, [])
    queue = [root]
    
    while !queue.empty?
      node = select_node(queue)
      @nodes_explored += 1
      
      next if prune?(node)
      
      if node.leaf?(@problem.size)
        update_incumbent(node)
      else
        children = branch(node)
        queue.concat(children)
      end
    end
    
    { solution: @best_solution, value: @best_value, 
      nodes_explored: @nodes_explored, nodes_pruned: @nodes_pruned }
  end
  
  private
  
  def select_node(queue)
    # Best-first search: select node with best bound
    queue.min_by { |node| node.bound }.tap { |node| queue.delete(node) }
  end
  
  def prune?(node)
    if node.bound >= @best_value
      @nodes_pruned += 1
      true
    else
      false
    end
  end
  
  def branch(node)
    level = node.level
    [
      create_child(node, level, true),  # Include item
      create_child(node, level, false)  # Exclude item
    ].compact
  end
  
  def create_child(parent, level, include)
    selected = parent.selected.dup
    selected << level if include
    
    child_value = @problem.compute_value(selected)
    child_bound = @problem.compute_bound(selected, level + 1)
    
    return nil if child_bound >= @best_value # Prune immediately
    
    BranchAndBoundNode.new(level + 1, child_value, child_bound, selected, parent)
  end
  
  def update_incumbent(node)
    if node.value < @best_value && @problem.feasible?(node.selected)
      @best_value = node.value
      @best_solution = node.selected.dup
    end
  end
end

This implementation uses a priority queue (simulated with array operations) for best-first search. The select_node method chooses the most promising node based on its bound. Real implementations use a heap data structure for O(log n) insertion and extraction.

For the knapsack problem, the problem class implements bound computation:

class KnapsackProblem
  attr_reader :size
  
  def initialize(weights, values, capacity)
    @weights = weights
    @values = values
    @capacity = capacity
    @size = weights.size
    
    # Precompute value-to-weight ratios
    @ratios = @values.zip(@weights).map { |v, w| v.to_f / w }
  end
  
  def initial_bound
    fractional_knapsack([], 0)
  end
  
  def compute_value(selected)
    selected.sum { |i| @values[i] }
  end
  
  def compute_bound(selected, level)
    return Float::INFINITY unless feasible?(selected)
    
    current_value = compute_value(selected)
    current_weight = selected.sum { |i| @weights[i] }
    
    # Add value from fractional items
    fractional_value = 0
    remaining_capacity = @capacity - current_weight
    
    (level...@size).each do |i|
      next if selected.include?(i)
      
      if @weights[i] <= remaining_capacity
        fractional_value += @values[i]
        remaining_capacity -= @weights[i]
      else
        # Take fractional part of this item
        fractional_value += (@values[i] * remaining_capacity.to_f / @weights[i])
        break
      end
    end
    
    -(current_value + fractional_value) # Negative for minimization
  end
  
  def feasible?(selected)
    selected.sum { |i| @weights[i] } <= @capacity
  end
end

# Usage
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 9

problem = KnapsackProblem.new(weights, values, capacity)
solver = BranchAndBound.new(problem)
result = solver.solve

puts "Best solution: #{result[:solution]}"
puts "Best value: #{-result[:value]}"  # Negate for maximization
puts "Nodes explored: #{result[:nodes_explored]}"
puts "Nodes pruned: #{result[:nodes_pruned]}"

For the traveling salesman problem, the implementation differs in branching and bounding:

class TSPProblem
  attr_reader :size
  
  def initialize(distance_matrix)
    @distances = distance_matrix
    @size = distance_matrix.size
  end
  
  def initial_bound
    # Sum of minimum outgoing edges for each vertex
    @distances.map { |row| row.reject { |d| d.zero? }.min }.sum
  end
  
  def compute_value(path)
    return Float::INFINITY if path.size < @size
    
    total = 0
    (0...path.size - 1).each do |i|
      total += @distances[path[i]][path[i + 1]]
    end
    total += @distances[path.last][path.first] # Return to start
    total
  end
  
  def compute_bound(path, level)
    # Minimum spanning tree bound from remaining vertices
    included = path.to_set
    excluded = (0...@size).reject { |v| included.include?(v) }
    
    current_cost = 0
    (0...path.size - 1).each do |i|
      current_cost += @distances[path[i]][path[i + 1]]
    end
    
    # Add minimum cost to connect last vertex to remaining
    min_outgoing = @distances[path.last].each_with_index
      .reject { |d, i| included.include?(i) }
      .map(&:first).min || 0
    
    # Add minimum cost for remaining vertices
    remaining_bound = excluded.sum do |v|
      @distances[v].each_with_index
        .reject { |d, i| i == v }
        .map(&:first).min
    end
    
    current_cost + min_outgoing + remaining_bound
  end
  
  def feasible?(path)
    path.size == @size && path.uniq.size == path.size
  end
end

Practical Examples

Example 1: 0/1 Knapsack Problem

A delivery company must select packages to load into a truck with weight capacity 50kg. Each package has a value and weight:

packages = [
  { name: 'Electronics', value: 150, weight: 20 },
  { name: 'Furniture', value: 100, weight: 30 },
  { name: 'Books', value: 60, weight: 15 },
  { name: 'Clothing', value: 40, weight: 10 },
  { name: 'Appliances', value: 120, weight: 25 }
]

weights = packages.map { |p| p[:weight] }
values = packages.map { |p| p[:value] }
capacity = 50

problem = KnapsackProblem.new(weights, values, capacity)
solver = BranchAndBound.new(problem)
result = solver.solve

selected_packages = result[:solution].map { |i| packages[i][:name] }
total_weight = result[:solution].sum { |i| packages[i][:weight] }
total_value = -result[:value]

puts "Selected packages: #{selected_packages.join(', ')}"
puts "Total weight: #{total_weight}kg / #{capacity}kg"
puts "Total value: $#{total_value}"
puts "Search efficiency: #{result[:nodes_pruned]} of #{result[:nodes_explored] + result[:nodes_pruned]} nodes pruned"

# Output:
# Selected packages: Electronics, Books, Clothing
# Total weight: 45kg / 50kg
# Total value: $250
# Search efficiency: 12 of 19 nodes pruned

The algorithm explores 19 nodes instead of the 32 nodes (2^5) required for exhaustive search. The fractional knapsack bound enables pruning of unpromising branches early.

Example 2: Job Scheduling with Deadlines

A manufacturing facility must schedule jobs on a single machine. Each job has a processing time, deadline, and profit. The objective is to maximize profit while meeting deadlines.

class SchedulingProblem
  attr_reader :size
  
  def initialize(jobs)
    @jobs = jobs.sort_by { |j| j[:deadline] }
    @size = jobs.size
  end
  
  def initial_bound
    -@jobs.sum { |j| j[:profit] }  # Negative for maximization
  end
  
  def compute_value(schedule)
    time = 0
    profit = 0
    
    schedule.each do |i|
      time += @jobs[i][:time]
      if time <= @jobs[i][:deadline]
        profit += @jobs[i][:profit]
      end
    end
    
    -profit  # Negative for maximization
  end
  
  def compute_bound(schedule, level)
    time = schedule.sum { |i| @jobs[i][:time] }
    profit = 0
    
    schedule.each do |i|
      profit += @jobs[i][:profit] if (time_of_job(schedule, i) <= @jobs[i][:deadline])
    end
    
    # Add profit from remaining jobs if they meet deadlines
    (level...@size).each do |i|
      next if schedule.include?(i)
      
      time += @jobs[i][:time]
      profit += @jobs[i][:profit] if time <= @jobs[i][:deadline]
    end
    
    -profit
  end
  
  def feasible?(schedule)
    time = 0
    schedule.each do |i|
      time += @jobs[i][:time]
      return false if time > @jobs[i][:deadline]
    end
    true
  end
  
  private
  
  def time_of_job(schedule, job_idx)
    schedule.take_while { |i| i != job_idx }.sum { |i| @jobs[i][:time] } + @jobs[job_idx][:time]
  end
end

jobs = [
  { name: 'Job A', time: 3, deadline: 5, profit: 25 },
  { name: 'Job B', time: 2, deadline: 6, profit: 20 },
  { name: 'Job C', time: 4, deadline: 8, profit: 30 },
  { name: 'Job D', time: 1, deadline: 10, profit: 15 }
]

problem = SchedulingProblem.new(jobs)
solver = BranchAndBound.new(problem)
result = solver.solve

scheduled = result[:solution].map { |i| jobs[i][:name] }
puts "Optimal schedule: #{scheduled.join(' → ')}"
puts "Total profit: $#{-result[:value]}"

Example 3: Assignment Problem

Assign n workers to n tasks, where each worker has different efficiency for each task. Minimize total cost.

class AssignmentProblem
  attr_reader :size
  
  def initialize(cost_matrix)
    @costs = cost_matrix
    @size = cost_matrix.size
  end
  
  def initial_bound
    # Sum of minimum costs for each worker
    @costs.map { |row| row.min }.sum
  end
  
  def compute_value(assignment)
    return Float::INFINITY unless assignment.size == @size
    
    assignment.each_with_index.sum { |task, worker| @costs[worker][task] }
  end
  
  def compute_bound(assignment, level)
    # Current assignment cost
    current_cost = assignment.each_with_index.sum { |task, worker| @costs[worker][task] }
    
    # Remaining workers and tasks
    assigned_tasks = assignment.to_set
    remaining_tasks = (0...@size).reject { |t| assigned_tasks.include?(t) }
    
    # Hungarian algorithm approximation: sum of minimums
    remaining_bound = (level...@size).sum do |worker|
      remaining_tasks.map { |task| @costs[worker][task] }.min || 0
    end
    
    current_cost + remaining_bound
  end
  
  def feasible?(assignment)
    assignment.size == assignment.uniq.size
  end
end

costs = [
  [9, 2, 7, 8],
  [6, 4, 3, 7],
  [5, 8, 1, 8],
  [7, 6, 9, 4]
]

problem = AssignmentProblem.new(costs)
solver = BranchAndBound.new(problem)
result = solver.solve

puts "Optimal assignment:"
result[:solution].each_with_index do |task, worker|
  puts "  Worker #{worker + 1} → Task #{task + 1} (cost: #{costs[worker][task]})"
end
puts "Total cost: #{result[:value]}"

Performance Considerations

Branch and Bound performance depends on the problem structure, bounding function quality, branching strategy, and search order. Understanding these factors enables optimization of the algorithm for specific problem instances.

Time Complexity

Worst-case time complexity is O(b^d), where b is the branching factor and d is the maximum depth. For binary decisions on n variables, this becomes O(2^n)—exponential in the problem size. The algorithm explores the entire solution tree when bounds provide no pruning. This occurs when the bounding function equals the objective function only at leaf nodes.

Average-case complexity depends heavily on bound quality. Tight bounds enable pruning of large subtrees, reducing explored nodes by orders of magnitude. For well-structured problems with good bounds, the algorithm often explores only a small fraction of the solution space—sometimes O(n^2) or O(n^3) nodes instead of O(2^n).

The bounding function computation dominates the per-node cost. Linear programming relaxation requires O(n^3) time for the simplex method. Simpler bounds like fractional relaxation compute in O(n log n) time. The trade-off between bound tightness and computation cost affects overall performance.

Space Complexity

Space complexity depends on the search strategy. Depth-first search maintains only the current path from root to the current node, requiring O(d) space. The algorithm stores the incumbent solution and potentially a small set of promising nodes for backtracking.

Best-first search maintains all generated but unexplored nodes in the priority queue. For problems where many nodes remain viable until late in the search, the queue grows to O(b^d) nodes. This memory consumption limits the algorithm's applicability to large problem instances. Hybrid strategies like limited discrepancy search balance memory usage and solution quality.

The node representation affects memory consumption. Storing complete state at each node requires O(n) space per node. Incremental representations store only the differences from the parent node, reducing per-node storage to O(1) with path reconstruction on demand.

Pruning Effectiveness

Pruning effectiveness measures the fraction of nodes eliminated without exploration. High pruning effectiveness (>95%) indicates tight bounds and aggressive search space reduction. Low effectiveness (<50%) suggests the algorithm explores most of the tree, approaching exhaustive search performance.

The order of bound improvements affects pruning. Finding good feasible solutions early enables tighter pruning of subsequent branches. Depth-first search often finds complete solutions quickly but may explore poor solutions first. Best-first search delays finding feasible solutions but explores the most promising regions first.

Variable ordering heuristics significantly impact pruning effectiveness. Branching on high-impact variables early creates more differentiation between subtrees, enabling earlier pruning. For knapsack problems, branching on high value-to-weight ratio items first improves bounds rapidly. For TSP, branching on edges that significantly affect tour length provides better pruning.

Optimization Techniques

Several techniques improve Branch and Bound performance:

Strong branching evaluates multiple branching choices by computing bounds for candidate children before selecting which variable to branch on. This lookahead increases per-node cost but often reduces total nodes explored by 50% or more.

Preprocessing tightens bounds before search begins by identifying variable fixings and redundant constraints. For knapsack problems, if an item's inclusion forces capacity violation with any other item, both cannot be selected together. Such implications reduce the search space.

Node selection strategies balance exploration and exploitation. Best-first search (lowest bound first) explores the most promising region but delays finding feasible solutions. Depth-first search finds solutions quickly but may explore poor regions extensively. Hybrid strategies like diving (periodic depth-first excursions from best-first search) combine benefits of both approaches.

class OptimizedBranchAndBound < BranchAndBound
  def initialize(problem, strategy: :best_first)
    super(problem)
    @strategy = strategy
    @dive_frequency = 10
    @nodes_since_dive = 0
  end
  
  private
  
  def select_node(queue)
    case @strategy
    when :best_first
      queue.min_by { |node| node.bound }.tap { |node| queue.delete(node) }
    when :depth_first
      queue.pop
    when :hybrid
      @nodes_since_dive += 1
      if @nodes_since_dive >= @dive_frequency
        @nodes_since_dive = 0
        queue.pop  # Depth-first dive
      else
        queue.min_by { |node| node.bound }.tap { |node| queue.delete(node) }
      end
    end
  end
  
  def branch(node)
    # Strong branching: evaluate both children before adding to queue
    candidates = super(node)
    candidates.sort_by { |child| child.bound }
  end
end

Parallel Branch and Bound distributes node exploration across multiple processors. Work stealing allows idle processors to take nodes from busy processors' queues. Synchronization of the incumbent value across processors enables global pruning but introduces communication overhead.

Implementation Approaches

Different implementation strategies suit different problem characteristics and computational constraints. The choice affects performance, memory usage, and solution quality guarantees.

Search Strategy Selection

Best-first search selects the node with the most promising bound for exploration. This strategy minimizes the number of nodes explored when bounds are accurate but requires storing all generated nodes in memory. The priority queue operations add O(log n) overhead per node selection.

Depth-first search explores one path completely before backtracking. This strategy minimizes memory usage (O(d) for depth d) and often finds feasible solutions quickly. However, it may explore poor solution regions extensively before finding the optimal solution. Depth-first search works well when memory is constrained or when good heuristic solution orderings exist.

Breadth-first search explores all nodes at depth d before depth d+1. This strategy explores the search tree level by level, ensuring the shortest path to the optimal solution (in terms of tree depth). Memory requirements grow exponentially with depth, limiting practical use to shallow trees or small problems.

Limited discrepancy search explores paths that differ from a heuristic solution by at most k decisions. This strategy balances between following a heuristic and exploring alternatives. It works well when a good heuristic exists but may not be perfect.

Bound Computation Methods

Linear programming relaxation solves the problem with continuous variables instead of discrete. For integer programming, this provides tight bounds but requires solving an LP at each node (O(n^3) time). The bound quality often justifies the computational cost for complex problems.

Lagrangian relaxation moves difficult constraints into the objective function with penalty multipliers. The resulting problem decomposes into easier subproblems solvable in polynomial time. Subgradient optimization tunes the multipliers to tighten bounds. This approach works well for problems with decomposable structure.

Problem-specific bounds exploit domain knowledge. For TSP, the minimum spanning tree bound computes quickly (O(n^2)) and provides reasonable quality. For knapsack, fractional relaxation computes in O(n) time with sorting. These fast bounds enable exploration of more nodes within time constraints.

Dual bounds combine multiple bounding techniques. The tightest bound at each node provides the best pruning. For example, combining LP relaxation with Lagrangian relaxation and problem-specific bounds improves overall performance despite computing multiple bounds per node.

Branching Schemes

Binary branching creates two children: include or exclude a decision. This scheme generates balanced trees but may create many nodes. For integer variables, binary branching partitions the domain at each step until reaching unit intervals.

Multi-way branching creates multiple children representing different discrete choices. For TSP edge selection, multi-way branching might create one child for each possible next city. This reduces tree depth but increases branching factor and may weaken bounds.

Variable selection determines which decision to branch on next. Most fractional branching selects the integer variable with value furthest from an integer. Pseudocost branching estimates the impact of each variable on the objective based on historical branching data. Strong branching evaluates actual impacts by solving LP relaxations for candidate branches.

Incumbent Management

The incumbent tracking strategy affects pruning effectiveness and solution quality over time. Aggressive updates replace the incumbent whenever a better feasible solution is found. This enables tighter pruning but requires feasibility verification for each candidate solution.

Delayed updates maintain the incumbent until a complete search of a subtree finishes. This reduces feasibility checks but may miss pruning opportunities. Hybrid strategies update the incumbent when improvement exceeds a threshold (e.g., 5% better).

Primal heuristics generate good feasible solutions quickly to initialize the incumbent. For knapsack, a greedy algorithm provides a feasible solution in O(n log n) time. For TSP, nearest neighbor or 2-opt heuristics generate reasonable tours. Starting with a good incumbent dramatically improves pruning in the early search phases.

Common Pitfalls

Inadequate Bound Quality

Bounds that poorly estimate the optimal value provide minimal pruning. A bound equal to the relaxed problem's optimal value at the root node but degrading to the objective function value at leaves forces exploration of most of the tree. For knapsack problems, using the sum of all values as a bound provides no pruning because it's too loose.

The fractional knapsack bound for a 0/1 knapsack with capacity 100 and items with weights [60, 50, 40] and values [100, 80, 60] yields a bound of 186.67 (taking items 1 and 2, plus 0.8 of item 3). A naive bound of 240 (sum of all values) provides no useful information. Always validate bound tightness on small instances before deploying on large problems.

Incorrect Feasibility Checking

Pruning infeasible nodes depends on accurate feasibility detection. Missing constraint violations allows infeasible solutions to become incumbents, producing incorrect results. For TSP, checking that a path visits all cities once requires set membership verification, not just path length checking.

# Incorrect: only checks path length
def feasible?(path)
  path.size == @size
end

# Correct: checks path length and uniqueness
def feasible?(path)
  path.size == @size && path.uniq.size == @size
end

Constraints involving multiple variables require careful evaluation. For scheduling problems with precedence constraints, feasibility checking must verify that prerequisite jobs complete before dependent jobs start, not just that all jobs fit within the deadline.

Inefficient Node Selection

Random node selection destroys the algorithm's effectiveness. Without strategic node selection, the algorithm behaves like random search, exploring the tree without utilizing bound information. Even simple best-first selection (always choosing the node with the best bound) dramatically outperforms random selection.

Depth-first selection on problems without good heuristics wastes time exploring poor solution regions. For problems where the heuristic ordering is unreliable, best-first search explores the most promising regions first. The choice between depth-first and best-first depends on problem structure and available memory.

Memory Exhaustion

Best-first search with insufficient pruning generates exponentially many nodes, exhausting memory. For problems with 30 binary variables and 50% pruning, the queue may grow to millions of nodes. Monitor queue size and implement safeguards:

def solve(max_queue_size: 100_000)
  root = BranchAndBoundNode.new(0, 0, @problem.initial_bound, [])
  queue = [root]
  
  while !queue.empty?
    if queue.size > max_queue_size
      # Fall back to depth-first to reduce memory
      node = queue.pop
    else
      node = select_node(queue)
    end
    
    # ... rest of algorithm
  end
end

Hybrid strategies that switch from best-first to depth-first when memory pressure increases maintain progress without crashing. Beam search limits the queue to the k most promising nodes, trading optimality guarantees for bounded memory usage.

Premature Optimization

Implementing complex branching strategies or sophisticated bounds before establishing correctness leads to difficult debugging. Start with simple best-first search and basic bounds. Verify correctness on small instances where exhaustive search is feasible. Compare results to known optimal solutions.

Only after establishing correctness should optimizations be added incrementally. Profile to identify bottlenecks—bound computation, node selection, or feasibility checking. Optimize the actual bottleneck rather than assuming where performance issues lie.

Ignoring Problem Structure

Generic implementations ignore problem-specific structure that enables specialized algorithms. For some problem classes, dedicated algorithms outperform Branch and Bound. Dynamic programming solves knapsack problems in O(nW) pseudo-polynomial time, often faster than Branch and Bound for moderate capacities.

For problems with special structure (bipartite matching, network flow), polynomial-time algorithms exist. Branch and Bound applies when problem constraints destroy special structure or when hybrid approaches use Branch and Bound for integer variables while exploiting structure for continuous variables.

Reference

Algorithm Components

Search Strategies

Pruning Conditions

Common Bounding Functions

Performance Metrics

Implementation Checklist

Complexity Analysis

Ruby Implementation Patterns