  In the paper, 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, requiring customers to patronize
only a limited number of opening facilities and an outside option. We 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 and the outside
option, we show that 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 classic
submodular inequalities, enabling to obtain another MILP formulation with a
tighter linear programming (LP) relaxation. By extensive numerical experiments,
we show that the proposed B&C approach outperforms the state-of-the-art
generalized Benders decomposition approach by at least one order of magnitude.
Furthermore, it enables to solve CFLPLCR instances with 10000 customers and
2000 facilities.
