(206a) A Branch-and-Price Algorithm for Multistage Stochastic Programs with Discrete State Variables

Modeling multistage planning problems is becoming increasingly important in various real-world applications, such as developing optimal expansion policies for renewable energy transitions, solving optimal power flow problems in power systems, and deriving complex scheduling decisions in various chemical industries. However, in practice, it is extremely challenging to model and solve these large-scale problems, which often forces decision-makers to adapt and implement suboptimal policies. Some of the major factors that render these model difficult include: 1) Unavailability or inaccessibility of data, resulting in uncertainty in these models. 2) Discrete decisions, such as capacity expansion via installation of new chemical plants, which lead to mixed-integer optimization models. 3) Complex nonlinear correlations between various decision variables result in mixed-integer nonlinear programs (MINLPs), which can often be nonconvex and are known to be one of the most challenging classes of problems to solve. To address the above-mentioned issues, we propose to apply a stochastic programming [1] framework and develop a tailored decomposition approach for multistage stochastic MINLPs with discrete state variables.

Stochastic programming provides a natural framework for modeling sequential optimization problems under uncertainty; however, the efficient solution of large-scale multistage stochastic programs, particularly under significant uncertainty (large number of scenarios), remains a challenge. In the presence of discrete state variables, the multistage stochastic MINLPs exhibit a decomposable structure that allows them to be solved using a branch-and-price approach. Following a Dantzig-Wolfe reformulation, we apply column generation (CG) [2, 3] such that each pricing subproblem is an MINLP of much smaller size, making it more amenable to exact MINLP solvers like BARON. Furthermore, the decoupled subproblems allow for a distributed computing approach, which significantly reduces the solution time. To mitigate the known convergence issues [4] in CG, we further incorporate a technique for information sharing among subproblems [5], generating more relevant and feasible columns per CG iteration. Finally, we propose effective branching strategies to further improve the efficiency of our branch-and-price algorithm. Several case studies of practical relevance are used to demonstrate the effectiveness of our proposed decomposition algorithm over solving the full-space model.

References

[1] Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media.

[2] Lübbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations research, 53(6), 1007-1023.

[3] Allman, A., & Zhang, Q. (2021). Branch-and-price for a class of nonconvex mixed-integer nonlinear programs. Journal of Global Optimization, 81, 861-880.

[4] Vanderbeck, F. (2005). Implementing mixed integer column generation. Column generation, 331-358.

[5] Flores-Quiroz, A., & Strunz, K. (2021). A distributed computing framework for multi-stage stochastic planning of renewable power systems with energy storage as flexibility option. Applied Energy, 291, 116736.