Branch and bound

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&B algorithm operates according to two principles:

• It recursively splits the search space into smaller spaces, then minimizing f(x) on these smaller spaces; the splitting is called branching.
• Branching alone would amount to 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 "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 of the problem. Denote the set of candidate solutions of an instance I by S_I. The instance representation has to come with three operations:

• branch(I) produces two or more instances that each represent a subset of S_I. (Typically, the subsets are disjoint to prevent the algorithm from visiting the same candidate solution twice, but this is not required. However, an optimal solution among S_I must be contained in at least one of the subsets.[6])
• bound(I) computes a lower bound on the value of any candidate solution in the space represented by I, that is, bound(I) ≤ f(x) for all x in S_I.
• solution(I) determines whether I represents a single candidate solution. (Optionally, if it does not, the operation may choose to return some feasible solution from among S_I.[6]) If solution(I) returns a solution then f(solution(I)) provides an upper bound for the optimal objective value over the whole space of feasible solutions.

Using these operations, a B&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 greater than an upper bound found so far; 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.

// 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;
}

This approach is used for a number of NP-hard problems:

• Integer programming
• Nonlinear programming
• Travelling salesman problem (TSP)[4][11]
• Quadratic assignment problem (QAP)
• Maximum satisfiability problem (MAX-SAT)
• Nearest neighbor search[12] (by Keinosuke Fukunaga)
• Flow shop scheduling
• Cutting stock problem
• Computational phylogenetics
• Set inversion
• Parameter estimation
• 0/1 knapsack problem
• Feature selection in machine learning[13][14]
• Structured prediction in computer vision[15]^:267–276

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.

Nau et al. present a generalization of branch and bound that also subsumes the A*, B* and alpha-beta search algorithms.[16]

• Backtracking
• Branch-and-cut, a hybrid between branch-and-bound and the cutting plane methods that is used extensively for solving integer linear programs.

• LiPS – Free easy-to-use GUI program intended for solving linear, integer and goal programming problems.
• Cbc – (Coin-or branch and cut) is an open-source mixed integer programming solver written in C++.