PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving Mixed Integer Programs Using Neural Networks

Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, Yori Zwols

arXiv:2012.13349v3math.OCcs.AIcs.DMcs.LGcs.NE

TL;DR

MIP solving depends on heuristics suited to each application, motivating machine-learning methods that construct heuristics from datasets of MIP instances. The paper combines Neural Diving and Neural Branching with SCIP, reporting large improvements over SCIP on large-scale real-world datasets and MIPLIB.

  • Problem

    MIP applications depend crucially on how well their heuristics suit the application, while machine learning can construct effective heuristics from datasets of MIP instances.

  • Method

    The paper combines Neural Diving for high-quality joint variable assignments with Neural Branching, using a scalable Full Strong Branching variant.

  • Results

    3× and 3.6× less time: Neural Diving with parallel sub-MIP solving reaches 1% average primal gap than the compared approach.

  • Takeaways & Limitations

    The approach demonstrates large improvements over SCIP on both large-scale real-world application datasets and MIPLIB.

  • Takeaways & Limitations

    Full Strong Branching is often too computationally expensive for practical MIP solving, and CPU-based implementations can be too expensive on large-scale MIPs even for offline data generation.

Abstract

from arXiv · show

Mixed Integer Programming (MIP) solvers rely on an array of sophisticated heuristics developed with decades of research to solve large-scale MIP instances encountered in practice. Machine learning offers to automatically construct better heuristics from data by exploiting shared structure among instances in the data. This paper applies learning to the two key sub-tasks of a MIP solver, generating a high-quality joint variable assignment, and bounding the gap in objective value between that assignment and an optimal one. Our approach constructs two corresponding neural network-based components, Neural Diving and Neural Branching, to use in a base MIP solver such as SCIP. Neural Diving learns a deep neural network to generate multiple partial assignments for its integer variables, and the resulting smaller MIPs for un-assigned variables are solved with SCIP to construct high quality joint assignments. Neural Branching learns a deep neural network to make variable selection decisions in branch-and-bound to bound the objective value gap with a small tree. This is done by imitating a new variant of Full Strong Branching we propose that scales to large instances using GPUs. We evaluate our approach on six diverse real-world datasets, including two Google production datasets and MIPLIB, by training separate neural networks on each. Most instances in all the datasets combined have $10^3-10^6$ variables and constraints after presolve, which is significantly larger than previous learning approaches. Comparing solvers with respect to primal-dual gap averaged over a held-out set of instances, the learning-augmented SCIP is 2x to 10x better on all datasets except one on which it is $10^5$x better, at large time limits. To the best of our knowledge, ours is the first learning approach to demonstrate such large improvements over SCIP on both large-scale real-world application datasets and MIPLIB.

1. Introduction

The paper learns dataset-customized MIP heuristics for two solver sub-tasks: generating high-quality feasible assignments and bounding their objective gap. Neural Diving and Neural Branching are integrated with SCIP, producing substantially better performance on large MIP datasets.

  • Motivation: MIP solvers’ heuristic effectiveness depends strongly on how well heuristics suit each application, while conventional solvers do not automatically exploit cross-instance structure.Machine learning can construct customized heuristics from datasets, reducing reliance on hand-designed, application-specific expertise.
  • Approach: Neural Diving generates multiple partial integer assignments, then uses SCIP to solve smaller sub-MIPs and complete high-quality joint assignments.The model learns from feasible assignments, not only optimal ones, which may be less expensive to collect.
  • Approach: Neural Branching learns to imitate Full Strong Branching’s variable choices, using a GPU-scalable ADMM variant to generate training data for large MIPs.The trained policy approximates the expert at a fraction of the computational cost during testing.
  • Results: On four of five datasets with the largest MIPs, the combined Neural Solver achieves a significantly better gap or the same gap in less time than Tuned SCIP, matching it on the fifth.The evaluation covers diverse real-world datasets, including two Google production systems, and MIPLIB.
  • Contribution: The work combines learned primal and branching heuristics in a solver and reports large improvements over SCIP on large-scale application datasets and MIPLIB.This extends beyond earlier studies of individual learned heuristics in isolation.

2. Integer programming background

