Sequential Competitive Facility Location: Exact and Approximate Algorithms
研究两家企业按顺序开设新设施、在概率选择模型下最大化市场份额的竞争选址问题，提出了精确求解的混合整数非线性规划转化和近似算法，并扩展到一般成本、外部竞争等场景。
In “Sequential Competitive Facility Location: Exact and Approximate Algorithms,” Qi et al. consider a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets and maximize their market shares of demand following a probabilistic choice model. They derive an equivalent, single-level mixed-integer nonlinear program (MINLP) reformulation of the bilevel MINLP and exploit the problem structures to derive valid inequalities based on submodularity and concave overestimation. They also develop an approximation algorithm with a constant approximation guarantee. They further study several extensions of CFLP that have general facility-opening costs, outside competitors, and diverse facility-planning decisions. Their approaches significantly accelerate the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods.