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

Aigerim Saken (), Emil Karlsson (), Stephen J. Maher () and Elina Rönnberg ()
Additional contact information
Aigerim Saken: University of Exeter
Emil Karlsson: Linköping University
Stephen J. Maher: University of Exeter
Elina Rönnberg: Linköping University

SN Operations Research Forum, 2023, vol. 4, issue 3, 1-53

Abstract: Abstract 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.

Keywords: Logic-based Benders’ decomposition; Cut strengthening; Feasibility cuts; Optimality cuts; Irreducible cuts; Benders’ cuts (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s43069-023-00242-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:4:y:2023:i:3:d:10.1007_s43069-023-00242-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-023-00242-3

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().