Economics at your fingertips  

The Benders Dual Decomposition Method

Ragheb Rahmaniani (), Shabbir Ahmed (), Teodor Gabriel Crainic (), Michel Gendreau () and Walter Rei ()
Additional contact information
Ragheb Rahmaniani: Optimized Markets Inc., Pittsburgh, Pennsylvania 15213
Shabbir Ahmed: School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Teodor Gabriel Crainic: CIRRELT & School of Management for École des Sciences de la Gestion, Université du Québec à Montréal, Montréal, Québec H3C 3P8, Canada
Michel Gendreau: CIRRELT & Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal, Montréal, Québec H3C 3A7, Canada
Walter Rei: School of Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332

Operations Research, 2020, vol. 68, issue 3, 878-895

Abstract: Many methods that have been proposed to solve large-scale mixed integer linear programing (MILP) problems rely on decomposition techniques. These methods exploit either the primal or the dual structure of the problem, yielding the Benders decomposition or Lagrangian dual decomposition methods. We propose a new and high-performance approach, called Benders dual decomposition (BDD), which combines the complementary advantages of both methods. The development of BDD is based on a specific reformulation of the Benders subproblem, where local copies of the master variables are introduced in the proposed subproblem formulation and then priced out into the objective function. We 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. We report encouraging computational results on various benchmark MILP problems.

Keywords: Benders decomposition; Lagrangian relaxation; dual decomposition; mixed-integer programming (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed

Downloads: (external link) (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:

Access Statistics for this article

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

Page updated 2020-10-24
Handle: RePEc:inm:oropre:v:68:y:2020:i:3:p:878-895