EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Cover-based inequalities for the single-source capacitated facility location problem with customer preferences

Christina Büsing, Markus Leitner, Sophia Wrede

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →