An efficient branch-and-cut approach for large-scale competitive facility location problems with limited choice rule

We consider the competitive facility location problem with limited choice rule (CFLPLCR), which attempts to open a subset of facilities to maximize the net profit of a “newcomer” company, while assuming that customers will patronize only a limited number of high-utility opening facilities of each company, including both the newcomer and its competitors. We investigate the polyhedral structure of a mixed 0–1 set, defined by the function characterizing the probability of a customer patronizing the newcomer’s open facilities, and propose an efficient branch-and-cut (B&C) approach for the CFLPLCR based on newly proposed mixed integer linear programming (MILP) formulations. Specifically, by establishing the submodularity of the probability function, we develop an MILP formulation for the CFLPLCR using the submodular inequalities. For the special case where each customer patronizes at most one open facility of each company, the submodular inequalities can characterize the convex hull of the considered set and provide a compact MILP formulation. Moreover, for the general case, we strengthen the submodular inequalities by sequential lifting, resulting in a class of facet-defining inequalities. The proposed lifted submodular inequalities are shown to be stronger than the submodular inequalities, enabling to obtain another MILP formulation with a tighter linear programming (LP) relaxation. By extensive numerical experiments, we show that thanks to the very tight LP relaxation, the proposed B&C approach outperforms the state-of-the-art generalized Benders decomposition approach by at least one order of magnitude in terms of CPU time. Furthermore, it enables to solve CFLPLCR instances with 10000 customers and 2000 facilities.