Risk-Neutral Stochastic Linear Programming Methods

In this chapter, we study decomposition methods for risk-neutral two-stage stochastic linear programming (RN-SLP). We use the theoretical properties of the models derived in Chap. 2 and decomposition techniques from Chap. 5 to derive solution algorithms for RN-SLP. We begin our study with the classical L-shaped algorithm in Sect. 6.2, which generates a single optimality cut at a given iteration of the algorithm to approximate the recourse function. We then consider two extensions of the algorithm; namely, the multicut algorithm in Sect. 6.3 and the adaptive multicut algorithm in Sect. 6.4. Instead of generating a single optimality cut at a given iteration of the algorithm, the multicut method generates multiple optimality cuts, one for each scenario. In the adaptive multicut method an arbitrary aggregation of the cuts is permitted to potentially speed up computation time. computer implementation (coding) of decomposition algorithms for RN-SLP may not be an easy activity for many students. Therefore, in our derivation of the various algorithms, we place emphasis on implementation and provide guidelines for efficient computer codes. We end the chapter with a list of other decomposition methods for RN-SLP not covered in this chapter in Sect. 6.5.