  The P-median facility location problem with user preferences (PUP) studies an
operator that locates P facilities to serve customers/users in a cost-efficient
manner, upon anticipating customer preferences and choices. The problem can be
visualized as a leader-follower game in which the operator is the leader that
opens facilities, whereas the customer is the follower who observes the
operator's location decision at first and then seeks services from the most
preferred facility. Such a modeling perspective is of practical importance as
we have witnessed its applications to various problems, such as the
establishment of power plants in energy markets and the location of healthcare
service centers for COVID-19 Vaccination. Despite that a considerable number of
solution methodologies have been proposed, many of them are heuristic methods
whose solution quality cannot be easily verified. Moreover, due to the hardness
of the problems, existing exact approaches have limited performance. Motivated
by these observations, we aim to develop an efficient exact algorithm for
solving large-scale PUP models. We first propose a branch-and-cut decomposition
algorithm and then design accelerated techniques to further enhance the
performance. Using a broad testbed, we show that our algorithm outperforms
various exact approaches by a large margin, and the advantage can go up to
several orders of magnitude in terms of computational time in some datasets.
Finally, we conduct sensitivity analysis to draw additional implications and to
highlight the importance of considering user preferences when they exist.
