Improving the heuristic performance of Benders’ decomposition
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, few, if any, have been designed for Benders’ decomposition and 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. The general Benders’ decomposition 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 Benders’ decomposition to solve the auxiliary problems of all large neighbourhood search heuristics 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 improvements to the heuristic performance of Benders’ decomposition achieved by the trust region heuristic and a general large neighbourhood search enhancement technique.
Journal of Heuristics 27:615 – 648, 2021.
Download: Journal Article