Journal
INFORMS JOURNAL ON COMPUTING
Volume 34, Issue 5, Pages 2428-2442Publisher
INFORMS
DOI: 10.1287/ijoc.2022.1184
Keywords
stochastic planning and scheduling; logic-based Benders decomposition; two-stage stochastic programming with integer recourse
Ask authors/readers for more resources
This paper applies logic-based Benders decomposition method to solve two-stage stochastic planning and scheduling problems, and finds that it is computationally superior to the integer L-shaped method and provides faster solution for larger problem instances.
We apply logic-based Benders decomposition (LBBD) to two-stage stochastic planning and scheduling problems in which the second stage is a scheduling task. We solve the master problem with mixed integer/linear programming and the subproblem with constraint programming. As Benders cuts, we use simple no-good cuts as well as analytic logic-based cuts we develop for this application. We find that LBBD is computationally superior to the integer L-shaped method. In particular, a branch-and-check variant of LBBD can be faster by several orders of magnitude, allowing significantly larger instances to be solved. This is due primarily to computational overhead incurred by the integer L-shaped method while generating classic Benders cuts from a continuous relaxation of an integer programming subproblem. To our knowledge, this is the first application of LBBD to two-stage stochastic optimization with a scheduling second-stage problem and the first comparison of LBBD with the integer L-shaped method. The results suggest that LBBD could be a promising approach to other stochastic and robust optimization problems with integer or combinatorial recourse.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available