Branch and bound

Branch and Bound (abbr. B&B or BnB) is a general paradigm for designing exact algorithms for solving discrete and combinatorial optimization problems, particularly NP-hard problems. The method is a systematic enumeration strategy in which the entire set of feasible solutions is successively partitioned into subsets (branching), and for each subset, bounds on the objective function's value are calculated (bounding). These bounds make it possible to discard (prune) subsets that are guaranteed not to contain optimal solutions, thereby significantly reducing the search space.

The method was first proposed by A. H. Land and A. G. Doig in 1960 for solving integer programming problems. Since then, it has become one of the most fundamental approaches in operations research and computer science. The key feature of the method is its flexibility: it is not a specific algorithm but a high-level strategic scheme (framework) that can be adapted to the structure of the problem being solved.

Key components of the method

The method is based on three fundamental operations applied to subsets of the solution space, which are organized in the form of a search tree.

• Branching is the process of recursively partitioning the current set of feasible solutions $S_i$ into several smaller, typically non-overlapping subsets $S_{i1},S_{i2},\dots ,S_{ik}$. Each such subset corresponds to a new subproblem and is represented as a child node in the search tree. For example, in integer programming problems, branching is often performed on a variable that has a fractional value in the solution of the LP-relaxation.

• Bounding — for each node of the search tree (i.e., for each subproblem), a bound on the value of the objective function is calculated. For a minimization problem, this is a lower bound, which is a guaranteed underestimation for any solution within that subset. This bound is most often obtained by solving a relaxation of the original subproblem—a simplified version in which some complex constraints (e.g., integrality) are temporarily ignored. The most common type is the LP-relaxation.

• Pruning is the process of eliminating nodes (and their entire corresponding subtrees) from consideration that are guaranteed not to contain an optimal solution. A node is pruned in one of the following cases:

1. Pruning by bound: The lower bound for a given node is no better than (i.e., greater than or equal to, for a minimization problem) the value of the best feasible solution found so far, known as the incumbent.
2. Pruning by feasibility: The solution to the node's relaxation is feasible for the original problem (e.g., all variables are integer-valued). This solution is compared with the current incumbent, and if it is better, the incumbent is updated. No further branching from this node is necessary.
3. Pruning by infeasibility: The subproblem corresponding to the node has no feasible solutions.

General Algorithm

A generalized Branch and Bound algorithm for a minimization problem can be described by the following steps:

1. Initialization: Find an initial feasible solution (e.g., using a heuristic) and set its value as the initial upper bound (incumbent) $U$. Create a queue of active nodes $Q$, containing the root node (the original problem).
2. Main Loop: While the queue $Q$ is not empty:
   • Select a node from $Q$ according to a search strategy (e.g., depth-first or best-first search).
   • Solve the relaxation for this node to obtain a lower bound $L$.
   • Prune the node if $L\ge U$.
   • If the relaxation's solution is feasible for the original problem, update the incumbent: $U\leftarrow L$.
   • If the node is not pruned and its solution is not feasible, perform branching by splitting it into child nodes and add them to the queue $Q$.
3. Termination: When the queue $Q$ becomes empty, the algorithm terminates. The solution corresponding to the incumbent $U$ is globally optimal.

Key properties and theorems

• Correctness and Convergence: The algorithm is guaranteed to find a globally optimal solution in a finite number of steps if the set of feasible solutions is finite and the branching procedure is convergent (i.e., recursive partitioning causes the subsets to "shrink" to single points).
• Search Strategy: The efficiency of the algorithm strongly depends on the strategy for selecting the next node to branch on (e.g., depth-first search, breadth-first search, best-first search) and on the choice of the branching variable. Modern solvers often use hybrid strategies.

Examples

• Integer Programming Problem: A classic application of the method. Linear programming is used as the relaxation. Branching is performed on a fractional variable $x_j$, creating two subproblems with the additional constraints $x_j\le \lfloor x_j^{*}\rfloor$ and $x_j\ge \lceil x_j^{*}\rceil$.
• Traveling Salesman Problem: The solution space consists of all possible Hamiltonian cycles in a graph. Branching can be performed on edges (i.e., including or excluding an edge from the tour). Lower bounds can be obtained by solving simpler problems, such as the assignment problem or constructing a minimum spanning tree.

Related concepts and applications

• Branch-and-Cut: A hybrid method that combines B&B with the cutting-plane method. At each node of the search tree, in addition to solving the relaxation, extra inequalities (cuts) are generated to strengthen the lower bound, leading to more effective pruning of branches.
• Backtracking: Branch and Bound can be seen as a generalization of this algorithm for optimization problems.
• Alpha-beta pruning: A conceptual analogue used in game trees to prune branches that are guaranteed to be losing.

See also

• Integer programming
• Combinatorial optimization
• Traveling salesman problem
• NP-hard problem
• Simplex method