PaperlayerView exact revision on arXiv

Source-linked AI summary

Hybrid Models for Learning to Branch

Prateek Gupta, Maxime Gasse, Elias B. Khalil, M. Pawan Kumar, Andrea Lodi, Yoshua Bengio

arXiv:2006.15212v3cs.LGmath.OCstat.ML

TL;DR

MILP solvers use CPU-only branch-and-bound, limiting the practicality of a GNN branching model whose inference is not competitive without a GPU. The paper therefore combines a root-node GNN with inexpensive MLP predictors, achieving up to 26% lower solving time across four problem families while retaining extrapolation to harder instances.

  • Problem

    The GNN branching model has high inference cost and is not competitive on CPU-only machines, although MILP solvers rely solely on CPUs.

  • Method

    The proposed hybrid architecture runs a GNN at the root node and combines its structural representation with cheap candidate features for MLP prediction at later nodes.

  • Results

    Up to 26% lower overall solving time was achieved across four MILP problem families versus SCIP’s default branching strategy without a GPU.

  • Takeaways & Limitations

    The hybrid model provides a CPU-compatible compromise between the expressive power of GNNs and the computational efficiency of MLPs while extrapolating to harder problems than those used for training.

  • Takeaways & Limitations

    The comparison with general branching such as RPB is not completely fair because specialized versions of those strategies remain future work.

Abstract

from arXiv · show

A recent Graph Neural Network (GNN) approach for learning to branch has been shown to successfully reduce the running time of branch-and-bound algorithms for Mixed Integer Linear Programming (MILP). While the GNN relies on a GPU for inference, MILP solvers are purely CPU-based. This severely limits its application as many practitioners may not have access to high-end GPUs. In this work, we ask two key questions. First, in a more realistic setting where only a CPU is available, is the GNN model still competitive? Second, can we devise an alternate computationally inexpensive model that retains the predictive power of the GNN architecture? We answer the first question in the negative, and address the second question by proposing a new hybrid architecture for efficient branching on CPU machines. The proposed architecture combines the expressive power of GNNs with computationally inexpensive multi-layer perceptrons (MLP) for branching. We evaluate our methods on four classes of MILP problems, and show that they lead to up to 26% reduction in solver running time compared to state-of-the-art methods without a GPU, while extrapolating to harder problems than it was trained on. The code for this project is publicly available at https://github.com/pg2455/Hybrid-learn2branch.

1 Introduction

MILP branch-and-bound performance depends strongly on branching decisions, motivating learned policies that balance predictive quality against inference cost. Because the original GNN is not competitive on CPU-only machines, the paper proposes a hybrid architecture that retains structural information from a root-node GNN while using inexpensive predictors elsewhere.

  • MILPs are NP-hard optimization problems, and branch-and-bound solves them by recursively partitioning subproblems and solving linear relaxations.
  • Branching selects the decision variable used to partition the current subproblem, making it a central branch-and-bound decision that affects the search tree and running time.
  • GNN-based branching uses MILP bipartite graphs and imitation learning to approximate the expensive strong-branching heuristic.
  • CPU-only inference makes the original GNN noncompetitive despite its branching quality, exposing a trade-off between decision quality and decision time.
  • The hybrid architecture applies a GNN at the root node and a fast MLP at remaining nodes, augmenting the MLP with root-level structural information.
  • Up to 26% lower overall solving time was achieved across four MILP problem families versus SCIP’s default branching strategy without a GPU.

3 Preliminaries

The preliminaries define MILPs and describe branch-and-bound as a recursive procedure that branches on fractional integer variables until optimality is established. The selected branching variable partitions each subproblem into two descendants.

  • A MILP combines a linear objective, linear constraints, and continuous and integral decision variables.
  • Branch-and-bound first solves the LP relaxation, then stops when the solution is integral or inferior to a known integral solution.
  • If the LP solution is fractional, the algorithm selects an integral variable and creates two sub-MILPs with additional constraints.
  • The selected variable is the branching variable, while C denotes the set of branching candidates.
  • The root node contains the original MILP, whereas subsequent nodes contain local MILPs generated during the search.

4 Methodology

The methodology combines root-level GNN representations with inexpensive candidate features and MLP-based predictors at tree nodes. It also evaluates alternative hybrid forms and training procedures, including pre-training, end-to-end training, knowledge distillation, auxiliary representation objectives, and depth-dependent loss weighting.

  • Hybrid architecture: Node representations use either a bipartite graph G or cheaper branching-candidate features X, with the hybrid strategy combining both representations.The graph contains variable, edge, and constraint features, whereas X contains candidate-specific features.
  • Hybrid architecture: The hybrid model extracts structural information with a GNN at the root and combines it with cheap candidate features X at each tree node.This aims to approach the performance of GNN(G) while retaining a cost closer to MLP(X).
  • Hybrid architecture: The evaluated functional forms enrich MLP inputs with GNN outputs through mechanisms including concatenation and feature-wise linear modulation.In FiLM, GNN-generated parameters modulate intermediate MLP representations as h ← β · h + γ.
  • Training protocol: Training uses strong branching decisions as imitation-learning targets for identifying the highest-scoring branching candidate.The observations include root graphs, node graphs, candidate features, and strong-branching decisions.
  • Training protocol: The protocol compares pre-trained and end-to-end training, knowledge distillation from a pre-trained GNN, and auxiliary objectives that diversify variable representations.The auxiliary objectives use Euclidean distance or minimum hyperspherical energy to separate representations.
  • Loss weighting scheme: Depth-dependent loss weighting addresses distribution shift by assigning node losses according to relative depth in the branch-and-bound tree.Five weighting functions share w(0) = 1.0 at the root and w(1) = e^-0.5 at the deepest node, while differing between those endpoints.

5 Experiments

The experiments evaluate branching strategies across four MILP problem classes and compare predictive accuracy, training protocols, runtime, and optimality gaps. The hybrid FiLM approach performs strongly on CPU-based solving, while larger unsolved instances and generalization remain important limitations.

  • Evaluation setup: The evaluation uses four MILP problem classes, with small, medium, and big instances measuring performance across training and increasing problem sizes.Each scenario uses 20 instances and three solver seeds; standard metrics include solving time and node count.
  • Model selection: All considered hybrid models outperform MLPs across the four problem sets, while FiLM and CONCAT perform significantly better than other architectures.GNN performance serves as an upper bound for the hybrid models’ test accuracy.
  • Training protocols: Training protocols improve FiLM accuracy by 0.5–0.9%, producing a minor yet practically useful improvement in B&B performance.Knowledge distillation improves FiLM performance except for Combinatorial Auctions.
  • Loss weighting: Sigmoidal loss weighting is selected because exponential and linear schemes appeared to degrade performance by disregarding early tree nodes too aggressively.The weighting experiments use a simple MLP trained on small Combinatorial Auctions instances and evaluated through B&B tree size on big instances.
  • Runtime performance: Up to 26% reduction in medium-instance solving time and up to 8% reduction on big instances are achieved versus the next-best branching strategy.The comparison includes both learned and classical strategies; FiLM also performs substantially better than other CPU-based strategies, while CPU GNN inference loses in running-time performance.
  • Limitations: Most big Set Covering and Maximum Independent Set instances remain unsolved, although FiLM models close a larger optimality gap than other branching strategies.The paper also notes that evaluating larger-than-studied instances is time-consuming and that test Top-1 accuracy is only a proxy for B&B node count under distribution shift.

6 Conclusion

The paper combines GNNs with inexpensive MLPs to balance branching accuracy and computational cost, achieving savings in solver time and nodes compared with classical and expensive learned strategies.

  • Hybrid models combine GNN expressiveness with MLP computational efficiency for learning to branch in MILP solvers.Training protocols augment basic MLPs to narrow the accuracy gap with more expensive models.

Broader Impact

The work addresses the gap between GPU-oriented learning-to-branch methods and CPU-based MILP solvers. It provides a CPU-compatible integration path for machine-learning branching strategies.

  • MILP solvers run on CPU-only machines, while GPU-based learning-to-branch techniques had not been practically integrated into them.The challenge became more pressing after GNNs demonstrated benefits over SCIP's default strategy.
  • The proposed CPU-based techniques approximate GPU-model performance and provide a viable way to integrate learning to branch into commercial and noncommercial solvers.The authors connect this integration to broader use by solver developers and practitioners.

Supplement: Hybrid Models for Learning to Branch

This supplied supplement passage contains author and affiliation information rather than substantive research content.

  • The listed authors are Maxime Gasse, Prateek Gupta, Elias B. Khalil, Andrea Lodi, and Yoshua Bengio.The affiliations include Mila, Polytechnique Montréal, the University of Oxford, the Alan Turing Institute, and the University of Toronto.
  • The paper is identified as arXiv:2006.15212v3, dated 23 October 2020.

1 Inefficiency in using GNNs for solving MILPs in parallel

