EURO 2025 Leeds
Abstract Submission

432. Enforcing Stability in Capacitated Facility Location Problem with Ordinal Customer Preferences.

Invited abstract in session MB-48: Advances in Location Analysis, stream Locational Analysis.

Monday, 10:30-12:00
Room: Parkinson B09

Authors (first author is the speaker)

1. Adam Dunajski
School of Mathematics, University of Edinburgh
2. Sergio García Quiles
School of Mathematics, University of Edinburgh
3. Akshay Gupte
School of Mathematics, University of Edinburgh

Abstract

Classically in facility location problems both the choice of location and the customer allocation is completed by a central decision maker, and customers cannot choose amongst the open facilities. However, customer preferences may not align with those of the decision maker. Here customers can act as strategic agents and deviate from a proposed allocation. Such freedom of choice is present, for example, in school choice in the UK. Here parents have a right to express preferences over state schools, and all schools (except grammar schools) must offer a place to every child who has applied if they have space.

This work focuses on how known ordinal customer preferences can be incorporated into integer linear programming formulations for the capacitated facility location problem. We build on the work of Hanjoul and Peeters (1987) on the uncapacitated variant and subsequent work strengthening their proposed formulations.

We incorporate solution concepts from the algorithmic game theory and stable matching communities, including Nash stability and swap stability, into the capacitated problem. Both single source (each customer must have their entire demand satisfied by a single facility) and fractional (the demand of a customer can be split over multiple facilities) allocations are considered.

We propose new integer linear programming formulations which enforce the stability notions, and demonstrate their performance on benchmark instances.

Keywords

Status: accepted

Back to the list of papers