(194e) Nested Decomposition Algorithms for Large-Scale Multi-Period and Multistage Stochastic Mixed-Integer Linear Programming Models
We propose a Nested Decomposition algorithm based on Nested Benders Decomposition for mixed-integer multi-period problems to solve large-scale models . We adapt the framework proposed by Zou et al.  to deterministic multi-period problems and modify it to handle integer and continuous state variables (at the expense of losing the finite convergence property due to potential duality gap). We introduce three valid cuts to be used in this decomposition for this case of mixed-integer recourse, and propose acceleration techniques to improve the overall performance of the algorithm.
Additionally, we extend the Stochastic Dual Dynamic integer Programming (SDDiP) proposed by Zou et al.  to also handle mixed-integer recourse  in multistage stochastic programs. The SDDiP algorithm is computationally expensive but we take advantage of parallel processing to solve it more efficiently.
We test both the deterministic Nested Decomposition and the parallel SDDiP algorithms by solving a generation expansion planning model for a real-world case study in the region managed by the Electric Reliability Council of Texas (ERCOT). This model takes the viewpoint of a central planning entity, whose goal is to optimize the generation expansion to meet the projected electricity demand over a long-planning horizon while considering multiple sources (natural gas, coal, nuclear, solar, wind and storage), detailed operational constraints on an hourly basis, variability and intermittency of renewable generation sources, power flow between regions, and, for the stochastic version, multi-scale uncertainty (i.e. strategic uncertainty - e.g. fuel price and carbon tax uncertainties - and operational uncertainty - e.g. renewable availability and hourly load demand). The deterministic version of this problem is of the order of millions of variables and constraints, and the multistage stochastic programming version goes up to quadrillions of variables and constraints.
We show that the deterministic Nested Decomposition algorithm is more efficient than solving the monolithic version of the multiperiod model by commercial MILP solvers (i.e., it finds feasible solutions and converges faster), and that the SDDiP allows the solution of instances of multistage stochastic programs that could not be solved monolithically or with a scenario-based decomposition.
 J. R. Birge. Decomposition and partitioning methods for multistage stochastic linear programs. Operations Research, 33(5):989â1007, 1985.
 M. V. Pereira and L. M. Pinto. Multi-stage stochastic optimization applied to energy planning. Mathematical programming, 52(1-3):359â375, 1991.
 S. Cerisola, A. BaÄ±llo, J. M. Fernandez-Lopez, A. Ramos, and R. Gollmer. Stochastic power generation unit commitment in electricity markets: A novel formulation and a comparison of solution methods. Operations Research, 57(1):32â46, 2009.
 F. Thome, M. Pereira, S. Granville, and M. Fampa. Non-convexities representation on hydrothermal operation planning using sddp. URL: www. psr-inc. com, submitted, 2013.
 Zou, J., Ahmed, S. & Sun, X.A., (2018). âStochastic dual dynamic integer programmingâ, Mathematical Programming. pp. 1-42., https://doi.org/10.1007/s10107-018-1249-5
 Lara, C.L., Mallapragada, D.S., Papageorgiou, D.J., Venkatesh, A. & Grossmann, I.E. (2018) âDeterministic electric power infrastructure planning: Mixed-integer programming model and nested decomposition algorithmâ, European Journal of Operational Research. 3. 1037-1054.
 Lara, C.L., Siirola, J.D. & Grossmann, I.E. (2019) âElectric Power Infrastructure Planning Under Uncertainty: Stochastic Dual Dynamic Integer Programming (SDDiP) and parallelization schemeâ, Submitted for publication.