An Introduction to Two-Stage Stochastic Mixed-Integer Programming

This paper provides an introduction to algorithms for two-stage stochastic mixed-integer programs. Our focus is on methods that decompose the problem by scenarios representing randomness in the problem data. The design of these algorithms depends on where the uncertainty appears (right-hand side, recourse matrix, or technology matrix) and where the continuous and discrete decision variables are (first stage or second stage). In addition, we provide computational evidence that, similar to other classes of stochastic programming problems, decomposition methods can provide desirable theoretical properties (such as finite convergence) as well as enhanced computational performance when compared with solving a deterministic equivalent formulation using an advanced commercial mixed-integer programming solver.