Mixed integer programs optimize variables subject to linear constraints, with some variables required to be integer. Solvers use LP relaxations, primal bounds, dual bounds, and branch-and-bound heuristics to find near-optimal solutions and certify progress.

  • Problem formulation: A mixed integer linear program optimizes x ∈ R^n subject to linear constraints, with integer restrictions on variables indexed by I.The model includes coefficient matrix A, right-hand side b, objective coefficients c, and lower and upper bounds l and u.
  • Assignments: A complete assignment fixes every variable, while a partial assignment fixes only some; feasibility requires satisfying all problem constraints, and optimality additionally minimizes the objective.
  • Linear programming relaxation: Removing integrality yields an efficiently solvable convex LP relaxation whose optimal value is a lower bound on the original MIP objective.If the LP optimum is integral, it is also optimal for the original problem; this lower bound is called a dual bound.
  • Branch-and-bound: Branch-and-bound recursively branches on fractional integer variables, creating child nodes with domains constrained above or below the floor and ceiling of the LP value.LP relaxations provide node bounds used to prune subtrees that cannot improve a known feasible assignment.
  • Branch-and-bound: Search trees can be exponentially large, motivating node-selection and variable-selection heuristics that keep the tree small.Branch-and-bound repeatedly selects a leaf, solves its LP relaxation, and either prunes it or branches on a variable.
  • Primal heuristics: Primal heuristics seek feasible, not necessarily optimal, assignments that provide upper bounds and can enable additional branch-and-bound pruning.Examples include rounding and diving, which explore the search process to find feasible solutions.
  • Primal-dual gap: The solver tracks global primal and dual bounds to form a nonnegative sub-optimality gap, terminating when the relative gap is sufficiently small.A zero gap certifies optimality, while practical termination may return the best found primal solution as approximately optimal.
  • Neural-network representation: A MIP can be represented as a bipartite graph whose two node sets correspond to variables and constraints, with coefficients encoded as node and edge features.

3. MIP Representation and Neural Network Architecture

The paper represents MIPs as bipartite graphs and processes them with graph convolutional networks (GCNs) to support Neural Diving and Neural Branching. The architecture preserves permutation invariance and applies across MIPs of different sizes.

  • MIP representation: MIPs are represented as bipartite graphs whose variable and constraint nodes are connected when variables appear in constraints.Edges correspond to nonzero constraint-matrix entries; objective coefficients, constraint bounds, edge coefficients, and variable types provide features.
  • Shared architecture: The same GCN-based framework is used to learn models for both Neural Diving and Neural Branching.The two components differ in their outputs and loss functions while sharing common architectural elements.
  • GCN architecture: A GCN processes node features and graph connectivity to produce node embeddings for downstream prediction tasks.Each layer applies an MLP to node features and aggregates neighboring outputs through the adjacency matrix; later layers can feed a task-specific MLP.
  • Architectural properties: The network output is invariant to permutations of variables and constraints and can process MIPs with different numbers of variables and constraints.These properties address the lack of canonical ordering and variation in instance size within an application.
  • Architectural modifications: The architecture modifies standard GCNs by using constraint coefficients as edge weights, concatenating earlier embeddings through skip connections, and applying layer normalization.Alternative edge-embedding architectures may require more GPU memory and fewer layers, making GCNs better suited to large-scale MIPs.

4. Datasets

The evaluation uses application-specific MIP datasets and MIPLIB, with disjoint training, validation, and test sets. The instances span substantially different sizes, including large presolved problems.

  • Dataset composition: The datasets comprise application-specific collections plus MIPLIB, which aggregates instances from many applications.MIPLIB is included as an established solver benchmark despite being less representative of the within-application setting targeted by learning.
  • Dataset splits: The application datasets are randomly split into disjoint 70% training, 15% validation, and 15% test subsets.For MIPLIB, the 2017 Benchmark Set is used for testing, while the 2017 Collection and 2010 sets provide training and validation data after overlap removal.
  • Evaluation protocol: Training data learn dataset-specific models, validation data tune learning and SCIP parameters, and test data provide evaluation results.The test sets are kept separate from training to assess generalization to unseen instances.

5. Evaluation

