PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Combinatorial Optimization with Graph Convolutional Neural Networks

Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, Andrea Lodi

arXiv:1906.01629v3cs.LGmath.OCstat.ML

TL;DR

Branch-and-bound variable selection can strongly affect search-tree size, yet expert heuristics are tuned to representative MILP sets that may differ from recurring instances. This paper learns variable-selection policies from strong branching with a graph convolutional network and reports improvements over prior machine-learning approaches and SCIP’s default strategy, while generalizing to larger instances.

  • Problem

    Expert-designed branch-and-bound heuristics are tuned to representative MILP sets that may differ from recurring instances, while variable selection can strongly affect search-tree size.

    Source: §1 · p. 2, §3.2 · p. 3

  • Method

    The paper uses imitation learning from strong branching to train a graph convolutional network that represents MILPs through their variable-constraint bipartite structure.

    Source: §1 · p. 2, §4.3 · p. 5

  • Results

    Across four NP-hard problems, GCNN policies outperformed prior machine-learning branching approaches and could outperform SCIP’s default strategy, while generalizing to larger instances.

    Source: §5.2 · p. 8, §7 · p. 9

  • Takeaways & Limitations

    The results indicate that GCNN branching can be a competitive alternative on the evaluated problems, including instances larger than those used for training.

    Source: §5.2 · p. 8, §7 · p. 9

    Performance improvement generally decreases on progressively larger instances, and a model trained on small instances showed a performance drop on huge ones.

    Source: §6 · p. 9

Abstract

from arXiv · show

Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose a new graph convolutional neural network model for learning branch-and-bound variable selection policies, which leverages the natural variable-constraint bipartite graph representation of mixed-integer linear programs. We train our model via imitation learning from the strong branching expert rule, and demonstrate on a series of hard problems that our approach produces policies that improve upon state-of-the-art machine-learning methods for branching and generalize to instances significantly larger than seen during training. Moreover, we improve for the first time over expert-designed branching rules implemented in a state-of-the-art solver on large problems. Code for reproducing all the experiments can be found at https://github.com/ds4dm/learn2branch.

1 Introduction

The paper learns MILP branch-and-bound variable-selection policies with graph convolutional neural networks, using the MILP bipartite graph and imitation of strong branching. The approach improves on traditional branching rules and generalizes to larger instances than those used in training.

  • For MILPs, branch-and-bound is an exact method that partitions the solution space and prunes subtrees using relaxation bounds; its sequential decisions include node and variable selection.Exact methods can also provide an intermediate solution and optimality bound when interrupted before termination.Source: §1 · pp. 1–2
  • Learning branching policies faces challenges in encoding variable-sized MILP and search-tree states and designing models that generalize to larger instances.Repeatedly solved problem classes can differ from the instances typically used to evaluate branch-and-bound algorithms.Source: §1 · p. 2
  • GCNN policies use the MILP variable-constraint bipartite graph and behavioral cloning with cross-entropy to imitate strong branching decisions.The authors argue that predicting decisions is less difficult than predicting strong-branching scores or rankings.Source: §1 · p. 2
  • Across set covering, combinatorial auction, capacitated facility location, and maximum independent set, the approach substantially improves on traditional branching rules and generalizes to larger instances.The evaluation compares with prior learning approaches,, and [24], and SCIP’s default hybrid branching rule.Source: §1 · p. 2

2 Related work

Prior work applies learning to branching, other solver decisions, and approximate combinatorial optimization. This work distinguishes its branching policy through expert-decision classification, reduced feature engineering, larger-instance generalization, and evaluation in a full-fledged solver.

Related work

  • Unlike prior learned branching policies, this work classifies expert decisions, reduces feature engineering, tests larger-instance generalization, and evaluates in a full-fledged solver.Khalil et al. and Hansknecht et al. [24] learn candidate rankings, while Alvarez et al. regresses strong-branching scores; prior evaluations used simplified solvers.Source: §2 · p. 2
  • GCNNs have also been used for approximate combinatorial optimization, including greedy heuristics and NeuroSAT [47].These works provide evidence that GCNNs can capture structural characteristics of combinatorial optimization problems.Source: §2 · pp. 2–3
  • Other variable-selection methods choose among branching rules, combine existing scores [8], or learn policies for SAT [36] and SMT solvers.The SAT methods are restricted to conflict-driven clause learning and cannot readily extend to B&B for arbitrary MILPs; the SMT method exploits solver-specific aspects.Source: §2 · p. 3
  • Learning node selection, node selection and pruning [48], or primal heuristics addresses B&B components complementary to variable selection.The paper notes these approaches could in principle be combined to improve solver performance.Source: §2 · p. 3

3 Background

The background explains how LP relaxations and branching form a search tree for solving MILPs, with variable selection affecting its size. It also frames branching decisions as an episodic MDP and motivates imitation learning over reinforcement learning with a designed reward.

3.1 Problem definition

  • A MILP’s LP relaxation gives a lower bound; branching on a fractional variable creates two subproblems, and B&B uses bounds to certify optimality or infeasibility.The problem size is typically measured by the constraint matrix’s rows and columns.Source: §3.1 · p. 3

3.2 Branching rules

  • Branching choices strongly affect B&B tree size; strong branching scores candidates by expected bound improvement but costs two LP solves each, so solvers use hybrid rules.Hybrid strategies gradually switch from strong branching to simpler heuristics such as pseudo-costs or combinations of heuristics.Source: §3.2 · pp. 3–4

3.3 Markov decision process formulation

  • B&B is an episodic MDP in which a brancher selects a fractional variable at each state, and imitation learning avoids the challenges of designing a reinforcement-learning reward.A state includes the search tree, past branching decisions, current focused leaf, LP solutions, and solver statistics.Source: §3.3 · p. 4

4 Methodology

The method learns branch-and-bound variable-selection policies from an expert via imitation learning rather than reinforcement learning, and parameterizes the policy with a graph convolutional neural network over a variable-constraint bipartite graph.

4.1 Imitation learning

  • Behavioral cloning trains on strong-branching state-action examples and minimizes cross-entropy to imitate the expert.Strong branching has high computational cost but usually produces the smallest branch-and-bound trees; the examples are collected on training instances of interest.Source: §4.1 · p. 5

4.2 State encoding

  • The state graph links each LP constraint row to variables with nonzero coefficients, using constraint, variable, and edge features.With cuts enabled only at the root, graph structure is unchanged across the branch-and-bound tree, reducing feature-extraction cost. This representation is only a subset of solver state, yet strong branching can perform well from such a subset.Source: §4.2 · p. 5

4.3 Policy parametrization

  • The GCNN policy uses size-flexible, permutation-invariant graph convolutions whose computation scales with graph density, suiting sparse MILP graphs [12].A single convolution comprises variable-to-constraint and constraint-to-variable passes; a final perceptron and masked softmax assign probabilities to non-fixed candidate variables.Source: §4.3 · pp. 5–6
  • Prenorm layers stabilize un-normalized convolutions by centering and scaling summed features using fixed training-set statistics.The affine transformation x ← (x−β)/σ uses the empirical mean and standard deviation, initialized before training; un-normalized convolutions plus prenorm improve generalization to larger problems.Source: §4.3 · p. 6

5 Experiments

Experiments compare GCNN with learned and solver branching baselines on four hard MILP benchmarks, then test its convolution and prenorm choices through ablation.

5.1 Setup

  • The four benchmarks—set covering, combinatorial auction, capacitated facility location, and maximum independent set—test generalization from easy training instances to larger evaluation sizes.Evaluation uses SCIP 6.0.1 with a one-hour limit, root-only cutting planes, and disabled restarts; each difficulty uses 20 new instances and five seeds.Source: §5.1 · pp. 6, 8
  • Comparisons include default SCIP reliability pseudocost branching, full strong branching, and three learned branchers: TREES, SVMRANK, and LMART.For each benchmark, models train on 100,000 branching samples from 10,000 instances, with 20,000 validation samples from 2,000 instances.Source: §5.1 · pp. 6–7

