Facility location problems (FLPs) play an essential role in the operations research literature due to their applicability to many real-world problems. In their basic version, FLPs consist in choosing sites for opening facilities to provide some service for customers, and assigning these customers to open facilities. The aim is to minimise the total opening and assignment costs. The individual needs of customers, however, are neglected by this objective: Customers are treated as passive participants who will gladly follow their determined assignment. This is acceptable if customers correspond to inanimate objects, yet might lack realism if customers are actual people. In this talk, we study a variation of the basic FLP in which we are given a preference ranking of all facilities for each customer. Furthermore, we associate each customer with a demand, and each facility with a capacity for serving customer demands. In addition to the basic objective, each customer now has to be served at exactly one of their most-preferred open facilities and the capacity at each open facility has to be respected. This problem is known as the single-source capacitated facility location problem with customer preferences (CFLP-CP).

We analyse combinatorial structures and exact methods for the CFLP-CP. While the problem’s strong NP-completeness is expected, we observe that the structure of the customer preferences has an important impact on the problem’s complexity. Furthermore, we discuss cover-based inequalities for integer programs by utilising combinatorial structures implied by customer preferences. In a computational study, we observe that our inequalities successfully reduce the integrality gap. We furthermore propose a solver-free combinatorial branch-and-bound (B&B) algorithm for the CFLP-CP with strict customer preferences, which utilises insights from our analysis of the problem’s combinatorial structures. In a second computational study, we observe that our B&B algorithm finds better primal solutions for more instances than a state-of-the-art solver and, if slowly, makes progress on solving instances with 1000 customers and 1000 facilities for which a state-of-the-art solver fails.