A Review on the Performance of Linear and Mixed Integer Two-Stage Stochastic Programming Software

Round 1

Reviewer 1 Report

The manuscript presents some state-of-the-art methodologies for solving two-stage stochastic linear programming having mixed-integer variables.

The presentation is didactical, and the authors succeed in balancing the amount of technicalities to make the text accessible for beginners and yet interesting enough for more experienced researchers/practitioners looking for references and software in the field. 

The paper is easy to read, contains interesting observations, and reports extensive numerical experiments. However, as a downside, I found the presentation of Subsection 4.2 misleading. Comment #8 below lists additional references and remarks some inaccurate interpretations. 

 

Specific comments/questions to the authors:

 

1) The manuscript focus on the risk-neutral setting only. However, the authors could mention that the studied approaches can be extended to the risk-averse setting. Indeed, for some risk measures such as the Cvar, risk-averse optimization problems can be formulated to minimize an expected value function having one additional variable. The authors may add one paragraph on this matter, enlarging the manuscript's field of application while keeping the risk-neutral formulation's notation and convenience. Reference [A] below may be helpful.

 

2) Lines 29-30: Lagrangian decomposition and Progressive Hedging do not require linearity. Both methodologies can cope with nonlinear stochastic programs. 

 

3) Lines 41-42. "SP has not been widely used in industrial applications." This statement is certainly not true in the industry of energy. SP models have been officially used to plan and operate power systems in several countries worldwide (some countries have been employing SP since the 80s). Please check SDDP related literature if necessary. 

 

4) The manuscript's title contains the words "Mixed Integer," but the problem formulation is a "Mixed Binary" one. As far as one can tell, the studied methodologies can indeed handle mixed-integer variables. Why then restrict problem (1) to the mixed-binary setting? 

 

5) Was it explicitly said that \tau_\omega in (1) is the probability of scenario \omega? It seems that probabilities are missing in equation (20).

 

5) Lines 161-162. "The MP is often the most time-consuming part of the BD, especially in the case of mixed-integer problems." This statement is questionable. It is certainly not true in the continuous setting, and in the mixed-integer one, computational complexity will depend on the number of first-stage variables and scenarios. See for example [B]. Please rephrase that statement. At least remove the word "especially."

 

6) Section 4 is split into two subsections, the first is dedicated to reducing the cost of each iteration, and the second focuses on reducing the number of iterations. Recent papers concentrate on developments in both directions. I suggest the authors comment on that and cite, for instance, [D], [E] and [F]

 

7) Lines 197-199: please add the complete reference of [67] (this is a particular case of the more general regularization scheme of [G]).

 

8) Lines 200-202. "Regularized Decomposition is also known as the Proximal Bundle Method." Indeed, RD is nothing but a simplified PBM variant, which should be acknowledged as done for the pair L-Shaped & Benders decomposition: RD is for PBM what the L-Shaped is for Kelley's cutting plane method. The authors should also mention that the regularized methods briefly described in equations (12), (13), and (14) are all variants of the large family of bundle methods. As references for this claim, the authors may cite chapters XIV and XV of [H], and/or Chapters 3, 9, and 12 of [I]. 

Some specific comments follow by focusing on the area of interest: a variant of PBM applied to mixed-integer 2LSPs was investigated in [F]. In addition, reference [D] presents a trust-region bundle method to the same class of problems, and [G] extended the level bundle method of [38] to the convex mixed-integer programs, reporting numerical experiments on mixed-integer 2SLPs.

 

As already said, when applied to 2SLP, the Benders decomposition becomes the L-shaped method, and PBM simplifies to DR. 

A similar name change occurred for the level bundle method of [38]. It seems that reference [H] coined the term Level Decomposition. 

 

Please check if reference [68] is well placed on line 201.

 

9) Equation (19) requires bounds to make the feasible set compact. Otherwise, the master program may not have a solution (a drawback of the cutting-plane method, but not of either PBM or TR bundle method).

 

10) Lines 239-241. "Cutting-plane methods present similar drawback as the BD." This is explained by the fact that BD is (from the nonsmooth optimization point of view) a particular case of CP. Chapter 3 of [I] might be a good reference here.

 

11) The figures' labels are too small.  

 

 

References

 

[A] R. T. Rockafellar Solving stochastic programming problems with risk measures by progressive hedging, Set-Valued and Variational Analysis 26 (2018), 759--768

 

[B] F. Beltrán et al. Two-stage and multi-stage decompositions for the medium-term hydrothermal scheduling problem: a computational comparison of solution techniques. International Journal of Electrical Power & Energy Systems, 127, 106659 2021.

 

[D] Kim, K. et al. An asynchronous bundle-trust-region method for dual decomposition of stochastic mixed-integer programming. SIAM J. Optim. (2019) 29, 318–342 

 

[E] B. Colonetti et al. A mixed-integer and asynchronous level decomposition with application to the stochastic hydrothermal unit-commitment problem. Algorithms, V. 13, n 235, 2020

 

[F] S. Moazeni, R. A. Collado. Resource allocation for contingency planning: An inexact proximal bundle method for stochastic optimization. Eur. J. Oper. Res. 291(3): 1008-1023 (2021)

 

[G] W. de Oliveira. Regularized optimization methods for convex MINLP problems. TOP, (2016), 24(3) 665-692

 

[H] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis Minimization Algorithms II, Springer, Berlin (1993)

 

[I] A. M. Bagirov, et al. Numerical Nonsmooth Optimization: State of the Art Algorithms. Springer https://link.springer.com/book/10.1007/978-3-030-34910-3

 

[H] F. Casba, C.I., Szőke, Z. Solving two-stage stochastic programming problems with level decomposition. CMS4, 313–353 (2007). https://doi.org/10.1007/s10287-006-0026-8

 

 

 

 

 

 

Author Response

see attached pdf

Author Response File: Author Response.pdf

Reviewer 2 Report

The paper presents a tutorial on two-Stage mixed integer linear stochastic program algorithms with a focus on software and provides a comparative overview of the proposed methodologies. The paper is  well-structured and easy to follow. Given the general topic addressed here, the paper provides sufficient numerical results to show the performance of each algorithm. The biggest drawback of the proposed research is the references. Since this is more like a review/tutorial paper, and does not provide new knowledge, the references are so outdated. There is no reference cited after 2018. I highly encourage the authors to update their paper with new references. 

Author Response

see attached pdf

Author Response File: Author Response.pdf