Stable formulations for the Capacitated Facility Location Problem with Customer Preferences
Concepción Domínguez ∗, Juan de Dios Jaime-Alcántara · 2025
Read Stable formulations for the Capacitated Facility Location Problem with Customer Preferences by Concepción Domínguez ∗, Juan de Dios Jaime-Alcántara (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-21944.txt.
Introduction
Concepción Domínguez and Juan de Dios Jaime-Alcántara study fair placement when customers have favorite facilities in a 2025 paper. The classic problem opens a subset of plants and assigns each customer to their best open plant, at the lowest total cost. Their version adds capacity: each plant can serve only so many customers.
With capacity in play, stability needs new definitions. The authors craft three kinds: customer stable, pairwise stable, and cyclic-coalition stable assignments, and give two integer programming formulations for each. The strongest kind is Pareto optimal, meaning no customer can do better without another doing worse. Wide computer experiments compare the new assignments with older ones from the literature. A bonus result gives best-possible matchings for a cousin problem, assigning houses under capacity, at full size.
Catalog record
| CREATOR | Concepción Domínguez ∗, Juan de Dios Jaime-Alcántara |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-21944
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Stable formulations for the Capacitated Facility Location Problem with Customer Preferences Concepción Domínguez ∗, Juan de Dios Jaime-Alcántara Abstract In the Simple Plant Location Problem with Order (SPLPO), the aim is to open a subset of plants to assign every customer taking into account their preferences. Customers rank the plants in strict order and are assigned to their favorite open plant, and the objective is to minimize the location plus allocation costs. Here, we study a generalization of the SPLPO named the Capacitated Facility Location Problem with Customer Preferences (CFLCP) where a limited number of customers can be allocated to each facility. We consider the global preference maximization setting, where the customers preferences are globally maximized. For this setting, we define three new types of stable allocations, namely customer stable, pairwise stable and cyclic-coalition stable allocations, and we provide two mixed-integer linear formulations for each setting. In particular, our cyclic-coalition stable formulations are Pareto optimal in a global-preference maximization setting, in the sense that no customer can improve their allocation without making another one worse off. We provide extensive computational experiments and compare the quality of our allocations with previous ones defined in the literature. As an additional result, we present a novel formulation that provides Pareto optimal matchings in the Capacitated House Allocation problem of maximum cardinality. 1 Introduction The Simple Plant Location Problem with Order (SPLPO) is a generalization of the well-known Facility Location Problem (FLP) that takes into account customers’ preferences over the plants in the allocation process. The aim of SPLPO is to open a number of facilities from a set of candidate ones and allocate every customer, minimizing the overall cost of location plus allocation. Customers have certain preferences over the candidate locations that may be related to their size, distance, and other features, and they express their preferences ranking the candidate locations from the best to the worst (ties are not allowed in this setting). Once the plants are installed, each customer is assigned to their favorite open plant. It is assumed that the locator plays no role in the allocation of customers but has full knowledge of their rankings when making the location decision. SPLPO was introduced in Hanjoul and Peeters 1987 , where the state-of-the-art formulation available to this day is provided and a heuristic is developed to tackle small instances. Hansen et al. 2004 introduce a bilevel formulation that is then reformulated into a linear model in several ways, the best being the same formulation given by Hanjoul and Peeters. Cánovas et al. 2007 build upon the work from Hanjoul and Peeters 1987 , developing some valid inequalities as well as a basic preprocessing analysis, and Vasil’ev et al. 2009 also derive new valid inequalities based on the subyacent set packing polytope. The efficiency of said family of valid inequalities is checked in Vasilyev and Klimentova 2010 by implementing a cutting plane algorithm to find an optimal solution. A simulated annealing method is used to obtain the upper bounds in these exact methods. Vasilyev et al. 2013 carry out a polyhedral analysis of the problem, stating which inequalities are facet defining and developing a new set of facet-defining valid inequalities that are tested through extensive computational experiments. Very recently, Cabezas and García 2023 study some advantages of using a Lagrangian and semi-Lagrangian approach for the SPLPO, and they use the solution of a Lagrangian relaxation algorithm as the starting point of a semi-Lagrangian relaxation method. Then they apply a variable fixing heuristic to find good feasible solutions (often the optimal solution) in a so-called semi-Lagrangian relaxation heuristic algorithm. Note that, if the ranking is given by the distance to the facilities, then the preference constraints included in Hanjoul and Peeters 1987 and subsequent works match the well-known Closest Assignment Constraints (CAC). See Espejo et al. 2012 for a detailed comparison of CAC in integer programming. In this work, we study an extension of SPLPO where each facility has a capacity constraint, that is, a limited number of customers that can be allocated to it. The problem is known as Capacitated Facility Location with Customer’s Preferences (CFLCP). This is a much more general setting with many more realistic applications, such as assigning children to schools, students to universities, and patients to hospitals, among others. Its counterpart without customer preferences, the Capacitated Facility Location (CFL) problem, has been thoroughly studied ( Avella and Boccia 2009 ; Görtz and Klose 2012 ; Fernández and Landete 2015 ; Fischetti et al. 2016 , without being exhaustive, see e.g.) . However, the combination of a cardinality constraint and customers with preferences makes the allocation rule unclear. In fact, knowing the preferences of customers and taking them into account when selecting the facilities to be opened is not enough to properly define the assignments in the presence of capacity constraints. Thus, additional assumptions regarding the customers’ preferences and willingness to exchange locations are necessary and result in various allocation rules that give rise to different problems and formulations. This might be the reason why there are only a handful of references in the location literature that combine these two ingredients. There are two main approaches to customer allocation. In the first, customers are assigned to their favorite open plant, as in SPLPO. This approach corresponds to an individual preference maximization setting. Naturally, CAC are to be used to model the problem and facilities that are overloaded cannot ever be opened (note that the overloading of a facility depends on the rest of the open facilities). To the best of our knowledge, there are only two works focusing on this approach. Büsing et al. 2022 analyze the CFLCP if it is defined on a graph, where the assignment costs are equal to the distances between the customer nodes and the facility nodes. They derive some settings that are NP-complete and some that are polynomially solvable, closing the research gap regarding the computational complexity of FLPs with CAC mixed with capacity and revenue constraints. Büsing et al. 2025 build upon the previous work and contribute two novel preprocessing methods, which reduce the size of the considered integer programming formulation. Furthermore, they introduce sets of valid inequalities that decrease the integrality gaps. The second approach is the one followed in this article and consists in a global preference maximization setting. In this case, any facility can be opened, and if a facility is overloaded customers can be served at their next favorite one. The few works that follow this approach all introduce bilevel formulations with a second-level global-preference maximization problem. The authors of Calvete et al. 2020 introduce a bilevel formulation that is then reformulated into a single-level mixed-integer problem using duality theory. They also develop a matheuristic based on an evolutionary algorithm and compare the performance of both approaches. We build upon the work developed in this article, as it serves as motivation for the formulations hereby introduced. In Casas-Ramírez et al. 2018 , a very similar bilevel model is proposed for a slightly different setting where each customer has a demand and the capacity of a facility refers to the amount of demand it can deal with. This fact increases the difficulty of the resultant second-level formulation, which