an accelerated benders decomposition approach for the multi-level multi-capacitated facility location problem

This paper studies the multi-level multi-capacitated facility location problem (ml-mclp), first introduced in 2022 as a double generalization of the capacitated p-median problem (cpmp). this problem aims to determine the optimal facilities to open at each level, and their appropriate capacities to meet customer demands while minimizing assignment costs. our main contribution lies in the development of an enhanced benders decomposition (bd) specifically tailored to the ml-mclp. to improve the convergence speed of the bd algorithm, we propose modern acceleration techniques, including subproblem reformulation and advanced cut selection strategies. the performance of the accelerated bd algorithm is evaluated using a dataset generated based on justified difficulty criteria and data generation methods from the literature. the results showed that hybridizing acceleration techniques improve convergence much more than applying a single one. however, the decomposition-based technique proved to be inefficient, particularly due to the structure of the ml-mclp, and was therefore excluded.