Editing Branch and bound (section)

==Overview==
The goal of a branch-and-bound algorithm is to find a value {{mvar|x}} that maximizes or minimizes the value of a [[real-valued function]] {{math|''f''(''x'')}}, called an [[Loss function|objective function]], among some set {{mvar|S}} of admissible, or [[candidate solution]]s. The set {{mvar|S}} is called the search space, or [[feasible region]]. The rest of this section assumes that minimization of {{math|''f''(''x'')}} is desired; this assumption comes [[without loss of generality]], since one can find the maximum value of {{math|''f''(''x'')}} by finding the minimum of {{math|''g''(''x'') {{=}} −''f''(''x'')}}. A B&B algorithm operates according to two principles:

* It [[Recursion|recursively]] splits the search space into smaller spaces, then minimizing {{math|''f''(''x'')}} on these smaller spaces; the splitting is called ''branching''.
* Branching alone would amount to [[Brute-force search|brute-force]] enumeration of candidate solutions and testing them all. To improve on the performance of brute-force search, a B&B algorithm keeps track of ''bounds'' on the minimum that it is trying to find, and uses these bounds to "[[pruning (decision trees)|prune]]" the search space, eliminating candidate solutions that it can prove will not contain an optimal solution.

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 (computer science)|instance]]'' of the problem. Denote the set of candidate solutions of an instance {{mvar|I}} by {{mvar|S<sub>I</sub>}}. The instance representation has to come with three operations:

