(15f) A Modified Integer L-Shaped Method for Two-Stage Stochastic Programs

Two-stage stochastic programs are a natural choice for modeling several real-world problems where decisions must be made before and after some uncertain information becomes available. One drawback of these formulations is that they often require many scenarios to accurately model the random parameters in the problem, which leads to very large problems in terms of numbers of variables and constraints. As a result, tailored solution algorithms that exploit the unique structure of two-stage stochastic programs are often necessary to efficiently solve problems of industrially relevant size.

In this work, we consider two-stage stochastic mixed-integer linear programs with relatively complete recourse and binary state variables (i.e., all first-stage decisions that directly affect the second stage are binary), which are often solved using the integer L-shaped method (Angulo et al., 2016; Laporte & Louveaux, 1993). A typical implementation of the algorithm operates in a fashion similar to Benders decomposition by iteratively generating so-called optimality cuts from solutions of LP subproblems and MILP subproblems (“integer subproblems”). In the case of two-stage stochastic programs, the subproblem can be separated into multiple independent subproblems, where each of them corresponds to one particular scenario. These subproblems can be solved in parallel in a “multicut” implementation, which often speeds up the solution of problems with many scenarios. One drawback of the classical integer L-shaped method, however, is that optimality cuts generated by solving integer subproblems, sometimes referred to as no-good optimality cuts (Wolsey, 2020), require solving the subproblems to full optimality. This can slow the solution of problems significantly—and diminish the advantage provided by parallelization—if even only a few of the integer subproblems are difficult to solve.

In this work, we propose a modification to the integer L-shaped method that incorporates the use of suboptimal solutions to integer subproblems while still guaranteeing convergence to an optimal solution. A multicut implementation of the algorithm is tested in two case studies. In the first case study, a two-stage stochastic program is solved to determine the optimal investment into, and relocation of, mobile production modules given uncertain time-varying demands in a supply chain (Allman & Zhang, 2020). In the second case study, a two-stage stochastic program is used to determine the optimal design and scheduling of renewables-based fuels and power production networks with uncertain renewable power generation (Zhang et al., 2019). Ultimately, the case studies are used to compare the performance of the proposed algorithm to that of an off-the-shelf solver and the integer L-shaped method from the literature. Additionally, the results from the case studies reveal the main problem features that affect the suitability of the proposed algorithm.

References

Allman, A., & Zhang, Q. (2020). Dynamic location of modular manufacturing facilities with relocation of individual modules. European Journal of Operational Research, 286(2), 494–507.

Angulo, G., Ahmed, S., & Dey, S. S. (2016). Improving the Integer L-Shaped Method. INFORMS Journal on Computing, 28(3), 483–499.

Laporte, G., & Louveaux, F. V. (1993). The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters, 13(3), 133–142.

Wolsey, L. (2020). Integer Programming (2nd ed.). Wiley.

Zhang, Q., Martín, M., & Grossmann, I. E. (2019). Integrated design and operation of renewables-based fuels and power production networks. Computers & Chemical Engineering, 122, 80–92.