The evaluation compares Neural Diving, Neural Branching, their combination, and tuned SCIP on disjoint test instances using primal-dual gap and survival analyses over calibrated running time. Timing calibration reduces measurement variability on heterogeneous hardware.

  • Evaluation design: The study evaluates Neural Diving and Neural Branching separately and jointly on test MIPs disjoint from the training data.Results aggregate instance-seed pairs, using five SCIP random seeds for each instance.
  • Metrics: Performance is measured with primal, dual, and primal-dual gaps as functions of solving time, alongside survival plots for target gaps.The best known primal bound is precomputed using default SCIP with a 24-hour limit, and any later improvement updates prior gaps.
  • Timing methodology: Calibrated time estimates runtime using repeated small calibration-MIP solves on the same machine, reducing sensitivity to hardware heterogeneity and interference.The evaluation workload exceeds 160,000 MIP solves and nearly one million CPU and GPU hours.
  • Timing results: Calibration reduced the coefficient of variation of time measurements by 1.5× to 30× on four MIPLIB instances compared with wall-clock timing.This comparison is reported for the calibration procedure used to make runtime measurements more comparable.
  • Baseline: The principal baseline is SCIP 7.0.1 with dataset-specific tuning over 64 combinations of presolving, primal-heuristic, and cut settings.The selected configuration minimizes average primal-dual gap on 200 validation MIPs within a three-hour limit.

6. Neural Diving

Neural Diving learns distributions over integer-variable assignments and samples multiple partial assignments that define smaller sub-MIPs, which SCIP solves to obtain feasible solutions. Its conditional-independence approximation performs well empirically but cannot represent multimodal assignment distributions accurately.

  • Learning assignments: Neural Diving trains a generative model from feasible assignments found by SCIP and uses its predictions on unseen MIPs from the same distribution.The collected assignments need not be optimal, and data collection occurs once per application outside the training loop.
  • Neural Diving procedure: The model’s uncertainty defines multiple partial assignments that fix many integer variables, leaving smaller sub-MIPs for SCIP to solve.This produces high-quality feasible assignments while combining learned predictions with exact MIP solving on the remaining variables.
  • Relation to diving: Unlike regular diving, Neural Diving starts at the root, descends only partially, and solves the remaining sub-MIP instead of reaching a leaf sequentially.The vanilla method defines assignments in parallel and re-solves the linear program once.
  • Relation to neighborhood search: Compared with RENS, Neural Diving predicts fixed variable values with a learned model and uses multiple partial assignments rather than one.This gives the method a hybrid character combining diving and neighborhood search.
  • Model limitations: The conditionally independent model cannot accurately represent multimodal assignment distributions, although it shows strong empirical performance.Autoregressive alternatives provide modest improvements but incur substantially higher inference cost.
  • General integer variables: For general integer variables, bit-wise prediction can tighten bounds by at least 2^n_b−1 or predict a value exactly when ⌈log2(card(z))⌉≤n_b.The approach also interprets bit-wise value prediction as predicting branching decisions.

6.2. Combining Model Predictions with a Classical Solver

Neural Diving samples partial variable assignments, selectively fixes or tightens variables, and delegates the remaining sub-MIPs to SCIP. Multiple independently solved sub-MIPs support parallel or sequential search for a high-quality feasible solution.

  • Generating partial assignments: Neural Diving samples assignments x from pθ(x|M) and uses a classifier to decide which variables receive predictions.The acceptance head selects variables to fix or tighten, while the prediction head supplies their values.
  • Generating partial assignments: Coverage is the ratio of predicted to unpredicted variables, controlled by a threshold C and penalty hyperparameter λ.Models are trained with multiple coverage thresholds, typically ranging from 0.1 to 0.95.
  • Combining predictions with SCIP: Fixing or tightening many variables reduces problem size, moves search toward promising regions, and lets SCIP solve smaller sub-MIPs.The method can remove some assignments to expand the neighborhood before solving for the remaining open variables.
  • Combining predictions with SCIP: Multiple samples and coverage models generate diverse sub-MIPs whose best feasible objective is reported for the original MIP.Each sub-MIP can be solved independently, enabling distributed computation for a single instance.
  • Experimental settings: Parallel Neural Diving can generate up to 100 sub-MIPs and reports calibrated wall-clock time using the best-performing sub-MIP at each time.Sequential experiments process the same sub-MIPs in random order while controlling total computational resources.

