An improved Benders decomposition algorithm for the tree of hubs location problem

The tree of hubs location problem is a particularly hard variant of the so called hub location problems. When solving this problem by a Benders decomposition approach, it is necessary to deal with both optimality and feasibility cuts. While modern implementations of the Benders decomposition method rely on Pareto-optimal optimality cuts or on rendering feasibility cuts based on minimal infeasible subsystems, a new cut selection scheme is devised here under the guiding principle of extracting useful information even when facing infeasible subproblems. The proposed algorithm outperforms two other modern variants of the method and it is capable of optimally solving instances five times larger than the ones previously reported on the literature.

► A Benders decomposition algorithm is devised for the tree of hubs location problem. ► A new Benders’ cut selection scheme is developed. ► The new scheme clearly outperforms two other modern cut generation procedures. ► Instances five times larger than the ones previously reported are optimally solved. ► The new procedure can be use to tackle other types of problems.