标题： 一种针对有限选择规则的大规模竞争设施选址问题的高效分支定界方法 显示英文标题

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

摘要： 在论文中，我们考虑了有限选择规则下的竞争性设施选址问题（CFLPLCR），该问题旨在开设一组设施以最大化新进入公司的净利润，要求顾客只能光顾有限数量的开放设施和一个外部选项。 我们提出了一种高效的分支切割（B&C）方法，基于新提出的混合整数线性规划（MILP）公式来解决CFLPLCR。 具体而言，通过建立概率函数的次模性，我们利用次模不等式为CFLPLCR开发了一个MILP公式。 对于每个顾客最多光顾一个开放设施和外部选项的特殊情况，我们证明次模不等式可以表征所考虑集合的凸包，并提供了一个紧凑的MILP公式。 此外，对于一般情况，我们通过顺序提升加强了次模不等式，从而得到一类面定义不等式。 所提出的提升后的次模不等式被证明比经典的次模不等式更强，能够获得另一个具有更紧线性规划（LP）松弛的MILP公式。 通过大量的数值实验，我们表明所提出的B&C方法比最先进的广义Benders分解方法至少提高一个数量级。 此外，它能够解决包含10000个顾客和2000个设施的CFLPLCR实例。 显示英文摘要

摘要： 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.