* {{math|branch(''I'')}} produces two or more instances that each represent a subset of {{mvar|S<sub>I</sub>}}. (Typically, the subsets are [[disjoint sets|disjoint]] to prevent the algorithm from visiting the same candidate solution twice, but this is not required. However, an optimal solution among {{mvar|S<sub>I</sub>}} must be contained in at least one of the subsets.<ref name="bader">{{cite encyclopedia |first1=David A. |last1=Bader |first2=William E. |last2=Hart |first3=Cynthia A. |last3=Phillips |author3-link=Cynthia A. Phillips |title=Parallel Algorithm Design for Branch and Bound |editor-first=H. J. |editor-last=Greenberg |encyclopedia=Tutorials on Emerging Methodologies and Applications in Operations Research |publisher=Kluwer Academic Press |year=2004 |url=http://www.cc.gatech.edu/~bader/papers/ParallelBranchBound.pdf |access-date=2015-09-16 |archive-url=https://web.archive.org/web/20170813145917/http://www.cc.gatech.edu/~bader/papers/ParallelBranchBound.pdf |archive-date=2017-08-13 |url-status=dead }}</ref>)
* {{math|bound(''I'')}} computes a lower bound on the value of any candidate solution in the space represented by {{mvar|I}}, that is, {{math|bound(''I'') ≤ ''f''(''x'')}} for all {{mvar|x}} in {{mvar|S<sub>I</sub>}}.
* {{math|solution(''I'')}} determines whether {{mvar|I}} represents a single candidate solution. (Optionally, if it does not, the operation may choose to return some feasible solution from among {{mvar|S<sub>I</sub>}}.{{r|bader}}) If {{math|solution(''I'')}} returns a solution then {{math|''f''(solution(''I''))}} provides an upper bound for the optimal objective value over the whole space of feasible solutions.
<!--(For example, {{mvar|S}} could be the set of all possible trip schedules for a bus fleet, and {{math|''f''(''x'')}} could be the expected revenue for schedule {{mvar|x}}.)-->

Using these operations, a B&B algorithm performs a top-down recursive search through the [[search tree|tree]] of instances formed by the branch operation. Upon visiting an instance {{mvar|I}}, it checks whether {{math|bound(''I'')}} is equal or greater than the current upper bound; if so, {{mvar|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 {{mvar|f}}.<ref name="clausen99">{{cite tech report |first=Jens |last=Clausen |title=Branch and Bound Algorithms—Principles and Examples |year=1999 |publisher=[[University of Copenhagen]] |url=http://www.diku.dk/OLD/undervisning/2003e/datV-optimer/JensClausenNoter.pdf |access-date=2014-08-13 |archive-url=https://web.archive.org/web/20150923214803/http://www.diku.dk/OLD/undervisning/2003e/datV-optimer/JensClausenNoter.pdf |archive-date=2015-09-23 |url-status=dead }}</ref> To obtain an actual algorithm from this, one requires a bounding function {{math|bound}}, that computes lower bounds of {{mvar|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]].

# Using a [[heuristic]], find a solution {{mvar|x<sub>h</sub>}} to the optimization problem. Store its value, {{math|''B'' {{=}} ''f''(''x<sub>h</sub>'')}}. (If no heuristic is available, set {{mvar|B}} to infinity.) {{mvar|B}} will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
# Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
# Loop until the queue is empty:
## Take a [[Node (computer science)|node]] {{mvar|N}} off the queue.
## If {{mvar|N}} represents a single candidate solution {{mvar|x}} and {{math|''f''(''x'') < ''B''}}, then {{mvar|x}} is the best solution so far. Record it and set {{math|''B'' ← ''f''(''x'')}}.
## Else, ''branch'' on {{mvar|N}} to produce new nodes {{mvar|N<sub>i</sub>}}. For each of these:
### If {{math|bound(''N<sub>i</sub>'') > ''B''}}, do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded.
### Else, store {{mvar|N<sub>i</sub>}} on the queue.

Several different [[queue (abstract data type)|queue]] [[Data structure|data structures]] can be used. This [[FIFO (computing and electronics)|FIFO queue]]-based implementation yields a [[breadth-first search]]. A [[Stack (data structure)|stack]] (LIFO queue) will yield a [[depth-first search|depth-first]] algorithm. A [[Best-first search|best-first]] branch and bound algorithm can be obtained by using a [[priority queue]] that sorts nodes on their lower bound.<ref name="clausen99"/> 

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.<ref>{{cite book |last1=Mehlhorn |first1=Kurt |author-link1=Kurt Mehlhorn |first2=Peter |last2=Sanders|author2-link=Peter Sanders (computer scientist) |title=Algorithms and Data Structures: The Basic Toolbox |publisher=Springer |year=2008 |page=249 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/GenericMethods.pdf}}</ref>

==== {{Anchor|Code}}Pseudocode ====
A [[C++]]-like pseudocode implementation of the above is:
<syntaxhighlight lang="c++" line="1">
// 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&& 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;
}
</syntaxhighlight>

In the above pseudocode, the functions <code>heuristic_solve</code> and <code>populate_candidates</code> called as subroutines must be provided as applicable to the problem. The functions {{mvar|''f''}} (<code>objective_function</code>) and {{math|bound}} (<code>lower_bound_function</code>) are treated as [[function object]]s as written, and could correspond to [[anonymous function|lambda expression]]s, [[function pointer]]s and other types of [[callable object]]s in the C++ programming language.

===Improvements===
When <math>\mathbf{x}</math> is a vector of <math>\mathbb{R}^n</math>, branch and bound algorithms can be combined with [[Interval arithmetic|interval analysis]]<ref>{{cite book|last1=Moore|first1=R. E.|
title=Interval Analysis|
year=1966|publisher=Prentice-Hall|
location=Englewood Cliff, New Jersey|isbn=0-13-476853-1}}
</ref> and [[interval contractor|contractor]] techniques in order to provide guaranteed enclosures of the global minimum.<ref>
{{cite book|last1=Jaulin|first1=L.|last2=Kieffer|first2=M.|last3=Didrit|first3=O.|last4=Walter|first4=E.|
title=Applied Interval Analysis|year=2001|publisher=Springer|location=Berlin|isbn=1-85233-219-0}}
</ref><ref>
{{cite book|last=Hansen|first=E.R.|
title=Global Optimization using Interval Analysis|year=1992|
publisher=Marcel Dekker|location=New York}}
</ref>