DeepMind & Google Use Neural Networks to Solve Mixed Integer Programs

Linear programming is used to maximize or minimize a linear objective function subject to one or more constraints, while mixed integer programming (MIP) adds one additional condition: that at least one of the variables can only take on integer values. MIP has found broad use in operational research and practical applications such as capacity planning and resource allocation.

In the new paper Solving Mixed Integer Programs Using Neural Networks, a team from DeepMind and Google Research leverages neural networks to automatically construct effective heuristics from a dataset of MIP instances. The novel approach significantly outperforms classical MIP solver techniques, demonstrating especially impressive improvements on the state-of-the-art SCIP (Solving Constraint Integer Programs) 7.0.1 solver.

A compelling use case for the proposed techniques is when applications have to solve a large set of instances of the same high-level semantic problem with different problem parameters. Most traditional off-the-shelf MIP solvers are unable to exploit shared structures among MIP instances, and therefore must rely on experts to hand-design heuristics. The research community has long-believed in machine learning’s potential to realize significant improvements in this regard, i.e. without requiring any application-specific expertise.

Inspired by this idea, the DeepMind & Google team constructed two corresponding neural network-based components — neural diving and neural branching — for the automatic construction of dataset heuristics. The proposed approach applies learning to two key sub-tasks of an MIP solver: outputting an assignment of values to all variables that satisfy the constraints, and proving a bound for the gap in objective values between a given assignment and an optimal one.

The neural diving component is designed to find high-quality joint variable assignments. The team trains a deep neural network to produce multiple partial assignments of the integer variables of an input MIP. The model is trained to assign a higher probability to feasible assignments with better objective values, and learns on all available feasible assignments. This eliminates the need for optimal assignments, which can be computationally expensive to collect.

Neural branching, meanwhile, is mainly used to bound the gap between an objective value of the best assignment and an optimal one. The team trains a deep neural network policy to imitate choices made by an expert policy. Once trained, the neural networks can approximate the expert with a lower cost at test time.

The team evaluated their approach on a diverse set of datasets containing large-scale MIPs from real-world applications, including datasets from Google’s production systems as well as the standard heterogeneous dataset benchmark MIPLIB.

In evaluations on solvers with respect to primal-dual gap averaged over a held-out set of instances at large time limits, SCIP augmented with the proposed approach achieved 1.5×, 2×, and 104× better gaps on three out of the five tested datasets with the largest MIPs, was 10 percent gap 5× faster on the fourth dataset, and matched SCIP performance on the fifth.

The researchers say theirs is the first learning approach to demonstrate such large improvements over SCIP on both large-scale real-world application datasets and MIPLIB. They have also open-sourced a dataset for the application of neural network verification to assist with further research in this field.

The code is available on the project GitHub. The paper Solving Mixed Integer Programs Using Neural Networks is on arXiv.

---

Author: Hecate He | Editor: Michael Sarazen, Chain Zhang

---

We know you don’t want to miss any news or research breakthroughs. Subscribe to our popular newsletter Synced Global AI Weekly to get weekly AI updates.