(194e) Nested Decomposition Algorithms for Large-Scale Multi-Period and Multistage Stochastic Mixed-Integer Linear Programming Models

Decomposition techniques are key to solving real world large-scale multiperiod/stochastic programming problems. The nested Benders decomposition method [1], and its stochastic version, the Stochastic Dual Dynamic Programming (SDDP) [2] are based on the idea of applying the Benders Decomposition method to a problem more than once, in a nested fashion. They are particularly appropriate for multi-period/multi-stage problems in which each pair of adjacent periods/stages can be considered separately as a subproblem. Their major limitation, however, is that the subproblems have to be convex in order for the Benders cut to be valid, which excludes discrete problems. This issue has recently been addressed by the development of Nested Benders-like decomposition that uses relaxations to derive valid cuts to mixed-integer subproblems [3,4,5].

We propose a Nested Decomposition algorithm based on Nested Benders Decomposition for mixed-integer multi-period problems to solve large-scale models [6]. We adapt the framework proposed by Zou et al. [5] 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. [5] to also handle mixed-integer recourse [7] 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.

[1] J. R. Birge. Decomposition and partitioning methods for multistage stochastic linear programs. Operations Research, 33(5):989–1007, 1985.

[2] M. V. Pereira and L. M. Pinto. Multi-stage stochastic optimization applied to energy planning. Mathematical programming, 52(1-3):359–375, 1991.

[3] 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.

[4] 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.

[5] 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

[6] 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.

[7] 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.