数学优化
整数规划
调度(生产过程)
随机规划
本德分解
线性规划松弛
计算机科学
线性规划
分支和切割
整数(计算机科学)
约束规划
分支机构和价格
数学
程序设计语言
作者
Özgün Elçi,John Hooker
出处
期刊:Informs Journal on Computing
日期:2022-09-01
卷期号:34 (5): 2428-2442
被引量:6
标识
DOI:10.1287/ijoc.2022.1184
摘要
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. Summary of Contribution: We study an important class of optimization problems, namely, two-stage stochastic programs with integer recourse, which are known to be extremely difficult to solve in general. We focus on an application in which the second-stage problem is a scheduling problem, a first in the literature to the best of our knowledge. Our study exemplifies how one can exploit the combinatorial structure of the scheduling problem to derive novel analytic Benders cuts and use them within a branch-and-check algorithm. The proposed algorithm solves instances that are intractable for commercial solvers and state-of-the-art decomposition-based methods, such as the integer L-shaped method. We believe that our study will inspire further research in the use of hybrid logic-based optimization methods for solving stochastic combinatorial optimization problems.
科研通智能强力驱动
Strongly Powered by AbleSci AI