Exact Combinatorial Optimization with Graph Convolutional Neural Networks

In plain words

Many hard optimisation problems are solved by splitting them into smaller pieces, again and again, and throwing away pieces that cannot contain the best answer. Each split asks one question: which quantity should we cut on next? A rule that makes this choice well can save a lot of time, but the best known rule is slow, because it tests every option before choosing.

The authors train a neural network to make that choice quickly. They describe the problem as a graph: one kind of node stands for the rules of the problem, another for its quantities, and a link shows which quantity appears in which rule. A network that passes messages along these links learns to copy the slow expert's choices. It is trained on examples that a solver produced while it worked through many problems.

The learned rule is tested on four classic problem families and compared with the solver's default rule and with earlier learned rules. It is most accurate at copying the expert, and it is often faster to solve. It also keeps working on problems larger than the ones it was trained on, which is the main point of the paper.

TL;DR

A learned branching rule for branch-and-bound, the exact method behind most mixed-integer solvers. A bipartite graph convolutional network reads the solver state and is trained with cross-entropy to pick what strong branching would pick. On four NP-hard families it beats earlier learned rules on accuracy and beats SCIP's default rule on time in most settings, including larger instances. All numbers are author-reported on the authors' benchmarks.

Problem

Branch-and-bound solves a mixed-integer linear program by repeatedly splitting one fractional variable into two child problems and pruning subtrees that cannot beat the incumbent §3.1 eq. 2. The choice of variable, the branching rule, changes the tree size a lot §3.2. Strong branching gives the smallest trees, but it solves two LPs per candidate, so it is too expensive to run at every node. Solvers therefore use hybrid rules that switch from strong branching to cheaper heuristics §3.2.

Earlier learned rules imitated strong branching but relied on heavy manual feature engineering, and they were tested on simplified solvers. They also learned scores or rankings rather than the expert's decision §2. The paper asks whether a graph network can learn the decision directly, with less feature engineering, and whether it generalises to instances larger than those seen in training §1.

Assumption: the target is the solve time of a fixed problem family, so a rule is useful when it keeps trees small and its own cost low §6.

Method

Formulation. Branching is a Markov decision process: the state is the branch-and-bound tree and solver statistics, the action is a fractional variable at the focused node, and an episode is one instance §3.3 fig. 1. The paper does not use reinforcement learning. It uses behavioural cloning: run the expert on training instances, record pairs of (state, expert action), and minimise a cross-entropy loss over the candidate variables §4.1 eq. 3.

\mathcal{L}(\theta) = -\frac{1}{N}\sum_{(\mathbf{s}, \mathbf{a}^*)\in\mathcal{D}} \log \pi_\theta(\mathbf{a}^*\,|\,\mathbf{s}) eq. 3

The expert is strong branching. The paper re-implements its vanilla full strong-branching rule inside SCIP so that it has no side effects on the solver [suppl. §1].

State encoding. The state is a bipartite graph §4.2 fig. 2:

• one constraint node per LP row, with 5 features;
• one variable node per LP column, with 19 features;
• an edge for every non-zero coefficient, with 1 feature (the coefficient).

The feature list is in [suppl. §2.1]. Variable features are a one-hot type (binary, integer, implied integer, continuous), the normalised objective coefficient, lower- and upper-bound indicators, solution-at-bound indicators, solution fractionality, a one-hot basis status (lower, basic, upper, zero), the normalised reduced cost, LP age, solution value, incumbent value and average incumbent value. Constraint features are the cosine similarity with the objective, a normalised bias, a tightness indicator, a normalised dual value and LP age. The edge feature is the coefficient normalised per constraint [suppl. §2.1]. The paper notes the graph structure stays fixed during a run when cuts are only allowed at the root §4.2.

Policy. One graph convolution, made of two half-convolutions: first from variables to constraints, then from constraints back to variables §4.3 eq. 4. Each half sums per-edge messages from a 2-layer perceptron with ReLU, without degree normalisation, then applies a prenorm layer §4.3. The policy discards the constraint nodes, applies a final 2-layer perceptron to each variable, and takes a softmax over the fractional candidates only §4.3.

\mathbf{c}_i \gets f_{\mathcal{C}}\Big(\mathbf{c}_i,\; \sum_{j:(i,j)\in\mathcal{E}} g_{\mathcal{C}}(\mathbf{c}_i, \mathbf{v}_j, \mathbf{e}_{ij})\Big), \qquad \mathbf{v}_j \gets f_{\mathcal{V}}\Big(\mathbf{v}_j,\; \sum_{i:(i,j)\in\mathcal{E}} g_{\mathcal{V}}(\mathbf{c}_i, \mathbf{v}_j, \mathbf{e}_{ij})\Big) eq. 4