5.2 Comparative experiment

  • GCNN clearly dominates overall in solving time, except LMART on combinatorial-auction Easy instances and RPB on maximum-independent-set Medium instances.The comparison reports solving time, wins, and node counts across Easy, Medium, and Hard instances.Source: Table 2 · p. 7, §5.2 · p. 8
  • GCNN outperforms the baseline competitors in prediction accuracy on all four problems; SVMRANK and LMART are on par, while TREES performs worst.The accuracy comparison uses the highest-ranked decision and top-five and top-ten rankings against the variables with the highest strong-branching score.Source: §5.1 · p. 7, §5.2 · p. 8
  • GCNN generalizes beyond training sizes and beats RPB in running time in almost every configuration, with significant node reductions on medium and hard set-cover and auction instances.Maximum independent set is a difficult exception: all machine-learning methods solve fewer instances than RPB, and GCNN shows high time and node variability; FSB is slow despite small trees.Source: §5.2 · p. 8

5.3 Ablation study

  • On small set-cover instances, MEAN and SUM perform similarly to GCNN; on large instances, both are significantly worse in solving time and node count, especially on hard instances.The ablation contrasts mean convolutions, sum convolutions without prenorm, and sum convolutions with prenorm; results support sum convolutions and prenorm for generalization and training stability.Source: §5.3 · p. 8, Table 3 · p. 9

6 Discussion

Discussion emphasizes that branching must trade off decision quality against speed, and that learned policies can transfer to larger instances but have problem-dependent limits.

6 Discussion

  • The proposed GCNN architecture balances decision quality against inference speed: deeper or wider policies slightly reduced node counts but increased decision costs, worsening average solving time.Strong branching illustrates the same tradeoff: it makes excellent decisions and uses fewer nodes overall, but each decision is so slow that total running time is not competitive.Source: §6 · p. 9
  • GCNNs generalize from small training instances to larger ones, but performance tends to decline with scale; medium-instance training restored strong performance on huge instances.Generalization limits depend on problem structure, making precise a priori estimates difficult.Source: §6 · p. 9

7 Conclusion

The paper formulates branch-and-bound as a Markov decision process and uses a bipartite-graph GCNN to learn branching policies that outperform prior machine-learning approaches and SCIP’s default strategy on four NP-hard problems, while generalizing to larger instances.

7 Conclusion

  • On four NP-hard problems, GCNN policies outperformed previously proposed machine-learning branching approaches and SCIP’s default strategy, and generalized to instances larger than those seen during training.Larger-instance generalization matters because collecting strong-branching decisions for training can be computationally prohibitive on large instances.Source: §7 · p. 9
  • The approach models branch-and-bound as a Markov decision process and encodes its state as a variable-constraint bipartite graph for GCNN branching policies learned by imitation.The authors identify sum convolutions with the proposed prenorm layer as a promising architectural prior for branching in MILP.Source: §7 · p. 9
  • Future work will test the approach on more combinatorial problems, explore reinforcement learning to improve imitation-learned policies, investigate hybrid branching methods, and analyze learned policies for MILP insights.Source: §7 · p. 9

Supplementary Materials

The supplementary materials identify the paper as arXiv:1906.01629v3, dated 30 October 2019, and name Andrea Lodi with the affiliations Mila and Polytechnique Montréal.

1 Dataset collection details

The section describes how training and validation state-action datasets are collected for four benchmark problems and how strong branching is isolated as an oracle during sample generation.

