New Methods for Stochastic Integer Programming: Exploiting Connections to Machine Learning
Abstract
Stochastic integer programming (SIP) is a mathematical optimization tool that considersproblems in which many discrete decisions must be made under conditions of uncertainty in system parameters. Problems with discrete decisions have incredibly wide applicabilitynificant uncertainties such as future resource requirements, machine failures, or adversary actions, providing immense challenge for design, planning, and operation of such systems. Unfortunately, despite its potential for improving decision-making in such uncertain settings, SIP has not been adopted nearly as widely as deterministic IP. There are two primary causes of this: (1) historically, it has been difficult to construct sufficiently accurate models for the random variables in SIP models, and (2) currently available recent surge in availability of data and advances in ML methodologies for using this data to make predictions. Thus, the goal of this project is to overcome the second limitation by advancing general-purpose methods for solving SIP problems to make them as routinely solvable as deterministic IP problems currently are. This goal will be achieved with three main thrusts. First, motivated by the observation that all state-of-the-art SIP algorithms require solving a large number of closely related deterministic IPsubproblems, we will explore techniques to harness the power of ML to learn good algorithmic choices for solving these subproblems, leading to dramatically reduced solution times. This thrust will build on recent research using ML to learn algorithmic choices for deterministic IP problems, but will necessarily adapt and extend this work to the SIP setting in which it is required to learn how to predict good choices given the parameters of the subproblem. Second, we will explore new techniques for strengthening the relaxation of a SIP problems. One key observation driving this thrust is that strong cuts can be generated for problems with small dimension, and this observation can be extended to higher-dimensional problems provided the cuts used to define the masterproblem are sparse. In our final thrust we will investigate the use of neural networks to define dual functions of multistage SIP problems. Using this general class of functions has the potential to create significantly better bounds on the optimal value of such problems, which can then ultimately be used to find better decision policies, together with guarantees on the quality of the policy. This project will lead to a set of mathematical and algorithmic tools that decision-makers can use to manage risk while making discrete decisions when designing, planning, and operating systems in an uncertain environment. By providing new general-purpose tools for solving SIP problems, this project will enable translation of the emerging abundance of data into improved decision-making capabilities. In addition, many problems in ML have a mathematical structure that is identical to that of SIP problems, and hence the advances achieved in this project can also be used to improve ML-based predictions. The project closely aligns with several ONR Framework priorities. It supports the Sensors and Sense-making priority by translating data to decisions (sense-making), and by providing tools that can solve sensor placement optimization problems. The new SIP algorithms can also help improve tactical decisions that mitigate risk to people and command and control infrastructure, thus advancing the Augmented Warfighter priority. Finally, the Operational Endurance priority is supported by providing design, planning, and decision-making tools that can enhance eff platforms.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jun 09, 2021
- Source ID
- N000142112574
Entities
People
- James Luedtke
Organizations
- Office of Naval Research
- United States Navy
- University of Wisconsin System