A Closest Benders Cut Selection Scheme for Accelerating the Benders Decomposition Algorithm

Kiho Seo (), Seulgi Joung (), Chungmok Lee () and Sungsoo Park ()
Additional contact information
Kiho Seo: Department of Industrial and Systems Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea
Seulgi Joung: Department of Industrial Engineering, Chonnam National University, Gwangju, Republic of Korea
Chungmok Lee: Department of Industrial and Management Engineering, Hankuk University of Foreign Studies, Youngin-si, Republic of Korea
Sungsoo Park: Department of Industrial and Systems Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea

INFORMS Journal on Computing, 2022, vol. 34, issue 5, 2804-2827

Abstract: The Benders decomposition algorithm often shows poor convergence. To improve the convergence of the Benders decomposition algorithm. Recently, it was proposed the use of feasibility cuts closest to a solution in the set defined by all feasibility cuts. We extend this feasibility cut selection scheme to a new cut selection scheme for optimality cuts and propose a new Benders separation framework that a single linear programming problem can solve. We show that optimality cuts generated by this scheme are Pareto optimal when some conditions are satisfied. Theoretical connections to the existing Benders cut generation methods are also identified. Extensive computational experiments on the multiple classes of benchmark problems demonstrate that the proposed algorithm improves the convergence speed and computational time. Summary of Contribution: The Benders decomposition algorithm is one of the most widely used algorithms in operations research. However, the Benders decomposition algorithm often shows poor convergence for some optimization problems. In this paper, to improve the convergence of the Benders decomposition algorithm, we propose a unified closest Benders cut generation scheme. We give theoretical properties of the proposed Benders cuts, including Pareto optimality and facet-defining conditions. Also, we conducted extensive computational tests on various instances, such as network design and expansion problems. The results show the effectiveness of the closest Benders cut compared with existing algorithms and Cplex.

Keywords: Benders decomposition algorithm; optimality cut; fractional programming problem; Pareto-optimal cut; multicommodity capacitated fixed-charge network design problem (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1207 (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:orijoc:v:34:y:2022:i:5:p:2804-2827

Access Statistics for this article

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