When multiple MILPs are solved in parallel, separately initialized GNNs can underutilize a GPU because asynchronous solving limits batching opportunities and GPU occupancy.

  • Asynchronous parallel MILP solving requires a separate GNN for each MILP, creating GPU memory and utilization constraints.The authors note that multiple GNNs can fit on one GPU but still use it inefficiently.
  • Packing 25 GNNs onto a Tesla V100 32 GB GPU still produces inefficient utilization.Figure 1 measures size as either batched inputs or separately simultaneous inputs on the GPU.

2 Input Features

The study compares input features and architectures for CPU-efficient branching, emphasizing cheaper predictors alongside graph-based representations. Relative-runtime results identify MLP ALL and GNN DOT as favored across four problem sets.

  • Input features: The models use graph features from prior branching work and 92 additional features for the MLP input X.The graph is represented through features described for G, while X contains 92 features.
  • Runtime comparison: Runtime comparisons measure total function-evaluation time across B&B nodes, without considering decision quality.The estimate uses 20 instances per difficulty level for each problem class and is described as rough.
  • Architectures: Five architectures span attention-based models, simple dot-product predictors, and MLP predictors used throughout the B&B tree.The comparison covers a spectrum from stronger inductive biases to cheaper architectures.
  • Runtime comparison: MLP ALL and GNN DOT are favored across the four problem sets in relative-runtime comparisons.The observation motivates exploring hybrid architectures.
  • Runtime comparison: Attention and transformer architectures perform better on GPUs, but their CPU performance is not better than GNNs.The authors associate the GPU advantage with massive parallelization in attention computations.

4 Attention Mechanism for MILPs

The attention mechanism lets variables and constraints attend within their own groups and lets variables attend to constraints through feature-modulated scores. Experiments compare this expressive architecture under fixed training and hardware settings.

  • Attention mechanism: Variables and constraints attend to all other variables or constraints through multi-headed self-attention.A final variable-to-constraint attention step uses variable representations as queries and constraint representations as keys.
  • Attention mechanism: Variable-to-constraint attention is modulated by variable-constraint features before producing final variable representations.The modulation follows the mechanism described by Shaw et al.
  • Experimental setup: The experiments use 10,000 training instances and 20,000 instances each for validation and testing.The training, validation, and testing sets contain 150,000, 30,000, and 30,000 collected observations, respectively.
  • Experimental setup: Knowledge distillation uses temperature T = 2 and mixing weight α = 0.9, while β is selected from {0.01, 0.001, 0.0001}.The β search targets the ED and MHE components.
  • Experimental setup: CPU evaluations run on an Intel Xeon E5-2650 v4, while GPU GNN evaluations use an NVIDIA TITAN Xp.The reported software environment includes PyTorch and CUDA 10.1 for GPU evaluation.

6 Depth-dependent loss weighting scheme

The depth-dependent weighting experiments compare branching strategies across architectures and loss-weighting schemes. The sigmoidal scheme achieves the best observed performance in the reported comparison.

  • Weighting schemes: The sigmoidal weighting scheme achieves the best performance among the compared schemes.The comparison plots sorted node-count ratios relative to the minimum observed for each instance.
  • Model results: The reported architecture results include top-1 accuracy and address auxiliary-task availability across model families.Auxiliary-task training is not possible for HyperSVM architectures, so those results are omitted from the relevant table.
  • Model results: FiLM models overfit on small maximum-independent-set instances, motivating regularization with 2,000 observations from medium instances.The regularized models are evaluated on the resulting medium-instance dataset.

9 Performance of HyperSVM architectures

HyperSVM architectures minimize computation cost but lose generalization on larger instances compared with FiLM architectures. Training-protocol comparisons show that auxiliary tasks help selectively, while inference cost remains unchanged.

  • HyperSVM performance: HyperSVM architectures are the cheapest computationally, but their ability to generalize to larger instances is reduced.The comparison with FiLM evaluates whether a 1–2% accuracy loss can still produce faster solving times.
  • HyperSVM performance: FiLM architectures generalize to larger instances better than HyperSVM architectures in the reported comparison.Table 8 compares the best FiLM and HyperSVM architectures from the main results table.
  • Generalization: FiLM models remain competitive on instances twice the size of the largest training instances, with performance depending strongly on problem family.The larger-instance evaluation contains 20 instances solved with three seeds each, producing 60 runs.
  • Training protocols: Auxiliary-task and knowledge-distillation training are clear winners through medium problem sizes, but KD ties KD plus auxiliary tasks in some comparisons.The performance gap across training protocols is described as small overall.
  • Training protocols: KD plus auxiliary tasks is recommended only when its accuracy is significantly better than KD alone, because inference cost is independent of training protocol.Accuracy differences are significant for Combinatorial Auctions and Maximum Independent Set but not for Capacitated Facility Location and Set Covering.
Loading 2006.15212v3…