---
kind: concept
slug: branch-and-bound
title: Branch-and-bound
summary: >-
  Exact search for mixed-integer programs: split one fractional variable into two child problems and prune subtrees that cannot beat the incumbent. The branching rule, which variable to split on, decides the tree size. Shown here with strong branching, SCIP's reliability pseudocost default and a learned graph-network rule, on four NP-hard families (author-reported).
tags: [combinatorial-optimization, mixed-integer-programming, exact-solvers]
papers: ["1906.01629"]
related: [imitation-learning, graph-neural-network, a-star-search]
status: draft
updated_at: 2026-10-19
---

## Overview

Branch-and-bound solves a mixed-integer linear program by repeatedly splitting
one fractional variable into two child problems and pruning any subtree whose
bound cannot beat the best solution found so far (the incumbent)
[arxiv:1906.01629 §3.1] [arxiv:1906.01629 eq. 2]. The shared invariant is that
pruning never discards the optimum, so the result is exact. What the variants
differ on is the branching rule, the choice of variable to split on. That
choice changes the tree size a lot [arxiv:1906.01629 §3.2].

The paper this page is built from is the only source so far. It presents a
learned branching rule, and it treats the classical rules as the reference
points it is compared with [arxiv:1906.01629 §1] [arxiv:1906.01629 §5.1].

## Variants

### Strong branching

Strong branching tests every fractional candidate by solving two linear
programs per candidate and picks the one with the best score. It gives the
smallest trees, but it is too expensive to run at every node, so it is used
as an expert to imitate or as the full-strength baseline
[arxiv:1906.01629 §3.2]. Card: [Exact Combinatorial Optimization with Graph
Convolutional Neural Networks](/papers/1906.01629). Its full version, labelled
FSB, has the highest per-instance times in the paper's tables for most
problem families [arxiv:1906.01629 tab. 2].

### Reliability pseudocost (solver default)

Hybrid rules switch from strong branching to cheaper heuristics
[arxiv:1906.01629 §3.2]. The paper's baseline is SCIP's default, the
reliability pseudocost rule, called RPB there [arxiv:1906.01629 §5.1]. The
card does not describe its internal mechanism, so check the paper before
implementing it. In the paper's tables it is the reference the learned rules
are timed against, and it is faster than the learned rules in some settings
[arxiv:1906.01629 tab. 2].

### Learned variable selection with a graph network

The branching decision is treated as a learned policy. A bipartite graph
convolutional network reads the solver state, one node per LP row and one per
LP column, and is trained by behavioural cloning on strong branching's choices
with a cross-entropy loss over the fractional candidates [arxiv:1906.01629
§4.1] [arxiv:1906.01629 §4.2] [arxiv:1906.01629 eq. 3]. No reinforcement
learning is used [arxiv:1906.01629 §3.3]. Card: [Exact Combinatorial
Optimization with Graph Convolutional Neural Networks](/papers/1906.01629).

The variant is evaluated against three learned baselines (TREES, SVMRANK and
LMART) on four families (set covering, combinatorial auction, capacitated
facility location, maximum independent set) in SCIP 6.0.1
[arxiv:1906.01629 §5.1]. It has the highest imitation accuracy on all four
families [arxiv:1906.01629 tab. 1].

## When to use which

All figures are author-reported, on the paper's benchmarks. The first column
names the constraint each row answers.

| Situation | Use | Why |
|---|---|---|
| A need for the smallest tree, and two LPs per candidate affordable at each node | Strong branching | Smallest trees, but the full version's times are high in the paper's tables [arxiv:1906.01629 §3.2] [arxiv:1906.01629 tab. 2] |
| No training data or GPU budget, general-purpose solver | Reliability pseudocost (solver default) | Default in SCIP and the paper's baseline [arxiv:1906.01629 §5.1]; no training needed |
| Many solves from one problem family, with training data and GPU time to spare | Learned graph-network rule | Lowest time in most settings on the paper's families, including larger instances [arxiv:1906.01629 tab. 2] [arxiv:1906.01629 §5.2] |
| Hard maximum independent set instances | Check first; do not assume the learned rule wins | Every learned method solves fewer hard instances than RPB there [arxiv:1906.01629 §5.2] |
| Unseen families, or a solver other than SCIP 6.0.1 | Not shown by the paper | Results cover four families and one solver version [arxiv:1906.01629 §5.1] |

Training cost is high. The paper reports GPU training of several hours per
problem for the learned rule, against under three hours for the competitors
and under 0.2 hours for TREES [arxiv:1906.01629 suppl. §5], so the learned
rule pays off only when a family is solved many times.

## Implementation sketch

The loop is shared by every variant. Only the branching rule changes. The
sketch uses the paper's split-and-prune structure and a placeholder for the
rule [arxiv:1906.01629 §3.1].

```pseudocode
# Keep open subproblems and the best solution so far  [arxiv:1906.01629 §3.1]
open = [root_relaxation]
incumbent = none
while open is not empty:
    # Pick the next node to process; depth-first or best-bound is solver-specific
    node = open.pop()
    # Solve the LP relaxation of this node  [arxiv:1906.01629 §3.1]
    bound, solution = solve_lp(node)
    # Prune when the bound cannot beat the incumbent  [arxiv:1906.01629 eq. 2]
    if incumbent exists and bound >= incumbent.value:
        continue
    if solution is integer:
        incumbent = solution
        continue
    # The branching rule is the only part that varies by variant  [§3.2]
    var = choose_branch_variable(node, solution)
    # Two children: var <= floor(value) and var >= ceil(value)
    open.push(child_with(node, var, "<=", floor(solution[var])))
    open.push(child_with(node, var, ">=", ceil(solution[var])))
return incumbent
```

Where the variants differ inside `choose_branch_variable`:

```pseudocode
# Strong branching: score every fractional candidate with two LPs each
# [arxiv:1906.01629 §3.2]
def strong_rule(node, solution):
    return argmax(strong_score(node, v) for v in fractional(solution))

# Learned rule: one forward pass of the policy, then the best fractional
# candidate  [arxiv:1906.01629 §4.3]
def learned_rule(node, solution):
    scores = policy(encode_state(node))  # bipartite graph  [§4.2]
    return argmax(scores[v] for v in fractional(solution))
```

## Contradictions

The paper's own tables disagree on node counts. For set covering, the
medium and hard GCNN node counts in [arxiv:1906.01629 tab. 2] (1450 and 29981)
differ from those in [arxiv:1906.01629 tab. 3] (1870 and 56348). The times
agree to rounding. The source card treats the node counts as uncertain and
cites the times instead. The table block labels in [arxiv:1906.01629 tab. 2]
are inferred, not stated, by the source card. No other card lists this concept
yet, so no cross-paper disagreement is recorded.

## Papers

- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](/papers/1906.01629): learns the branching rule of branch-and-bound with a bipartite graph convolutional network trained to imitate strong branching; compared with SCIP's default rule on four NP-hard families.