(61v) Quantitative Studies of Decomposition Algorithm Efficiencies for Global Nonconvex Stochastic Optimization Problems

Stochastic programming (SP) is a prevalent framework for modeling decision-making processes under uncertainty, and it has been widely applied in many areas, e.g., process planning and control. Nevertheless, it often leads to models with an exceedingly large number of variables and constraints. When the SP model also involves nonconvexity, directly solving it globally via standard global algorithms can be prohibitively costly. As a result, many decomposition algorithms have been developed to address nonconvex SP problems, aiming to reduce computational cost by leveraging the unique structure of SP models. However, these methods often fall short in guaranteeing global optimality and may perform as poorly as direct approaches in the worst-case scenarios.

In recent years, several decomposition algorithms have been developed for nonconvex SP problems that overcome the aforementioned disadvantages [1]–[3]. These methods can be understood as reduced-space spatial branch-and-bound (SBB) approaches, wherein only the first-stage variables are branched on in the SBB procedure, ensuring guaranteed global optimality and outstanding scalability concerning the number of scenarios in the SP problem. Nevertheless, our previous work [4] has theoretically demonstrated that these methods may suffer from significant efficiency drawbacks for general problems. Within the reduced-space SBB framework, the lower bounding schemes of all these methods exhibit first-order convergence in general, except for an idealized version of [1] under certain assumptions. From previous research [5], the low convergence order makes all these algorithms susceptible to the cluster problem, i.e., their SBB procedure needs to visit an exponentially large number of nodes before termination, causing low computational speed in practice. Existing results from these algorithms support this claim given their struggle with problems involving more than a limited number of first-stage decisions. According to our analysis [4], all convex relaxation-based reduced-space SBB methods (including [1]–[3]) will suffer from first-order convergence in general, except when the projected value function of the optimization problem exhibit certain properties. However, no numerical experiments have been conducted to substantiate this analysis, and it remains unclear whether real-world SP problems meet the properties necessary for these algorithms to avoid the cluster problem. Therefore, there is a pressing need for systematic numerical experiments to assess the efficiency of these cutting-edge algorithms and evaluate the practicality of the reduced space framework.

In this work, we built a library of nonconvex SP problems to assess the computational speed of the Cao and Zavala (CZ) algorithm [3] and the Li and Grossmann (LG) algorithm [1]. Our primary objective was to check whether, in general, both methods visit an exponential number of nodes relative to the first-stage variable number and the termination error before termination, which serves as the principal criterion for the occurrence of the cluster problem. The library, referred to as NSPLIB, comprises a diverse range of medium- to large-sized nonconvex SP problems, all derived from real-world applications. These problems feature continuous first-stage variables and may have mixed-integer second-stage variables, with nonconvexity arising either from the constraints or the integer second-stage variables. The CZ and LG algorithms were implemented in a streamlined manner, retaining only the aspects of their lower bounding schemes responsible for convergence, while the SBB procedure was executed in a simplistic fashion. In the LG algorithm, the subgradient method was fine-tuned to approach the Lagrangean dual. Alongside the number of visited nodes, we employed several additional metrics to estimate the computational speed of the algorithms. Both the problem library and the algorithm implementations were developed using Python/Pyomo and are available online.

Our experimental results revealed that the limited implementations of both algorithms display notably slow performance. In comparison to directly solving the full model, the basic versions of the algorithms proved to be several orders of magnitude slower for most problems. In practice, both methods demonstrate first-order convergence, and the cluster problem almost always arises, confirming the conclusions of our previous work. The only exception was that the cluster problem did not happen for MILP problems where the value functions exhibited favorable geometric properties near the optimizers, further validating the theorems presented in [4]. The implementation of the subgradient method in the LG algorithm revealed that obtaining Lagrangean duals is exceedingly challenging and impractical for use. Although the dual may exhibit a higher convergence order, potentially mitigating the cluster problem, it remains unsuitable for practical applications. Moreover, our findings uncovered several aspects of the reduced-space SBB framework that influence algorithm speed and were not previously emphasized, including tolerance settings for subproblems, practical implementation of the subgradient method, and upper bounding. In summary, this study employed a variety of numerical instances to highlight the limitations of the reduced-space SBB framework for decomposition algorithms in nonconvex SP problems, providing guidance for developing more efficient algorithms for such problems in the future. It was also the first study to numerically showcase the cluster problem in the context of real-world SP problems.

[1] C. Li and I. E. Grossmann, “A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables,” Journal of Global Optimization, vol. 75, no. 2, pp. 247–272, 2019, doi: 10.1007/s10898-019-00816-8.

[2] R. Kannan, “Algorithms, analysis and software for the global optimization of two-stage stochastic programs,” 2018. [Online]. Available: https://dspace.mit.edu/handle/1721.1/117326

[3] Y. Cao and V. M. Zavala, “A scalable global optimization algorithm for stochastic nonlinear programs,” Journal of Global Optimization, vol. 75, no. 2, pp. 393–416, 2019, doi: 10.1007/s10898-019-00769-y.

[4] D. L. Robertson, P. Cheng, and J. K. Scott, “Convergence Rate Analysis for Schemes of Relaxations in Decomposition Methods for Global Nonconvex Stochastic Optimization,” in 2020 Virtual AIChE Annual Meeting, 2020.

[5] A. Wechsung, S. D. Schaber, and P. I. Barton, “The cluster problem revisited,” Journal of Global Optimization, vol. 58, no. 3, pp. 429–438, 2014.