Optimization Online


Large neighbourhood Benders' search

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

Abstract: A general enhancement of the Benders' decomposition 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, their use is typically limited to finding solutions to the Benders' decomposition master problem, which may be of poor quality for the original problem or even infeasible. Given the lack of general frameworks for Benders' decomposition, only ad hoc approaches have been developed to enhance Benders' decomposition through the use of large neighbourhood search heuristics. Within the solver SCIP, a Benders' decomposition framework has been developed to achieve a greater integration with the internal large neighbourhood search heuristics. Benders' decomposition is employed to solve the auxiliary problems of all large neighbourhood search heuristics, the Large Neighbourhood Benders' Search, to improve the quality of the identified solutions and generate additional cuts that can be used to accelerate the convergence of the main solution algorithm. The computational results demonstrate the performance improvements achieved by this general enhancement technique for Benders' decomposition.

Keywords: Bender' decomposition, large-neighbourhood search, enhancement techniques, stochastic programming

Category 1: Stochastic Programming

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

Citation: Department of Management Science, Lancaster University, January 2018

Download: [PDF]

Entry Submitted: 01/08/2018
Entry Accepted: 01/08/2018
Entry Last Modified: 01/08/2018

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