Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design

摘要

This paper presents two exact algorithms based on Benders decomposition for solving the multicommodity uncapacitated fixed-charge network design problem. The first is a branch-and-cut algorithm based on a Benders reformulation enhanced with an in-tree matheuristic to obtain improved feasible solutions, valid inequalities in the projected master problem space to close the linear programming gap, and a tailored core point selection criterion from which significant time savings are obtained. The second exact algorithm exploits the problem's structure to combine a cut-and-solve strategy with Benders decomposition. Extensive computational experiments show both exact algorithms provide a speed-up of up to three orders of magnitude compared to a state-of-the-art general-purpose MIP solver's branch-and-cut and blackbox Benders decomposition algorithms. (C) 2019 Elsevier Ltd. All rights reserved.