Prenorm. The authors argue that normalising by degree would remove the ability to count neighbours §4.3. They therefore use un-normalised sums and fix the weight-initialisation problem with a prenorm layer x ← (x − β)/σ. β and σ are set once from the empirical mean and standard deviation of the layer's input over the training data, and then frozen §4.3.

The code also adds an initial 2-layer embedding for constraints and for variables, and an extra prenorm inside the message. The paper text does not describe either; see Paper vs code.

# Expert data: (state, expert choice) pairs from solver runs  [§4.1] [suppl. §1]
# Which rule drives the tree is not stated; the code uses pseudo-cost.
# [code: 02_generate_dataset.py#L321]
def collect(instances, n_samples):
    samples = []
    while len(samples) < n_samples:
        # Pick an instance with replacement, and a new seed per run  [suppl. §1]
        instance = pick_random(instances)
        seed = pick_random_seed()
        for node in solver_run(instance, seed):
            # Code only: expert queried at about 5% of nodes
            # [code: 02_generate_dataset.py#L40, #L322]
            if random_uniform() >= 0.05:
                continue
            # Strong branching scores every fractional variable  [§3.2]
            scores = strong_branching(node)
            # Drop samples with negative scores; time-limit artefact
            # [code: 02_generate_dataset.py#L58]
            if any(score < 0 for score in scores):
                continue
            # State encoding  [§4.2]; label is the best-scoring candidate
            # [§4.1]
            best = argmax(scores)
            samples.append((encode_state(node), node.candidates[best]))
    return samples

# Freeze prenorm layers from training statistics  [§4.3]
# Code: layers are fixed one at a time, in order
# [code: 03_train_gcnn.py#L28-L60]
for layer in prenorm_layers(model):
    # beta = empirical mean of the layer input, sigma = its std  [§4.3]
    layer.beta = mean(layer_input(train_samples, layer))
    layer.sigma = std(layer_input(train_samples, layer))

# Training loop: cross-entropy over candidates  [§4.1] [eq. 3]
# Adam, batch 32, lr 1e-3; /5 after 10 stale epochs, stop after 20
# [suppl. §2.1]
learning_rate = 1e-3
stale_epochs = 0
best_loss = infinity
while stale_epochs < 20:
    for batch in minibatches(train_samples, size=32):
        # One score per variable from the policy network  [§4.3]
        scores = model(batch.state)
        # Softmax only over the fractional candidates  [§4.3]
        candidate_scores = scores[batch.candidates]
        loss = cross_entropy(candidate_scores, batch.expert_choice)
        adam_step(model, loss, learning_rate)
    valid_loss = mean_loss(model, valid_samples)
    if valid_loss < best_loss:
        best_loss = valid_loss
        stale_epochs = 0
        # Code: keep the best-validation weights  [code: 03_train_gcnn.py#L272]
        save(model)
    else:
        stale_epochs += 1
        # Divide the learning rate by 5 after each 10 stale epochs
        # [suppl. §2.1]
        if stale_epochs % 10 == 0:
            learning_rate = learning_rate / 5

# Half-convolution from source nodes to target nodes  [§4.2] [eq. 4]
def half_convolution(target, source, edges, edge_feats):
    # Pre-activation per edge (i, j): sum of three linear maps  [eq. 4]
    # Shape: (num_edges, 64); 64 is from the code, not the text
    pre = (linear_target(target[target_index])
           + linear_source(source[source_index])
           + linear_edge(edge_feats))
    # Prenorm, ReLU and a second linear map form the message g  [§4.3]
    messages = linear_msg(relu(prenorm_edge(pre)))
    # Un-normalised sum of messages at each target node  [§4.3]
    summed = segment_sum(messages, target_index, num_targets)
    # Prenorm after the sum  [§4.3]
    # [code: models/baseline/model.py#L142-L144]
    summed = prenorm_sum(summed)
    # Update each target node with MLP f on [summed, own features]  [eq. 4]
    # ReLU after each half  [code: models/baseline/model.py#L425]
    return relu(mlp_f(concat(summed, target)))

