Solving Mixed Integer Programs Using Neural Networks
Date8th Apr 2021
Time03:00 PM
Venue Google Meet (see link).
PAST EVENT
Details
Mixed Integer Programs (MIPs) are a class of NP-hard discrete optimization problems where the goal is to optimize a linear objective function subject to linear constraints, with some or all of the variables constrained to be integer-valued. MIP solvers rely on an array of sophisticated heuristics developed with decades of research. Machine learning offers to automatically construct better heuristics from data by exploiting shared structure among MIP instances in the data. In this work we apply learning to the two key sub-tasks of a MIP solver: 1) generating a high-quality joint variable assignment, and 2) bounding the gap in objective value between that assignment and an optimal one. We evaluate our approach on diverse real-world datasets, including two Google production datasets and the standard benchmark MIPLIB, by training separate neural networks on each. Most MIP instances have 10^3 − 10^6 variables and constraints, which is significantly larger than instances handled by previous learning approaches. Our approach outperforms the state-of-the-art non-commercial solver SCIP at large time limits. To the best of our knowledge, ours is the first learning approach to demonstrate improvements over SCIP on both large-scale real-world application datasets and MIPLIB. Additional details can be found in https://arxiv.org/abs/2012.13349.
Speakers
Vinod Nair
Computer Science and Engg.