Integration of Modern Convex and Integer Optimization Approaches in Stochastic Mixed-Integer Programming

2016 - presentpresent

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 (SMIP) 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. Despite its power and generality, widespread adoption of the SMIP framework has been hamstrung by the non-availability of algorithms and software that can handle problems of practical size and complexity. We propose to change this situation by fusing algorithmic ideas from modern convex optimization, mixed-integer programming (MIP), and stochastic programming into powerful tools for solving practical SMIP problems. A vital ingredient in our approach is a variable-splitting decomposition combined with Lagrangian relaxation. This dual decomposition has a number of significant advantages for SMIP. First, the lower bounds produced by optimizing the Lagrangian can be significantly stronger than alternative bounds. Second, decomposition breaks the Lagrangian evaluation into a collection of independent MIP problems, allowing our algorithms to leverage the recent remarkable advances in MIP solution technology. Third, the approach parallelizes naturally, so our algorithms can take advantage of large-scale distributed computing platforms. Finally, in contrast to other decomposition schemes, our approach can readily be applied to SMIP instances that have multiple decision stages.