The Benders Dual Decomposition Method

• 成果类型: Article
• 署名作者: Rahmaniani, Ragheb; Ahmed, Shabbir; Crainic, Teodor Gabriel; Gendreau, Michel; Rei, Walter
• 署名单位: University System of Georgia; Georgia Institute of Technology; University of Quebec; University of Quebec Montreal; Universite de Montreal; University of Quebec; University of Quebec Montreal; Universite de Montreal; Polytechnique Montreal; Universite de Montreal; Polytechnique Montreal
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1892
• 发表日期: 2020
• 页码: 878-895
• 关键词: Benders decomposition; Lagrangian relaxation; dual decomposition; Mixed-Integer Programming

摘要

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.