# Full policy: one forward pass per branching decision  [§4.2] [§4.3]
def policy(constraint_feats, edge_feats, variable_feats, edges):
    # Initial embeddings: code only, not in the paper text
    # [code: models/baseline/model.py#L295-L312]
    constraints = embed_constraints(constraint_feats)
    variables = embed_variables(variable_feats)
    edge_feats = prenorm_edges(edge_feats)  # edges: prenorm only, no MLP
    # Variables to constraints, then constraints to variables  [§4.2]
    constraints = half_convolution(constraints, variables, edges, edge_feats)
    variables = half_convolution(variables, constraints, edges, edge_feats)
    # Constraint nodes are discarded; score each variable  [§4.3]
    return output_mlp(variables)  # one score per variable, masked later

Inference. Choose the variable with the highest score among the fractional candidates §4.3. The paper's experiments use the best validation checkpoint.

Hyperparameters

Values in the paper unless marked "code". "Not stated" means the paper and its supplement do not give the value.

Results

Author-reported. Setup: SCIP 6.0.1 with default settings except for root-only cuts and no restarts, 1-hour time limit, 20 unseen instances per difficulty and 5 seeds §5.1. Models are trained on easy instances only tab. 2. The baseline reliability pseudocost rule (RPB) is SCIP's default §5.1.

Imitation accuracy (test set, mean ± std over 5 seeds, acc@k = the expert's best candidate is in the model's top k) tab. 1:

A control with the same training-set size as the competitors, GCNN-small, has acc@1 of 57.9, 55.0, 69.1 and 50.1 on the four problems [suppl. §4].

Policy evaluation (time = 1-shifted geometric mean in seconds; wins = times the policy was fastest, over instances it solved; nodes = B&B nodes on instances solved by all baselines; each cell gives mean ± average per-instance std) tab. 2. The four blocks are Set covering, Combinatorial auction, Capacitated facility location and Maximum independent set, mapped as in the Pitfalls.

Set covering

Combinatorial auction

Capacitated facility location

Maximum independent set

Headline reading, from the tables: GCNN has the highest imitation accuracy on all four problems tab. 1. Its solving time is lower than RPB's in 11 of the 12 problem-and-size settings; the exception is maximum independent set, medium, where RPB is faster. GCNN is the fastest method of all in 10 of the 12 tab. 2. The authors say the learned policy generalises to larger instances and beats RPB on time in almost every setting §5.2. For maximum independent set they note that every learned method solves fewer hard instances than RPB §5.2. The 11-of-12 and 10-of-12 counts are read off tab. 2 by this card, not stated by the authors.

Ablation on set covering, 20 instances per difficulty tab. 3.

The authors read this as evidence that sum convolutions generalise better and that the prenorm layer stabilises training §5.3. The GCNN row's node counts differ from tab. 2 (see Pitfalls).

Costs [suppl. §5]. GCNN training took 14.45, 3.84, 18.18 and 4.73 hours on set covering, combinatorial auction, facility location and max independent set. The competitors took at most 2.87 hours, and TREES under 0.2 hours. GCNN features are cheaper to extract, but its prediction is slower [suppl. §5].

Paper vs code

Code: official repository ds4dm/learn2branch at commit 57e82603fba39c34ff81baf9bd0b5768f5a1a860, MIT licence LICENSE.

• Max independent set graphs. Paper: Erdős–Rényi graphs with affinity 4 §5.1. Code: the generator calls Graph.barabasi_albert with affinity 4 01_generate_instances.py. An Erdős–Rényi generator exists but the instance path does not call it 01_generate_instances.py.
• Expert data collection. Paper: solve with SCIP and record states and strong-branching decisions during B&B [suppl. §1]. Code: the tree is driven by pseudo-cost branching, and the expert is queried at 5% of nodes 02_generate_dataset.py.
• Data-collection time limit. Paper: one-hour limit for evaluation §5.1. Code: 3600 s for training data, 600 s for facility location 02_generate_dataset.py.
• Constraint nodes. Paper: one node per LP row §4.2. Code: one node per finite side, so a two-sided row gives two nodes with opposite-sign features utilities.py.
• Prenorm layers. Paper: one prenorm layer, after the summation §4.3. Code: one after the per-edge pre-activation, and one after the summation model.py.
• Initial embeddings. Paper: none described. Code: a 2-layer ReLU embedding for constraints and for variables, and only a prenorm for edges model.py.
• Embedding width. Paper: not stated. Code: 64 model.py.
• Feature normalisation. Paper: "normalized" only. Code: objective and row norms, and LP age divided by (LP count + 5) utilities.py.
• Model selection. Paper: LR schedule and early stopping [suppl. §2.1]. Code: also restores the best-validation weights and caps training at 1000 epochs 03_train_gcnn.py.
• Pretraining data. Paper: not stated. Code: every 10th training sample file, batch 128 03_train_gcnn.py.
• Epoch definition. Paper: not stated. Code: 312 minibatches of 32 samples drawn with replacement 03_train_gcnn.py.
• Accuracy ties. Code counts a prediction as a hit when its score equals the best score, so ties count 03_train_gcnn.py.
• Time measure. Paper: a 1-shifted geometric mean of solving times in seconds §5.1. Code: CPU user time, clock type 1, limit 3600 05_evaluate.py. The paper does not name the clock.
• Strong branching. Paper: re-implemented in SCIP [suppl. §1]. Code: a patch to SCIP is supplied vanillafullstrong.patch.

