Branch-and-bound

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) 1906.01629 §3.1 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 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 1906.01629 §1 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 1906.01629 §3.2. Card: Exact Combinatorial Optimization with Graph Convolutional Neural Networks. Its full version, labelled FSB, has the highest per-instance times in the paper's tables for most problem families 1906.01629 tab. 2.

Reliability pseudocost (solver default)

Hybrid rules switch from strong branching to cheaper heuristics 1906.01629 §3.2. The paper's baseline is SCIP's default, the reliability pseudocost rule, called RPB there 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 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] 1906.01629 §4.2 1906.01629 eq. 3. No reinforcement learning is used 1906.01629 §3.3. Card: Exact Combinatorial Optimization with Graph Convolutional Neural Networks.

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 1906.01629 §5.1. It has the highest imitation accuracy on all four families 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.

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 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 1906.01629 §3.1.

# 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:

# 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 1906.01629 tab. 2 (1450 and 29981) differ from those in 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 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: 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.