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.
Citation
Department of Management Science, Lancaster University, January 2018