Cover-based inequalities for the single-source capacitated facility location problem with customer preferences
Computers & Operations Research · 2025-10 · 182 · 107082
DOI: 10.1016/j.cor.2025.107082 ↗Kurz gefasst
Fachartikel in der Zeitschrift Computers & Operations Research, 2025-10. Verfasst von Christina Büsing und 2 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Federal Ministry of Education and Research Bonn Office, German Research Foundation, RWTH Aachen University.
Abstract (Originalsprache)
The single-source capacitated facility location problem with customer preferences (SSCFLPCP) is known to be strongly NP-hard. Computational tests imply that state-of-the-art solvers struggle with computing exact solutions. In this paper, we contribute two novel preprocessing methods which reduce the size of the considered integer programming formulation, and introduce sets of valid inequalities which decrease the integrality gap. Each of the introduced results utilises structural synergies between capacity constraints and customer preferences in the SSCFLPCP. First, we derive two preprocessing methods where the first method fixes location variables and the second method fixes allocation variables. Afterwards, we study cover-based inequalities. Here, we first strengthen the well-known cover inequalities: when determining covers, we also consider demands of customers not in the cover that must be assigned to the covered facility if a customer in the cover is assigned to it. We further strengthen these inequalities by including information on the assignments of customers in a cover if they are not assigned to the covered facility. Afterwards, we derive a new family of valid inequalities, which expresses the relation of open facilities based on sets of customers covering a facility. We then discuss solution methods for the corresponding separation problems and, finally, test our results for two preference types in a computational study. Our results show a clear positive impact of the preprocessing methods and inequalities, in particular when preferences are defined by assignment costs.
Förderung
- Federal Ministry of Education and Research Bonn Office
- German Research Foundation
- RWTH Aachen University
- Volkswagen Foundation
Zitieren
APA
Büsing, C., Leitner, M., & Wrede, S. (2025). Cover-based inequalities for the single-source capacitated facility location problem with customer preferences. Computers & Operations Research, 182, 107082. https://doi.org/10.1016/j.cor.2025.107082
Vancouver
Büsing C, Leitner M, Wrede S. Cover-based inequalities for the single-source capacitated facility location problem with customer preferences. Computers & Operations Research. 2025;182:107082. doi:10.1016/j.cor.2025.107082
BibTeX
@article{Bsing2025,
author = {Büsing, Christina and Leitner, Markus and Wrede, Sophia},
title = {Cover-based inequalities for the single-source capacitated facility location problem with customer preferences},
journal = {Computers & Operations Research},
year = {2025},
volume = {182},
pages = {107082},
doi = {10.1016/j.cor.2025.107082}
}
EUVIMED