Branch & Bound

Branch and bound is an exact optimization framework for problems whose candidate set is too large to enumerate directly. It still reasons about every candidate, but groups candidates into regions. A branch partitions one region into smaller regions; a bound proves how good any solution in a region could possibly be; and the best feasible solution found so far—the incumbent—sets the threshold that a region must beat to remain relevant.

The crucial distinction from a heuristic is not that branch and bound is always fast. In the worst case it explores an exponential tree. Its distinction is epistemic: if the search terminates normally, the discarded regions and the surviving incumbent form a proof that no better feasible solution exists. If it stops early, the incumbent and the frontier bounds quantify what remains unknown.

The framework originated in Land and Doig's method for discrete programming, but the same logic appears in integer programming, scheduling, routing, assignment, knapsack, and many custom combinatorial optimizers.

The bound–incumbent invariant #

Consider a minimization problem

$$z^* = \min_{x\in F} f(x),$$

where $F$ is the feasible set. A search node represents a region $R$ of the original candidate space. Its lower bound $B(R)$ must satisfy

$$B(R) \le \min_{x\in F\cap R} f(x).$$

The inequality is deliberately optimistic: the bound may claim that a region can do better than it really can, but it must never claim that the region is worse than its actual best solution. An incumbent $\hat{x}\in F$ supplies an upper bound

$$U=f(\hat{x}) \quad\text{and therefore}\quad z^*\le U.$$

If $B(R)\ge U$, no point in $R$ can improve the incumbent, so the entire node is safe to prune. If all still-possible solutions are covered by frontier regions $\mathcal{O}$, their best bound

$$L=\min_{R\in\mathcal{O}} B(R)$$

gives the global certificate

$$L\le z^*\le U.$$

The two inequalities are the central algorithm invariant. Every branch, prune, propagation step, and numerical shortcut must preserve them.

For maximization, all directions reverse:

Confusing these directions is one of the most destructive implementation errors: an invalid prune can remove the true optimum while leaving a plausible-looking answer.

The generic algorithm #

For minimization, a solver can be organized around the following skeleton. The callbacks hide problem-specific work: constructing a relaxation, extracting a feasible solution, deciding whether a node is solved, and partitioning a node.

def branch_and_bound(root):
    incumbent = None
    incumbent_value = float("inf")
    frontier = [root]

    while frontier:
        region = select_node(frontier)
        relaxation = solve_relaxation(region)

        if relaxation.proves_infeasible:
            continue

        lower_bound = relaxation.objective_bound
        if lower_bound >= incumbent_value:
            continue

        candidate = make_feasible(region, relaxation)
        if candidate is not None and objective(candidate) < incumbent_value:
            incumbent = candidate
            incumbent_value = objective(candidate)

        if relaxation.proves_region_solved:
            continue

        children = branch(region, relaxation)
        frontier.extend(children)

    return incumbent

Three pruning certificates are common:

1. Infeasibility: the region contains no feasible solution.
2. Bound dominance: even the region's optimistic bound cannot improve the incumbent.
3. Solved node: the relaxation has produced and certified the best feasible solution in that region—for example, an integral optimum of a linear relaxation.

A valid branch must cover the parent's feasible candidates. Usually the children are disjoint as well, which avoids duplicate work, but coverage is the condition needed for correctness. It must also make progress. For an integer variable with fractional relaxation value $x_i^*$, the standard split

$$x_i\le\lfloor x_i^*\rfloor \qquad\text{or}\qquad x_i\ge\lceil x_i^*\rceil$$

excludes the current fractional point while covering every integer value. SCIP's branching interface explicitly requires children to be proper restrictions; otherwise an implementation can generate an infinite path that repeats the same subproblem.

Why the algorithm is correct #

Suppose the root covers $F$, every branch covers its parent's feasible set, every bound is valid, and the search tree is finite. At any time, each original feasible point is in one of three places:

• represented by an open or active node;
• inside a node whose feasible candidates have already been solved; or
• inside a pruned node whose certificate proves that it cannot beat the incumbent.

This is the coverage invariant. When the frontier becomes empty, assume for contradiction that some feasible $x$ is better than the returned incumbent. Follow any covering branch path containing $x$. That path could not end at an infeasible node, because $x$ is feasible; it could not be pruned by a valid bound, because its region contains a solution better than the incumbent; and if it ended at a solved node, that node would have produced a solution at least as good as $x$. Every possible ending contradicts the assumption. The incumbent is therefore optimal.

For real solvers, “finite tree” includes termination of each relaxation and progress of each branch. If tolerances, unbounded variables, or repeated domains can create an infinite descending process, partial correctness alone does not establish termination.

Worked example: 0/1 knapsack #

Take a knapsack of capacity 6 and three indivisible items:

The problem maximizes total value. Its fractional relaxation allows part of an item, so greedily filling by value-to-weight ratio gives a valid upper bound. At the root, take A and B, then one quarter of C: the bound is

$$40+50+\frac{1}{4}(65)=106.25.$$

The feasible set $\{A,B\}$ has value 90, so 90 becomes the incumbent lower bound. Item C is fractional in the relaxation, so branch on $C\in\{0,1\}$.

At node 1, C consumes weight 4 and A exactly fills the remaining capacity, so both the fractional bound and an integer solution equal 105. At node 2, the best possible fractional value is only 90. The two children cover both possible values of C, so their certificates establish that A+C is globally optimal without enumerating all eight subsets.

