Solving Mixed Integer Programs Using Neural Networks

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.

References in corpus (11)

• Auto-Encoding Variational Bayes
• Semi-Supervised Classification with Graph Convolutional Networks
• Learning Combinatorial Optimization Algorithms over Graphs
• Representation Learning on Graphs with Jumping Knowledge Networks
• ParamILS: An Automatic Algorithm Configuration Framework
• Evaluating Robustness of Neural Networks with Mixed Integer Programming
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Attention, Learn to Solve Routing Problems!
• Reinforcement Learning for Integer Programming: Learning to Cut
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs

Cited by in corpus (19)

• The Transformer Network for the Traveling Salesman Problem
• A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP
• Learning Hard Optimization Problems: A Data Generation Perspective
• Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
• Single-pass Object-adaptive Data Undersampling and Reconstruction for MRI
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• Learning Large Neighborhood Search Policy for Integer Programming
• Data-Driven Demand-Side Flexibility Quantification: Prediction and Approximation of Flexibility Envelopes
• Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs
• Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming
• Persistent Message Passing
• Machine Learning Assisted Approach for Security-Constrained Unit Commitment
• Learning Primal Heuristics for Mixed Integer Programs
• Learning to Schedule Heuristics in Branch-and-Bound
• Neural Fixed-Point Acceleration for Convex Optimization
• Array Placement in Distributed Massive MIMO for Power Saving considering Environment Information
• Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks
• Clustering Plotted Data by Image Segmentation
• Simplex Initialization: A Survey of Techniques and Trends