Optimization Online


Enhancing large neighbourhood search heuristics for Benders' decomposition

Stephen Maher (s.maher3***at***lancaster.ac.uk)

Abstract: A general enhancement of the Benders' decomposition (BD) algorithm can be achieved through the improved use of large neighbourhood search heuristics within mixed-integer programming solvers. While mixed-integer programming solvers are endowed with an array of large neighbourhood search heuristics, few, if any, have been designed for BD. Further, typically the use of large neighbourhood search heuristics is limited to finding solutions to the BD master problem. Given the lack of general frameworks for BD, only ad hoc approaches have been developed to enhance BD through the use of large neighbourhood search heuristics. The general BD framework of SCIP has been extended with a trust region based heuristic and a general enhancement for all large neighbourhood search heuristics. The general enhancement employs BD to solve the auxiliary problems of all large neighbourhood search heuristics to improve the quality of the identified solutions. The computational results demonstrate the improvements to the heuristic performance of BD achieved by the trust region heuristic and a general large neighbourhood search enhancement technique.

Keywords: Benders' decomposition, large neighbourhood search heuristics, enhancement techniques, mixed integer programming

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Stochastic Programming

Citation: Department of Management Science, Lancaster University, Bailrigg, Lancaster LA1 4YX, UK, July 2019

Download: [PDF]

Entry Submitted: 11/01/2018
Entry Accepted: 11/01/2018
Entry Last Modified: 10/14/2019

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