论文标题
与基于逻辑的弯曲器分解的随机计划和调度
Stochastic Planning and Scheduling with Logic-Based Benders Decomposition
论文作者
论文摘要
我们将基于逻辑的弯曲器分解（LBBD）应用于两个阶段的随机计划和调度问题，其中第二阶段是调度任务。我们通过混合整数/线性编程和与约束编程的子问题解决主问题。随着弯曲者的削减，我们使用简单的Nogood切割以及为此应用开发的基于分析逻辑的切割。我们发现LBBD在计算上优于整数L形方法，其分支和检查LBBD的分支变体的速度更快地缩小了几个数量级，从而可以求解更大的实例。这主要是由于整数L形方法产生的计算间接开销，同时生成经典的弯曲器是由于整数编程子问题的连续放松而削减的。据我们所知，这是LBBD与计划第二阶段问题的两阶段随机优化的第一次应用，也是LBBD与Integer \ Mbox {l-hape}方法的第一个比较。结果表明，LBBD可能是用于通过整数或组合追索权的其他随机且可靠的优化问题的一种有希望的方法。
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 nogood cuts as well as analytical logic-based cuts we develop for this application. We find that LBBD is computationally superior to the integer L-shaped method, with a branch-and-check variant of LBBD 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 classical 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 \mbox{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.
