Scalable Methods for Solving Stochastic Mixed-Integer Programs

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

Many decision problems in science, engineering, economic analysis, and public-sector applications involve both discrete decisions and uncertainty about future outcomes. Stochastic mixed-integer programming is an important mathematical modeling framework that allows for the systematic treatment of uncertainty in optimization problems that involve a large number of discrete, yes-no decisions. If successful, this work will form the basis of general-purpose software that can be used in a wide variety of planning problems in areas as diverse as electricity generation planning, military operations, supply chain planning, and forest fire response. The availability of methods to solve such problems will give decision makers the ability to make plans that are more robust in the face of uncertainty, leading to improved outcomes and more efficient use of scarce resources. The adoption of these techniques will be encouraged by integrating optimization modeling under uncertainty into courses taken by students in a variety of disciplines. This project will fuse algorithmic ideas from modern convex optimization, mixed-integer programming, and stochastic programming to obtain powerful tools for solving stochastic mixed-integer programs. New algorithms will be designed, convergence results will be obtained, and software will be produced. A vital ingredient of the approach is a variable-splitting decomposition combined with Lagrangian relaxation. Obtaining strong lower bounds in this approach requires optimization of the Lagrangian dual, a challenging mathematical problem of maximizing a high-dimensional, non-smooth, concave function, for which the costs of evaluating the function and its subgradients are high. The research team will investigate the translation of convex optimization techniques that have recently been shown to be successful in data analysis applications to solving this Lagrangian dual. The research team will also investigate the use of integer programming techniques to obtain convergence to an optimal solution, including strong branching and pseudocosts, cutting planes, and primal heuristics.