6.3. Results

Neural Diving is evaluated against tuned SCIP using primal-gap curves and survival plots, including experiments on open MIPLIB instances. It generally finds strong primal bounds quickly, but may not sustain that advantage at long time limits.

  • Benchmark results: Neural Diving’s parallel and sequential runs produce better primal bounds in shorter time than SCIP across all evaluated datasets.The reported comparison uses average primal gap versus the baseline SCIP configuration.
  • Benchmark results: Neural Diving wins at shorter time limits but loses to SCIP at the end on Electric Grid Optimization and MIPLIB.The authors attribute its strength to quickly finding good solutions, while noting occasional failure to find optimal or near-optimal solutions.
  • Open MIPLIB instances: The open MIPLIB set is almost entirely heterogeneous, with only a handful of related instances available per problem.This heterogeneity creates an additional challenge for the learning-based approach.
  • Open MIPLIB instances: For three open MIPLIB instances, Neural Diving produced new incumbents with improved objective values over the previous best known solutions.Open instances have no known optimal solution or lack a feasible incumbent matching any known dual bound.

7. Neural Branching

Neural Branching learns local variable-selection decisions from an expensive expert policy, aiming to preserve small branch-and-bound trees while reducing decision cost. A GPU-batched ADMM solver makes expert data generation more scalable on large instances.

  • Neural Branching: Neural Branching learns a variable-selection policy by imitating a node-efficient but computationally expensive expert.The learned policy uses a local representation of the current branch-and-bound node rather than the entire tree.
  • Expert branching policy: Full Strong Branching evaluates candidate variables through one-step lookahead, solving 2 × n_cands linear programs per branching step.It combines the resulting LP values into candidate scores and selects a branching variable.
  • Expert branching policy: Full Strong Branching is often usable for only a few steps because its per-step computational cost becomes prohibitively high.SCIP therefore uses it initially before switching to a lower-cost heuristic.
  • ADMM batch LP solving: A GPU-batched ADMM solver simultaneously handles many related LPs, approximately solving full strong-branching LPs faster than sequential CPU execution.The authors wrote the batch solver because SOPLEX processes these LPs sequentially on CPU.
  • Imitation learning: The learned policy produces actions close enough to the ADMM expert to yield small search trees at a fraction of the computational cost.The appendix reports accurate approximation of the expert policy on both training and test sets.
  • Expert data generation: 31.7× and 1.6× more data on the largest-variable nodes, ADMM outproduces VFSB for Google Production Packing and MIPLIB, respectively.Across the full variable-count range, the corresponding increases are 12.1× and 1.4×.
  • Results: Neural Branching achieves significantly smaller average dual gaps at equal running time on four of six datasets and remains comparable on MIPLIB and Google Production Planning.At large time limits, it is about 7× better on CORLAT, 20× on Neural Network Verification, and 2× on Electric Grid Optimization.

8. Joint Evaluation

The joint solver combines Neural Branching and Neural Diving with SCIP in sequential and resource-controlled configurations. Across diverse datasets, the neural solver often reaches lower primal-dual gaps or solves more instances sooner than tuned SCIP.

  • Evaluation design: The evaluation compares tuned SCIP, both neural heuristics, Neural Branching alone, and tuned SCIP combined with sequential Neural Diving.When sequential Neural Diving is used, SCIP’s built-in primal heuristics are disabled.
  • Evaluation design: The sequential neural solver uses two CPU cores and two GPUs, while tuned SCIP receives two CPU cores and no GPUs.The comparison does not control for GPU resources because SCIP does not use GPUs.
  • Results: A neural solver solves a higher fraction of test problems at a given time than tuned SCIP on four datasets.The results are presented with average primal-dual gap curves and survival plots over calibrated running time.
  • Results: 2× lower gap on Electric Grid Optimization and 1.5× better gap on MIPLIB, the combined configurations improve over tuned SCIP at higher running times.The Google Production Packing advantage is primarily earlier in the run, whereas tuned SCIP later catches up.
  • Conclusion: The improvements occur across different problem scales and applications, including heterogeneous MIPLIB instances.The authors report this as evidence that learning improves a strong solver such as SCIP across diverse settings.

9. Related Work

