Stochastic Mixed-Integer Programming Methods

This chapter gives an introductory study of two-stage stochastic mixed-integer programming (SMIP). This subject is an extension of deterministic MIP to the stochastic setting. Thus, SMIP inherits the nonconvexity properties of MIP and with its large-scale nature due to data uncertainty, SMIP is very challenging to solve. Therefore, it is not surprising that there are few practical algorithms for SMIP. This motivates the study of SMIP due to its many practical applications. We begin with the basic properties in Sect. 9.2, discuss the design of algorithms in Sect. 9.3, and give an example instance in Sect. 9.4. We explore three solution methods and provide a numerical example to illustrate the steps of each algorithm in detail. We begin with the binary first-stage (BFS) algorithm in Sect. 9.5, then move on to cover the Fenchel decomposition (FD) algorithm in Sect. 9.6. We end with the disjunctive decomposition ( \(D^2\) ) algorithm in Sect. 9.7. The BFS algorithm is designed for SMIP with binary first-stage and arbitrary second-stage decision variables. The FD algorithm is a cutting-plane method designed for SMIP with arbitrary first- and second-stage decision variables. The \(D^2\) algorithm is also a cutting-plane method, but it is designed for SMIP with binary first stage and mixed-binary second stage. We describe each algorithm with a great level of detail to help with computer implementation as this is not a trivial matter.