← Search

The Benders Dual Decomposition Method

Ragheb Rahmaniani¹; Shabbir Ahmed²; Teodor Gabriel Crainic³; Michel Gendreau⁴; Walter Rei²

¹ Optimized Markets Inc., Pittsburgh, Pennsylvania 15213; · ² School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332; · ³ CIRRELT & School of Management for École des Sciences de la Gestion, Université du Québec à Montréal, Montréal, Québec H3C 3P8, Canada; · ⁴ CIRRELT & Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal, Montréal, Québec H3C 3A7, Canada

Many methods that have been proposed to solve large-scale MILP problems rely on the use of decomposition strategies. These methods exploit either the primal or dual structures of the problems by applying the Benders decomposition or Lagrangian dual decomposition strategy, respectively. In “The Benders Dual Decomposition Method,” Rahmaniani, Ahmed, Crainic, Gendreau, and Rei propose a new and high-performance approach that combines the complementary advantages of both strategies. The authors show that this method (i) generates stronger feasibility and optimality cuts compared with the classical Benders method, (ii) can converge to the optimal integer solution at the root node of the Benders master problem, and (iii) is capable of generating high-quality incumbent solutions at the early iterations of the algorithm. The developed algorithm obtains encouraging computational results when used to solve various benchmark MILP problems.

DOI

10.1287/opre.2019.1892

Volume

68 (3)

Pages

878-895

Language

en

Export

BibTeX

Sources

crossref openalex