Prior work applies learning to primal heuristics, branching, solver configuration, and combinatorial optimization, while this paper emphasizes broader MIP coverage and scalable evaluation.

  • Learning and MIP Primal Heuristics: Learned primal heuristics have been used to switch among existing heuristics, modify feasible assignments, or predict variable values for solver warm starts.Several approaches require a feasible assignment, restrict attention to binary variables, or assume fixed problem structure.
  • Learning and MIP Primal Heuristics: Neural Diving differs by constructing an application-specific primal heuristic without requiring a feasible assignment as input.The paper positions Neural Diving as useful when existing heuristics are poorly suited to an application.
  • Learning and MIP Branching Heuristics: Earlier branching studies imitate Full Strong Branching using handcrafted features or models, but did not report current state-of-the-art results for learned policies.Neural Branching builds on graph-based imitation learning while changing the expert-scaling and evaluation setup.
  • Learning and MIP Branching Heuristics: This work uses an ADMM-based expert to scale Full Strong Branching to large instances and evaluates learned branching on real-world applications.The paper identifies these as major differences from earlier learned branching approaches.
  • Other Learning Approaches for MIP Solvers: Algorithm configuration and selection learn solver parameters or predict solver performance, and these techniques can complement application-specific heuristic learning.Related work includes SMAC, which evaluates parameter settings, models performance, and selects new candidates.
  • Learning for Combinatorial Optimization: Learning for combinatorial optimization spans routing, satisfiability, graph-structured problems, and other domains beyond MIP solving.The paper situates its approach within this broader research area and cites a survey of the topic.

10. Conclusion

The paper concludes that machine learning can substantially improve MIP solver performance, while noting data scarcity and reinforcement-learning challenges as directions for further gains.

  • Conclusion: Machine learning can significantly improve the performance of a strong MIP solver such as SCIP.The conclusion frames the work as evidence for the long-held promise of learning-based MIP improvements.
  • Conclusion: Heterogeneous datasets can provide a bridge to specialized models when an application has too little data to train strong models directly.The proposed progression starts with models trained across heterogeneous problems and specializes them as application data accumulates.
  • Conclusion: Behavioral cloning or distillation is capped by the best available expert, whereas reinforcement learning may exceed that expert.The paper identifies efficient exploration, long-range credit assignment, and computational scalability as major RL challenges for large-scale MIPs.
  • Conclusion: Further model and algorithm advances could produce larger performance improvements, including through reinforcement learning and learned cutting procedures.The paper presents learning to cut and warm-starting models as future directions.

12. Appendix

The appendix examines autoregressive Neural Diving, Neural Branching fidelity, ADMM-based batching, calibrated timing, and additional dataset and evaluation details.

  • 12.1. Autoregressive Models for Neural Diving: Autoregressive Neural Diving improves average primal gap and optimal-solution counts, but increased sampling time outweighs most gains because assignments are no longer sampled in parallel.These results are preliminary and are presented on the Google Production Packing dataset.
  • 12.1. Autoregressive Models for Neural Diving: No universal canonical variable ordering works well for all MIPs, so ordering is treated as a hyperparameter selected during sweeps.Candidate orderings include input, objective-coefficient, and fractionality orderings; fractionality performed best empirically for autoregressive models.
  • 12.3. Neural Branching: The learned branching policy closely matches the expert on training and test sets and generalizes well to unseen instances.Its performance is much closer to the expert policy than to a uniformly random policy.
  • 12.5. ADMM Batch LP Solver: Batching produces an average speedup of approximately 800× across instances, with larger MIPs typically yielding larger speedups.The appendix attributes the broad speedup to solving many LP-related computations together on the GPU.
  • 12.5. ADMM Batch LP Solver: The ADMM batch LP solver computes 12.2k branch scores at roughly ten times one solve, yielding an approximately 1200× speedup over sequential LP solving.The batching strategy enables large-scale expert scoring that would otherwise be impractical.
  • 12.7. Details of Calibrated Time: Calibrated time reduces coefficient of variation versus wall-clock measurements by about 30×, 8.3×, 7×, and 1.5× on four MIPLIB instances.The reductions are reported for air05, n5-3, swath1, and dano3 3, respectively.
Loading 2012.13349v3…