Editing Branch and bound (section)

===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.