REVIEW 9 cited by
Solving Mixed Integer Programs Using Neural Networks
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
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.
Forward citations
Cited by 9 Pith papers
-
CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees
A verification layer around learned pruning of NP-hard problems yields prediction-independent worst-case guarantees and PAC-learnable parameters.
-
GraphBU: MILP Instance Generation with Graph-Native Block Units
GraphBU generates MILP instances via graph-native block units that pair local subproblems with explicit coupling interfaces, achieving high structural similarity and feasibility preservation across four MILP families.
-
A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention
A dual self- and cross-attention backbone learns MILP variable and constraint embeddings and outperforms GNN baselines in feasibility, solution, and branching prediction tasks.
-
Machine Learning Guided Optimal Transmission Switching to Mitigate Wildfire Ignition Risk
A domain-informed Predict-and-Search + Neural Diving method finds near-optimal power-line de-energization decisions for wildfire risk in 30 minutes, cutting the primal integral by 30.9% relative to Gurobi on 54 hard C...
-
A parallel algorithm for generating Pareto-optimal radiosurgery treatment plans
ADMM parallelized across objective weights generates hundreds of Gamma Knife plans on a GPU in under two minutes, with clinical metrics matching the sequential simplex solver.
-
SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs
SPL-LNS replaces the greedy proposal step in neural Large Neighborhood Search with sampling over locally-informed proposals, trained by hindsight relabeling on self-generated data, and reports large gains over prior n...
-
Improving Full Strong Branching Decisions by Incorporating Additional Information
Modified strong branching scores that cap estimated LP gains at the primal-dual gap and re-weight branches based on leaf asymmetry reduce branch-and-bound tree sizes on MIPLIB 2017 instances.
-
Self-Improving Neural Pruning: A Graph Neural Network Framework for Scalable Mixed Bundle Pricing
A GNN-guided pruning framework predicts customer-product assignment probabilities and solves a restricted mixed-bundling MILP, reporting 97-99% of optimal revenue on small instances and faster large-scale solutions.
-
STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization
STRCMP's GNN-plus-LLM code search for MILP and SAT heuristics does not consistently beat AutoSAT in the paper's own reported numbers.
Discussion (0). Continue with ORCID to comment.