1 Dataset collection details

  • Each problem uses 10,000 training, 2,000 validation, and 60 test instances, with 20 test instances each for easy, medium, and hard cases.Using SCIP with a new random seed for each solve, the authors sample instances with replacement until they record 100,000 training and 20,000 validation node states and strong-branching decisions; not all instances need be used.Source: §1 · p. 14
  • The authors re-implemented SCIP's full strong branching rule as vanillafullstrong to provide oracle decisions without changing the solver state.This version also enables extraction of strong-branching scores for ranking- and regression-based machine-learning competitors.Source: §1 · p. 14

2 Training details

The section specifies how the GCNN is trained and how the SVMrank, LambdaMART, and ExtraTrees baselines are adapted and trained. The baselines use variable-wise features and strong-branching supervision, with training-set limits imposed by scalability or memory constraints.

2.1 GCNN

  • GCNN training uses recorded strong-branching decisions and bipartite state representations, followed by prenorm pretraining and cross-entropy optimization with Adam.Training uses minibatches of 32 and an initial learning rate of 1e-3; the rate is divided by 5 after 10 epochs without validation-loss improvement, and training stops after 20 such epochs.Source: §2.1 · p. 15

2.2 SVMrank and LambdaMART

  • SVMrank and LambdaMART use strong-branching ranks and Khalil et al. features with SCIP-specific substitutions, query normalization, 80th-centile labels, and all candidate variables.SVMrank uses a cost-sensitive pairwise loss and validation-selected regularization; LambdaMART uses 500 estimators, normalized discounted cumulative gain, and validation early stopping. Training was capped at 250,000 candidate variables and 100,000 validation variables because full-dataset training required over 500GB RAM for SVMrank or over one week for LambdaMART.Source: §2.2 · pp. 15–16

2.3 ExtraTrees

  • ExtraTrees combines each variable’s features with neighborhood minima, means, and maxima of edge and constraint features, then selects the candidate with the highest predicted strong-branching score.It is trained by mean-squared error and limited to 250,000 candidate variables because of memory issues; the authors omit Khalil et al. expert features because they degraded performance.Source: §2.3 · p. 16

3 When are decisions hard for the GCNN policy?

On easy instances across four problems, GCNN uncertainty roughly correlates with strong-branching uncertainty, suggesting that both hesitate on intrinsically difficult decisions.

3 When are decisions hard for the GCNN policy?

  • GCNN hesitation roughly tracks strong-branching hesitation across decisions on easy instances in all four problems, suggesting both identify intrinsically difficult choices.Confidence is measured by policy entropy; strong-branching entropy is log m, where m is the number of candidates with maximal strong-branching score.Source: §3 · p. 16

4 Training set sizes for the machine learning methods

The GCNN’s accuracy advantage over competing machine-learning methods is not explained solely by its larger training set: a GCNN trained on the competitors’ data amount still clearly outperforms them. The section also identifies the GCNN’s ability to use larger training sets within the same computational budget as an advantage.

4 Training set sizes for the machine learning methods

  • Computational limits prevented the competing machine-learning methods from being trained on the full dataset used for the GCNN, while Table 3 reports the branching-node counts for the training datasets.The complete GCNN dataset contains 100,000 training and 20,000 validation branching nodes; the competitors’ datasets were sized to obtain 250,000 training and 100,000 validation candidate-variable samples.Source: §4 · pp. 16–17, Table 3 · p. 17
  • The GCNN’s ability to scale to larger training sets within the same computational budget is a major advantage over the competing machine-learning methods.The authors note that there is little reason to restrict models to smaller datasets than they can handle, particularly since reliability pseudocost is not a machine-learning method.Source: §4 · pp. 16–17
  • GCNN-SMALL, trained on the same amount of data as competitors, still clearly outperforms them in imitation-learning accuracy.The comparison uses 250,000 candidate variables for training and 100,000 for validation; the authors conclude that more samples improve performance but do not alone explain the gains.Source: §4 · p. 17, Table 4 · p. 18

Related papers

Loading 1906.01629v3…