An Accelerated Benders Decomposition Approach for the Multi-Level Multi-Capacitated Facility Location Problem

In this paper, we study the Multi-Level Multi-Capacitated Facility Location Problem (ML-MCLP), which was first introduced in 2022 as a double generalization of the Capacitated P-Median Problem (CPMP). The objective of this problem is to determine the optimal facilities to open at each level, and their appropriate capacities to meet customer demands, while minimizing assignment costs. We adopt the Benders Decomposition exact approach, complemented by modern acceleration techniques to enhance convergence speed. 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 hybridization of acceleration techniques, such as subproblem reformulation and cut selection, significantly improves convergence. However, decomposition-based technique proved to be inefficient, particularly due to the structure of the ML-MCLP, and was therefore excluded.