Empirical Comparison of Unified Benders Cuts for Multi-Commodity Fixed-Charge Network Design

Among the many types of acceleration techniques designed to improve the performance of Benders decomposition, unified cut generation schemes have recently attracted a keen interest. Unified cuts aim for a better balance between the generation of optimality and feasibility cuts, while also providing a way to compare the strengths of different feasibility cuts. Our goal is to assess the experimental performance of a broad selection of unified and distinct Benders cuts in the context of the multi-commodity fixed-charge network design problem (MCFNDP).
We express under a common mathematical structure and notation the construction of each unified or distinct Benders cut considered. We also explain how the generic formulations of the Benders cuts can be specialized to conform to the specifications of the MCFNDP. In addition, we suggest bespoke methods for comparing the performance of several solution methods when the benchmark is made up of heterogeneous problem instances. We report the results of a systematic empirical analysis comparing the performances of 50 Benders methods involving unified or distinct cuts in applications to a common testing bench made up of standardized MCFNDP instances. The analysis identifies a small number of leading Benders methods, namely those featuring the static Brandenberg-Stursberg cuts and the Hosseini-Turner l1-deepest cuts. In addition, we also report results obtained by using both Gurobi and CPLEX as the supporting solver to the SMS++ computation library.