Source-linked AI summary
Exact Combinatorial Optimization with Graph Convolutional Neural Networks
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, Andrea Lodi
TL;DR
Branch-and-bound variable selection is difficult because branching choices strongly affect search trees, while strong branching is effective but expensive. The paper learns a GCNN policy from strong-branching decisions using the MILP variable-constraint bipartite graph. Across four NP-hard problem classes, the learned policies outperform prior machine-learning branching methods and can outperform SCIP’s default strategy on large problems.
Problem
Branching choices strongly affect branch-and-bound search-tree size, but strong branching is computationally expensive and existing heuristics may face differing instance distributions.
Method
The method represents MILP branch-and-bound states as bipartite graphs and trains a GCNN variable-selection policy by behavioral cloning from strong branching.
Results
Across four NP-hard problems, GCNN policies outperform previously proposed machine-learning branching approaches and can outperform SCIP’s default branching strategy on large problems.
Takeaways & Limitations
Graph-based policy learning reduces manual feature engineering while supporting generalization to instances larger than those used during training.
Takeaways & Limitations
Performance improvements generally decrease on progressively larger instances, and models trained on small instances can drop in performance on huge instances.
Abstract
from arXiv · showhide
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
Combinatorial optimization is difficult because discrete solution spaces can make exhaustive search intractable, while MILP instances are commonly solved exactly with branch-and-bound. The paper learns variable-selection policies to address limitations of hard-coded branching heuristics across differing problem instances.
- Motivation: Combinatorial optimization seeks optimal configurations in discrete spaces where exhaustive enumeration is intractable.Applications include electronics, transportation, management, retail, manufacturing, structured prediction, and maximum a posteriori inference.
- Branch-and-bound: Branch-and-bound recursively partitions the solution space and uses relaxation bounds to prune subtrees that cannot contain an optimum.
- Branch-and-bound: Node selection and variable selection are sequential branch-and-bound decisions traditionally guided by expert-designed hard-coded heuristics.
- Motivation: Repeatedly solved problem families may differ substantially from the representative instances used to evaluate branch-and-bound algorithms.
- Contribution: The paper proposes a graph convolutional neural network and imitation learning to approximate strong branching for variable selection.The approach uses the MILP variable-constraint bipartite graph and behavioral cloning with cross-entropy loss.
2 Related work
Prior work learns branching through instance-specific or offline imitation, ranking, score prediction, and rule-combination approaches. GCNNs have also been used for approximate combinatorial optimization, while other studies learn node selection, pruning, or primal heuristics.
- Learning branching rules: Khalil et al., Alvarez et al., and Hansknecht et al. learn branching rules by imitating strong branching with different learning formulations.The formulations include instance-customized or offline policies, ranking, and score prediction.
- GCNNs for optimization: GCNNs have been applied to approximate combinatorial optimization, including greedy heuristics and satisfiability prediction.These methods seek good solutions quickly without optimality guarantees.
- Learning branching rules: Other approaches learn variable-selection rules by clustering existing heuristics or weighting their scores rather than directly learning a branching policy.
- Other branch-and-bound decisions: Related work also learns node selection, pruning, and primal heuristics for branch-and-bound algorithms.
3 Background
Branch-and-bound solves MILPs by recursively branching on fractional variables while tracking relaxation and integral-solution bounds. Its branching decisions can be viewed as a Markov decision process, and strong branching offers high-quality but computationally expensive guidance.
- MILP formulation: A MILP is characterized by objective coefficients, a constraint matrix, right-hand sides, variable bounds, and integer-variable count.Its size is typically measured by the constraint matrix dimensions m and n.
- Branch-and-bound: Branching on a fractional variable creates two subproblems by updating its bounds with floor and ceiling operations.
- Branch-and-bound: Branch-and-bound builds a search tree whose leaf LP solutions provide lower bounds and best integral solutions provide upper bounds.The process stops when the bounds coincide or feasible regions no longer decompose.
- Branching rules: Selecting a fractional branching variable can substantially change the resulting search-tree size.
- Branching rules: Strong branching evaluates expected bound improvement for every candidate variable but requires two LP solves per candidate, making it prohibitive at every node.
- Markov decision process: The branch-and-bound process can be modeled as an episodic Markov decision process in which the solver is the environment and the brancher is the agent.Episodes begin with sampled MILP instances and end when optimization terminates; imitation learning avoids key reinforcement-learning issues.
4 Methodology
The method encodes branch-and-bound states as MILP bipartite graphs and trains a GCNN policy by behavioral cloning from strong branching. Message passing updates variable and constraint representations before a masked softmax selects among candidate variables.
- Imitation learning: Reinforcement learning is natural for the sequential branching problem but raises practical issues, motivating imitation learning.
- Imitation learning: Behavioral cloning records strong-branching expert state-action pairs and minimizes cross-entropy to learn the policy.Strong branching is expensive but usually produces the smallest branch-and-bound trees.
- State encoding: Each state is represented as a bipartite graph linking MILP constraint nodes to variable nodes whenever the corresponding matrix coefficient is nonzero.Node and edge features encode the constraint-variable structure, while restricting cuts can keep the graph topology fixed across the tree.
- Policy parametrization: The GCNN performs successive variable-to-constraint and constraint-to-variable passes, enabling node features to incorporate neighbor information.
- Policy parametrization: A final perceptron discards constraint nodes and applies masked softmax over non-fixed LP variables to produce branching probabilities.
- Policy parametrization: Un-normalized sum convolutions with prenorm layers improve generalization to larger problems compared with mean convolutions or sum convolutions without prenorm.The prenorm transformation stabilizes learning after neighborhood aggregation.
5 Experiments
The experiments compare GCNN branching against machine-learning and expert-designed baselines across four NP-hard benchmarks, evaluating accuracy, solving time, wins, and search-tree size. GCNN generally performs best, including on larger instances, while the ablation supports sum convolutions with prenorm layers.
- Comparative experiment: The study compares GCNN with three machine-learning branchers, SCIP’s reliability pseudocost rule, and full strong branching.The competing machine-learning methods are TREES, SVMRANK, and LMART; full strong branching serves as a slow expert reference.
- Experimental setup: Evaluation covers set covering, combinatorial auction, capacitated facility location, and maximum independent set benchmarks at easy, medium, and hard difficulty levels.Models are trained on easy instances and evaluated on separate instances, including larger problem sizes.
- Comparative experiment: GCNN clearly outperforms the baseline competitors on imitation-learning accuracy across all four problems.Accuracy is measured using acc@1, acc@5, and acc@10 relative to the highest strong-branching decision.
- Comparative experiment: GCNN clearly dominates solving time overall, except on combinatorial auction Easy and maximum independent set Medium, where LMART and RPB are faster, respectively.Solving time reflects both search-tree size and each policy’s feature-extraction and inference cost.
- Comparative experiment: GCNN generalizes to larger-than-training instances and outperforms SCIP’s RPB in running time in almost every configuration.It significantly outperforms RPB in node counts on medium and hard set-covering and combinatorial-auction instances, while maximum independent set remains challenging.
- Ablation study: On large set-covering instances, mean- and sum-convolution variants without the full architecture perform significantly worse in solving time and node counts, especially on hard instances.The ablation compares MEAN, SUM without prenorm, and GCNN with sum convolutions plus prenorm; the evidence supports the latter architectural combination for generalization.
6 Discussion
The proposed branching policy must balance decision quality against inference cost, and its ability to generalize declines as instances become progressively larger. The authors therefore frame both computational efficiency and transfer beyond the training distribution as practical boundaries.
- Efficiency trade-off: Larger GCNNs made better decisions and slightly reduced node counts, but their higher inference costs increased average solving times.The selected architecture compromises between learning capacity and inference speed.
- Generalization: GCNN policies generalized to fairly larger instances, but improvements generally decreased as evaluated problems grew beyond training sizes.The paper reports a performance drop on huge instances when training used small instances.
- Generalization: Training on medium instances restored good performance on huge instances, indicating that transfer depends on the scale and structure of the training distribution.The authors state that generalization limits are dependent on problem structure and difficult to quantify a priori.
7 Conclusion
The paper represents branch-and-bound branching as graph-based decision-making and evaluates imitation-learned GCNN policies on four NP-hard problems. These policies outperform prior machine-learning branching approaches, also surpass SCIP’s default strategy, and generalize beyond training sizes.
- Conclusion: The authors formulate branch-and-bound as a Markov decision process and represent each MILP state as a variable-constraint bipartite graph.This representation naturally leverages MILP structure and reduces feature engineering.
- Conclusion: Simple imitation learning produces GCNN branching policies that outperform previously proposed machine-learning approaches on four NP-hard problems.The learned policies also outperform SCIP’s default branching strategy.
- Conclusion: The learned policies generalize to instance sizes larger than those seen during training.This matters because collecting strong-branching decisions for large training instances can be computationally prohibitive.
- Future work: Future work includes broader problem coverage, reinforcement learning, hybrid traditional-machine-learning branching, and analysis of learned policies.These directions are stated as proposed future investigations.
Supplementary Materials
The supplementary-material passage identifies the paper as arXiv version 3, dated 30 October 2019, and lists Andrea Lodi’s affiliation with Polytechnique Montréal.
- Publication metadata: The paper is identified as arXiv:1906.01629v3.The identifier appears with the computer-science machine-learning classification.
- Publication metadata: This version is dated 30 Oct 2019.The date is given in the arXiv header.
- Author affiliation: Andrea Lodi is affiliated with Polytechnique Montréal.The affiliation is listed directly beneath the author name.
1 Dataset collection details
The dataset collection uses randomly generated benchmark instances solved with SCIP to record state-action pairs and strong-branching decisions. The collection is designed to obtain 100,000 training samples, with solve counts distinguished from unique instances because sampling uses replacement.
- Instance generation: The study generates 10,000 training, 2,000 validation, and 3×20 test instances for each of four benchmark problems.The benchmarks are set covering, combinatorial auction, capacitated facility location, and maximum independent set.
- State-action collection: SCIP solves sampled instances with varying random seeds while recording branch-and-bound node states and strong-branching decisions.These records form state-action pairs for training and validation.
- Collection accounting: 100,000 training samples are obtained through SCIP solves, and the table reports both total solves and unique instances.Instances are sampled with replacement, so these counts differ.
- Oracle construction: The strong-branching rule is reimplemented as vanillafullstrong to provide oracle decisions without solver side effects.The vanilla implementation also facilitates extraction of strong-branching scores for training.
2 Training details
The paper trains GCNN and baseline branching models from strong-branching decisions represented over MILP structure, using distinct supervised objectives and feature constructions. Computational constraints required limiting competitor datasets, while the GCNN uses scalable deep-learning training.
- GCNN: GCNN training records strong-branching decisions and bipartite state representations during branch-and-bound, producing state-action pairs for imitation learning.The model is implemented in TensorFlow, with prenorm-layer pretraining followed by cross-entropy optimization using Adam.
- GCNN: The GCNN state is a bipartite representation containing constraint, edge, and variable features.The feature inventory is described in Table 2.
- SVMrank and LambdaMART: SVMrank and LambdaMART learn from strong-branching ranks using variable-wise features and ranking-oriented training procedures.The approaches use query-based feature normalization and binarized ranking labels around the 80th centile; SVMrank uses a pairwise loss, while LambdaMART maximizes normalized discounted cumulative gain.
- Training constraints: Competitor training on the full dataset was prohibitive, requiring limits of 250,000 candidate variables for training and 100,000 for validation.The stated bottleneck was poorer training scalability than stochastic-gradient-descent deep neural networks, including memory and training-time demands.
- ExtraTrees: ExtraTrees learns to predict strong-branching scores from variable features combined with neighborhood summaries of edge and constraint features.At test time, branching selects the variable with the highest predicted score.
3 When are decisions hard for the GCNN policy?
GCNN uncertainty tracks strong-branching uncertainty: decisions with higher policy entropy tend to be decisions where the expert also hesitates. This indicates that GCNN hesitation corresponds to intrinsically difficult branching decisions.
- Confidence and decision difficulty: Entropy at every decision point on easy instances roughly correlates between the GCNN policy and strong branching across four problems.Strong-branching entropy is defined as log m, where m is the number of candidates tied for the maximal strong-branching score.
- Confidence and decision difficulty: GCNN hesitation occurs on decisions where strong branching also hesitates, suggesting these decisions are intrinsically difficult.The comparison extends beyond imitation-learning accuracy to the confidence of the learned policy.
4 Training set sizes for the machine learning methods
The proposed GCNN benefits from larger training datasets than competing machine-learning methods, but its performance improvement decreases on progressively larger test instances. A matched-data GCNN still outperforms competitors, separating the method’s advantage from dataset size alone.
- Training-set scalability: Competitor training on the full dataset was impossible under the reported computational constraints, whereas the GCNN could use more training data with the same budget.The paper identifies this scalability difference as a major advantage of the proposed deep policy.
- Training-set sizes: The complete GCNN dataset contains 100,000 training and 20,000 validation branching nodes, compared with competitor datasets of 250,000 training and 100,000 validation variable-score pairs.Table 3 reports the corresponding state-action-node counts used to obtain competitor samples.
- Matched-data comparison: GCNN-SMALL, trained with 250,000 candidate variables for training and 100,000 for validation, still clearly outperforms competitors in imitation-learning accuracy.The result shows that GCNN improvements cannot be explained only by using more training samples, although additional samples improve performance.