A Neural Network Approach for Integer Programming Duality
Abstract
Duality is perhaps the most fundamental concept in optimization. While linear and convex programming duality are extremely well understood and essential for modern algorithms, much less is known about integer programming (IP) duality. It has been shown that the value function of a maximization IP can be characterized as a Gomory function, meaning that it can be constructedrecursively from a set of linear functions through the composition of addition, nonnegative multiplication, minimization, and rounding down operations. Despite its elegance, this fundamental result has had a surprisingly limited impact on IP theory or practice.In recent years, Machine Learning (ML) has become increasingly popular ahis space focuses on learning policies to make algorithmic decisions in an optimization algorithm or directly estimating the solution of an IP from its input parameters. The oft-overlooked characterization of the value function exposes fundamental similarities between neural networks and Gomory functions. Thisproposal will study the IP value function, its relationship with deep learning, and use it to develop algorithms for stochastic (mixed-)integer programs that will pave the way in the future for effective methods for other challenging problems. We aim to build on the incredible success of the reinforcement learning community in modeling value functions with deep learning models.Our investigation into ML approaches to IP duality will raise important theoretical questions, incations and their IP duals. We will study important computational aspects as well, such as the design of network architecture, optimizing over trained neural networks, and evaluating goodness-of-fit. There are many classes of difficult discrete optimization problems that are amenable to IP duality approaches. We will focus on IP dual approaches to stochastic integer programming (SIP) and stochastic mixed-integer programming (SMIP), and investigate how ML can be leveraged for algorithmic development.While this proposal will focus on general classes of discrete optimization problems (e.g., stochastic integer programs), a successful ML approach to IP duality (and generalizations) will lead to a more powerful and efficient way of decomposing difficult discrete optimization problems arising in various contexts. It will also have direct practical impact through a simpler approach to sensitivityanalysis. The proposed work will help facilitate these directions through articles in high-quality journals and well-engineered software tools.The first thrust of the proposed work will focus on theoretical analysis, studying the neural network representability of IP value functions. In particular, we will seek to derive theoretical results to help us understand how well neural networks can model IP value functions. The second thrust of the proposed work will focus on algorithm design for producing good neural network approximations for unknown IP value functions. This endeavor will include development of efficient, well-tested, and well-documented software libraries for fitting neural network approximations to value functions from observed data. We will next study natural extensions of the work into SIP and SMIP. While these models have multiple applications in a variety of fields(e.g., healthcare, energy, capacity planning, etc.), they remain computationally challenging. Value function reformulations for SIPs and SMIPs will allow for the development of new and efficient solution algorithms that will both contribute to the theory linking combinatorial optimization and machine learning, and expand the practical adoption of those models.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Apr 06, 2021
- Source ID
- N000142112262
Entities
People
- Andrew Schaefer
Organizations
- Office of Naval Research
- Rice University
- United States Navy