We consider the capacitated facility location problem with (partial) single-sourcing (CFLP-SS). A natural mixed integer formulation for the problem involves 0-1 variables x_j indicating whether faclility j is used or not and y_{ij} variables indicating the fraction of the demand of client i that is satisfied from facility j. When the x variables are fixed, the remaining problem is a transportation problem with single-sourcing. This structure suggest the use of a Benders’ type decomposition algorithm. Here we present three possible variants. Applied to CFLP-SS they are compared computationally with a commercial solver (CPLEX) on the original formulation and a CPLEX version of Benders. Our results show that for CFLP-SS, when the percentage of clients requiring single-sourcing is less equal than 25%, the Benders’ variants achieve a speedup of between 1.2 and 3.7.
Citation
Friedrich-Alexander Universität Erlangen-Nürnberg, 04/2022