This small trace exposes the whole mechanism: a relaxation supplies optimism, a heuristic or integral relaxation supplies a feasible incumbent, and their meeting closes the proof gap.

Designing a useful bound #

A common way to obtain a bound is to relax constraints. In minimization, enlarging the feasible set can only lower or preserve the optimum; in maximization, it can only raise or preserve it. Examples include:

• replacing $x_i\in\{0,1\}$ with $0\le x_i\le1$;
• dropping a difficult constraint and pricing its violation with a Lagrangian multiplier;
• solving a simpler assignment, flow, or matching problem beneath a harder routing or scheduling problem;
• summing independent per-component lower bounds after ignoring conflicts between components.

A relaxation has two competing costs. A weak bound is cheap but leaves many nodes alive. A strong bound is expensive but may eliminate most of the tree. The right metric is end-to-end search work, not bound tightness or per-node speed alone.

Validity comes before strength. A bound derived from a heuristic estimate is unsafe unless its admissible direction has been proved. Rounding a floating-point relaxation objective in the wrong direction, omitting a negative cost, or applying a bound outside the assumptions under which it was derived can silently invalidate the result.

Bounds can often be tightened without branching. Constraint propagation narrows variable domains; cutting planes add inequalities that every feasible integer solution satisfies; symmetry breaking chooses one representative from equivalent solutions. Each technique is safe only when it preserves every feasible solution relevant to the stated optimization problem.

Branching and node selection #

Branching determines the shape of the proof tree. Node selection determines which part of that tree is explored next. They change performance and the timing of certificates, but not the optimum when all rules are valid.

The distinction explains a common puzzle: a solver can find the final optimal solution early and still run for a long time. Finding an incumbent answers “how good is this feasible solution?” Proving optimality requires raising the global lower bound for minimization—or lowering the global upper bound for maximization—until no open region can do better. SCIP's node-selector documentation makes that tradeoff explicit, while its strong-branching implementation evaluates tentative child relaxations to estimate dual-bound improvement.

Gaps and early stopping #

For minimization with finite incumbent $U$ and global lower bound $L$, the absolute optimality gap is

$$g_{\mathrm{abs}}=U-L\ge0.$$

Stopping when $U-L\le\varepsilon$ certifies that the returned solution is at most $\varepsilon$ objective units worse than the unknown optimum. For maximization, use frontier upper bound minus incumbent lower bound.

A relative gap divides by a scale based on $U$, $L$, or both. Solvers use different denominators and special handling around zero, opposite signs, and infinite bounds. Therefore “1% gap” is not a portable statement unless the convention is named. An absolute gap is unambiguous if objective units are meaningful.

No incumbent means there is not yet a finite feasible upper bound for minimization. A strong frontier bound alone cannot produce a usable optimality gap. Conversely, an excellent incumbent without a competitive global bound may be optimal in fact but remains unproved.

At a resource limit, an exact branch-and-bound solver can legitimately report:

• the best feasible incumbent, if one exists;
• the best global bound;
• the resulting gap under a declared convention; and
• a status such as time limit or node limit.

It must not report “optimal” unless the gap is closed to the solver's stated tolerance and all proof obligations remain valid.

Relationship to neighboring methods #

Backtracking search prunes when a partial assignment cannot be extended to any feasible complete assignment. Branch and bound adds an objective comparison: a partial region may contain feasible completions yet still be discarded because none can improve the incumbent. In practice, one solver often uses both feasibility propagation and objective bounds.

Heuristics and approximation algorithms play two roles. A heuristic can quickly provide a strong incumbent, accelerating an exact search, but the heuristic value is not itself a proof. An approximation algorithm may give an independent quality guarantee without exploring a proof tree. Branch and bound instead derives its guarantee from exhaustive coverage plus valid region bounds.

Dynamic programming merges subproblems with identical sufficient state; branch and bound usually retains a search tree of regions and discards nodes by inequalities. They can be combined when repeated states occur. The worst-case exponential behavior is unsurprising for many problems connected to NP-completeness: exactness does not remove the underlying combinatorial difficulty.

Failure modes and diagnostic questions #

Parallel search adds another distinction. A worker using a stale incumbent may merely miss pruning opportunities; that is inefficient but safe. A worker using an invalid or overly aggressive bound can prune the optimum; that is incorrect. Shared state should therefore treat incumbents as monotone performance information and proof bounds as correctness-critical data.

A compact implementation checklist #

Before trusting a branch-and-bound implementation, answer each question explicitly:

1. What exact candidate region does every node represent?
2. Do the children cover every feasible candidate in the parent, and does each child make progress?
3. In which direction is every bound valid, and under which assumptions?
4. Is the incumbent always a genuinely feasible solution to the original problem?
5. Which comparisons use tolerances, and can they ever prune a truly better solution?
6. What global bound is reported while nodes are active or queued?
7. What status is returned when no incumbent exists, the root is infeasible, the objective is unbounded, or a resource limit fires?
8. If all optimal solutions must be enumerated, is equality handled differently? For minimization, pruning at $B(R)=U$ is safe for finding one optimum but can discard alternative optima.

Branch and bound is best understood as a proof protocol implemented by a search engine. Branches maintain exhaustive coverage, bounds justify omission, and incumbents turn those local justifications into a global statement about the optimum.