Optimization by eliminating non optimal solutions to sub-problems
Branch and bound (BB, B&amp;B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores "branches" of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated "bounds" on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.
The method was first proposed by Ailsa Land and Alison Doig whilst carrying out research at the London School of Economics sponsored by British Petroleum in 1960 for discrete programming, and has become the most commonly used tool for solving NP-hard optimization problems. The name "branch and bound" first occurred in the work of Little "et al." on the traveling salesman problem.
Overview.
The goal of a branch-and-bound algorithm is to find a value x that maximizes or minimizes the value of a real-valued function "f"("x"), called an objective function, among some set S of admissible, or candidate solutions. The set S is called the search space, or feasible region. The rest of this section assumes that minimization of "f"("x") is desired; this assumption comes without loss of generality, since one can find the maximum value of "f"("x") by finding the minimum of "g"("x") 
 −"f"("x"). A B&amp;B algorithm operates according to two principles:
Turning these principles into a concrete algorithm for a specific optimization problem requires some kind of data structure that represents sets of candidate solutions. Such a representation is called an "instance" of the problem. Denote the set of candidate solutions of an instance I by SI. The instance representation has to come with three operations:
Using these operations, a B&amp;B algorithm performs a top-down recursive search through the tree of instances formed by the branch operation. Upon visiting an instance I, it checks whether bound("I") is equal or greater than the current upper bound; if so, I may be safely discarded from the search and the recursion stops. This pruning step is usually implemented by maintaining a global variable that records the minimum upper bound seen among all instances examined so far.
Generic version.
The following is the skeleton of a generic branch and bound algorithm for minimizing an arbitrary objective function f. To obtain an actual algorithm from this, one requires a bounding function bound, that computes lower bounds of f on nodes of the search tree, as well as a problem-specific branching rule. As such, the generic algorithm presented here is a higher-order function.
 "f"("xh"). (If no heuristic is available, set B to infinity.) B will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
Several different queue data structures can be used. This FIFO queue-based implementation yields a breadth-first search. A stack (LIFO queue) will yield a depth-first algorithm. A best-first branch and bound algorithm can be obtained by using a priority queue that sorts nodes on their lower bound. Examples of best-first search algorithms with this premise are Dijkstra's algorithm and its descendant A* search. The depth-first variant is recommended when no good heuristic is available for producing an initial solution, because it quickly produces full solutions, and therefore upper bounds.
Pseudocode.
A C++-like pseudocode implementation of the above is:
// C++-like implementation of branch and bound, 
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
 CombinatorialProblem problem, 
 ObjectiveFunction objective_function /*f*/,
 BoundingFunction lower_bound_function /*bound*/) 
 // Step 1 above.
 double problem_upper_bound = std::numeric_limits ;double ;::infinity; // = B
 CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
 problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
 CombinatorialSolution current_optimum = heuristic_solution;
 // Step 2 above
 queue ;CandidateSolutionTree ; candidate_queue;
 // problem-specific queue initialization
 candidate_queue = populate_candidates(problem);
 while (!candidate_queue.empty()) { // Step 3 above
 // Step 3.1
 CandidateSolutionTree node = candidate_queue.pop();
 // "node" represents N above
 if (node.represents_single_candidate()) { // Step 3.2
 if (objective_function(node.candidate()) ; problem_upper_bound) {
 current_optimum = node.candidate();
 problem_upper_bound = objective_function(current_optimum);
 // else, node is a single candidate which is not optimum
 else { // Step 3.3: node represents a branch of candidate solutions
 // "child_branch" represents N_i above
 for (auto&amp;&amp; child_branch : node.candidate_nodes) {
 if (lower_bound_function(child_branch) ;= problem_upper_bound) {
 candidate_queue.enqueue(child_branch); // Step 3.3.2
 // otherwise, bound(N_i) ; B so we prune the branch; step 3.3.1
 return current_optimum;
In the above pseudocode, the functions codice_1 and codice_2 called as subroutines must be provided as applicable to the problem. The functions "f" (codice_3) and bound (codice_4) are treated as function objects as written, and could correspond to lambda expressions, function pointers and other types of callable objects in the C++ programming language.
Improvements.
When formula_1 is a vector of formula_2, branch and bound algorithms can be combined with interval analysis and contractor techniques in order to provide guaranteed enclosures of the global minimum.
Applications.
This approach is used for a number of NP-hard problems:
Branch-and-bound may also be a base of various heuristics. For example, one may wish to stop branching when the gap between the upper and lower bounds becomes smaller than a certain threshold. This is used when the solution is "good enough for practical purposes" and can greatly reduce the computations required. This type of solution is particularly applicable when the cost function used is "noisy" or is the result of statistical estimates and so is not known precisely but rather only known to lie within a range of values with a specific probability.
Relation to other algorithms.
Nau "et al." present a generalization of branch and bound that also subsumes the A*, B* and alpha-beta search algorithms.
Optimization Example.
Branch and bound can be used to solve this problem
Maximize formula_3 with these constraints
formula_4
formula_5
formula_6
formula_7 and formula_8 are integers. 
The first step is to relax the integer constraint. We have two extreme points for the first equation that form a line: formula_9 and formula_10. We can form the second line with the vector points formula_11 and formula_12. 
The third point is formula_13. This is a convex hull region so the solution lies on one of the vertices of the region. We can find the intersection using row reduction, which is formula_14, or formula_15 with a value of 276.667. We test the other endpoints by sweeping the line over the region and find this is the maximum over the reals. 
We choose the variable with the maximum fractional part, in this case formula_8 becomes the parameter for the branch and bound method. We branch to formula_17 and obtain 276 @ formula_18. We have reached an integer solution so we move to the other branch formula_19. We obtain 275.75 [Tag]. We have a decimal so we branch formula_7 to formula_22 and we find 274.571 [Tag]. We try the other branch formula_24 and there are no feasible solutions. Therefore, the maximum is 276 with formula_25 and formula_26.
References.
 ;templatestyles src="Reflist/styles.css" / ;