Computational Evaluation of Cut-Strengthening Techniques in Logic-Based Benders’ Decomposition

被引：0

作者：

Saken A. ^{[1
]}

Karlsson E. ^{[2
,3
]}

Maher S.J. ^{[1
,4
]}

Rönnberg E. ^{[2
]}

机构：

[1] Department of Mathematics, University of Exeter, Stocker Rd, Exeter

[2] Department of Mathematics, Linköping University, Linköping

[3] Saab AB, Linköping

[4] Quantagonia GmbH, Bad Homburg

来源：

Operations Research Forum | / 4卷 / 3期

关键词：

Benders; cuts; Cut strengthening; Feasibility cuts; Irreducible cuts; Logic-based Benders’ decomposition; Optimality cuts;

D O I：

10.1007/s43069-023-00242-3

中图分类号：

学科分类号：

摘要：

Cut-strengthening techniques have a significant impact on the computational effectiveness of the logic-based Benders’ decomposition (LBBD) scheme. While there have been numerous cut-strengthening techniques proposed, very little is understood about which techniques achieve the best computational performance for the LBBD scheme. This is typically due to implementations of LBBD being problem specific, and thus, no systematic study of cut-strengthening techniques for both feasibility and optimality cuts has been performed. This paper aims to provide guidance for future researchers with the presentation of an extensive computational study of five cut-strengthening techniques that are applied to three different problem types. The computational study involving 3000 problem instances shows that cut-strengthening techniques that generate irreducible cuts outperform the greedy algorithm and the use of no cut strengthening. It is shown that cut strengthening is a necessary part of the LBBD scheme, and depth-first binary search and deletion filter are the most effective cut-strengthening techniques. © 2023, The Author(s).

引用

共 23 条

[1]

Hooker J.N., Ottosson G., Logic-based Benders decomposition, Math Program, 96, pp. 33-60, (2003)

[2]

Cire A.A., Coban E., Hooker J.N., Logic-based Benders decomposition for planning and scheduling: a computational analysis, Knowl Eng Rev, 31, 5, pp. 440-451, (2016)

[3]

Karlsson E., Ronnberg E., Strengthening of feasibility cuts in logic-based Benders decomposition, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 45-61, (2021)

[4]

Rahmaniani R., Crainic T.G., Gendreau M., Rei W., The Benders decomposition algorithm: a literature review, Eur J Oper Res, 259, pp. 801-817, (2017)

[5]

Karlsson E., Ronnberg E., Logic-based Benders decomposition with a partial assignment acceleration technique for avionics scheduling, Comput Oper Res, 146, (2022)

[6]

Lam E., Gange G., Stuckey P.J., Van Hentenryck P., Dekker J.J., Nutmeg: a MIP and CP hybrid solver using branch-and-check, SN Oper Res Forum, 1, pp. 22-12227, (2020)

[7]

Lindh E., Olsson K., Ronnberg E., Scheduling of an underground mine by combining logic-based Benders decomposition and a priority-based heuristic, Proceedings of the 13Th International Conference on the Practice and Theory of Automated Timetabling–PATAT, pp. 2-30, (2022)

[8]

Hooker J.N., Logic-Based Benders Decomposition for Large-Scale Optimization, pp. 1-26, (2019)

[9]

Hooker J.N., Planning and scheduling by logic-based Benders decomposition, Oper Res, 55, pp. 588-602, (2007)

[10]

Riedler M., Raidl G., Solving a selective dial-a-ride problem with logic-based Benders decomposition, Comput Oper Res, 96, pp. 30-54, (2018)

← 1 2 3 →