Optimization Online


Improving Benders decomposition via a non-linear cut selection procedure

G. Miranda(gilberto.miranda***at***ufes.br)
R.S. Camargo(rcamargo***at***dep.ufmg.br)
F. M. S. Lima(fatimasmlima***at***gmail.com)

Abstract: A non-linear lifting procedure is proposed to generate high density Benders cuts. The new denser cuts cover more master problem variables than traditional Benders cuts, shortening the required number of iterations to reach optimality, and speeding up the Benders decomposition algorithm. To lessen the intricacy stemmed from the non-linearity, a simple outer approximation lineariza- tion is devised to allow the use of linear programming tools to solve the additional Benders subproblem. Computational experiments show that the new cut selection procedure outperforms two existing alternatives the Pareto-optimal cuts by Papadakos (2008), and the high density Benders cuts of Tang et al (2013) on solving two distinct location problems. Despite an extra computational effort, the worthwhile subproblem greatly reduces the number of Benders iterations when facing harder instances, yielding in remarkable time savings.

Keywords: Benders decomposition Lifting procedure Stronger Benders cuts Large scale optimization

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Applications -- OR and Management Sciences

Category 3: Network Optimization


Download: [PDF]

Entry Submitted: 08/03/2016
Entry Accepted: 08/03/2016
Entry Last Modified: 08/03/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society