Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing
Weninger D, Wolsey LA (2023)
Publication Type: Journal article
Publication year: 2023
Journal
DOI: 10.1016/j.ejor.2023.02.042
Abstract
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 xj indicating whether faclility j is used or not and yij 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, a CPLEX version of Benders and a recent cut-and-solve approach developed specifically for CFLP-SS. Our results show that for CFLP-SS, when the percentage of clients requiring single-sourcing is less equal than 25%, the Benders’ variants achieve speedups of between 1.2 and 3.7.
Authors with CRIS profile
Involved external institutions
Belgium (BE)How to cite
APA:
Weninger, D., & Wolsey, L.A. (2023). Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing. European Journal of Operational Research. https://dx.doi.org/10.1016/j.ejor.2023.02.042
MLA:
Weninger, Dieter, and Laurence A. Wolsey. "Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing." European Journal of Operational Research (2023).
BibTeX: Download