Deepest Cuts for Benders Decomposition

Mojtaba Hosseini () and John Turner ()
Additional contact information
Mojtaba Hosseini: Tippie College of Business, University of Iowa, Iowa City, Iowa 52242
John Turner: The Paul Merage School of Business, University of California, Irvine, Irvine, California 92697

Operations Research, 2025, vol. 73, issue 5, 2591-2609

Abstract: Since its inception, Benders decomposition (BD) has been successfully applied to a wide range of large-scale mixed-integer (linear) problems. The key element of BD is the derivation of Benders cuts, which are often not unique. In this paper, we introduce a novel unifying Benders cut selection technique based on a geometric interpretation of cut depth, produce deepest Benders cuts based on ℓ p -norms, and study their properties. Specifically, we show that deepest cuts resolve infeasibility through minimal deviation (in a distance sense) from the incumbent point, are relatively sparse, and may produce optimality cuts even when classic Benders would require a feasibility cut. Leveraging the duality between separation and projection, we develop a guided projections algorithm for producing deepest cuts, exploiting the combinatorial structure and decomposability of problem instances. We then propose a generalization of our Benders separation problem, which not only brings several well-known cut selection strategies under one umbrella, but also, when endowed with a homogeneous function, enjoys several properties of geometric separation problems. We show that, when the homogeneous function is linear, the separation problem takes the form of the minimal infeasible subsystems (MIS) problem. As such, we provide systematic ways of selecting the normalization coefficients of the MIS method and introduce a directed depth-maximizing algorithm for deriving these cuts. Inspired by the geometric interpretation of distance-based cuts and the repetitive nature of two-stage stochastic programs, we introduce a tailored algorithm to further facilitate deriving these cuts. Our computational experiments on various benchmark problems illustrate effectiveness of deepest cuts in reducing both computation time and number of Benders iterations and producing high-quality bounds at early iterations.

Keywords: Optimization; Benders decomposition; acceleration techniques; cutting planes; mixed-integer programs (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.0503 (application/pdf)

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:inm:oropre:v:73:y:2025:i:5:p:2591-2609

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().