No discrepancies were found in the SCIP parameters: root-only separation and disabled restarts match §5.1 utilities.py.

Pitfalls

• Table 2 block labels. In the LaTeX source the four problem titles of tab. 2 sit below their blocks, and the last title sits after the bottom rule. The mapping used here (first block = set covering, then auction, facility location, max independent set) is inferred, not stated. It is supported by three matches, to rounding, between the first block's GCNN times and the GCNN times in tab. 3; by the paper's text on where LMART and RPB win; and by the paper's remark that every learned method solves fewer hard instances than RPB, which holds only for the last block. Check against the PDF before relying on any single cell.
• Node counts disagree within the paper. For set covering, GCNN node counts are 1450 (medium) and 29981 (hard) in tab. 2, but 1870 and 56348 in tab. 3. The times agree to rounding. Either the ablation was run differently or one table is wrong. Cite the times and treat the node counts as uncertain.
• Strong-branching labels need a patched SCIP. Stock SCIP's strong branching changes solver state, so the paper uses a re-implementation [suppl. §1]. Without it, the labels differ from the paper's.
• The sampling policy is not in the paper. The code drives the tree with pseudo-cost and queries the expert at 5% of nodes 02_generate_dataset.py. The state distribution, and so the learned policy, depends on this choice.
• Samples are dropped silently. Any node where a strong-branching score is negative is skipped, which happens when the solver stops early 02_generate_dataset.py.
• Prenorm is frozen once. The shift and scale come from training data and never change §4.3. The code guards zero variance by using scale 1 model.py. A new distribution of instances does not refresh them.
• Un-normalised sums grow with degree. Without prenorm, activations scale with the number of neighbours. The ablation shows the prenorm version generalises better §5.3, so do not drop it.
• Constraint node count depends on the LP. Ranged rows create two nodes, so the graph size is not simply the number of rows utilities.py. Implement this rule exactly or the features will not match the trained weights.
• Normalisation constants are not in the paper. The "+5" in the LP-age feature and the norms used for coefficients, reduced costs and duals are code-only utilities.py. Missing any of them changes every input.
• Competitors trained on less data. SVMrank, LambdaMART and ExtraTrees were trained on 250k candidates because they ran out of memory on the full set [suppl. §2.2]. GCNN-small, trained on the same amount, beats them on accuracy in every column except auction acc@1, where it scores 55.0 against LMART's 57.3 [suppl. §4]. The time comparison in tab. 2 uses the full GCNN training set.
• Generalisation limit. Early experiments on even larger instances showed a drop for the model trained on small ones. The authors say training on larger instances fixes it §6. This result is not in the tables.
• Training cost. GCNN is the slowest to train on every problem [suppl. §5]. Plan for hours of GPU time per problem.
• Missing details. Adam betas, initialiser, maximum epochs and the number of ExtraTrees trees are not in the text. The code sets the initialiser (orthogonal), the epoch cap and the tree count; Adam uses TensorFlow's defaults.

Lineage

• Builds on: imitation of strong branching with ranking or score targets, by Khalil et al. (AAAI 2016), Alvarez et al. (INFORMS JoC 2017) and Hansknecht et al. (2018). This paper uses classification over the expert's choice instead §2. No arXiv ids are given in the text, so none are linked.
• Compared against: SCIP's reliability pseudocost rule (RPB), full strong branching (FSB), and the three learned baselines TREES, SVMRANK and LMART §5.1.
• Superseded by: not stated in this card.