Subject：Sequential Competitive Facility Location: Exact and Approximate Algorithms

Guest：Jiang Ruiwei, Associate Professor, University of Michigan

Host：Cao Yufeng, Assistant Professor, ACEM-SJTU

Time：Wednesday, April 27, 2022, 10:00-11:30

Venue: Tencent Meeting

（Please send email to mliu18@sjtu.edu.cn by 18:00 April. 26th for meeting number and password.）

Abstract:

We study a competitive facility location problem (CFLP), in which two firms sequentially select locations of new facilities, in order to maximize their market shares of customer demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. Through integer programming methods, we derive an equivalent, single-level MINLP reformulation. In addition, we exploit the problem structures and derive two classes of valid inequalities, one based on submodularity and the other based on concave overestimation. We apply these inequalities in a branch-and-cut algorithm to find a globally optimal solution to CFLP. Furthermore, we propose an approximation algorithm for solving CFLP that is computationally more effective. Notably, this algorithm admits a constant approximation guarantee. Extensive numerical studies demonstrate that the exact algorithm can significantly accelerate the solving of CFLP on problem instances that have not been solved to optimality by existing methods. The approximation algorithm can find near-optimal solutions even more quickly.This is joint work with Mingyao Qi (Tsinghua University) and Siqian Shen (University of Michigan).

Guest Bio:

Ruiwei Jiang is an Associate Professor of Industrial & Operations Engineering at the University of Michigan. He conducts research on the theory of stochastic and robust optimization, integer programming, and their applications on power systems and healthcare operations. Ruiwei’s research has been recognized with an NSF Career Award, two INFORMS Junior Faculty Interest Group paper prizes, and an INFORMS George Nicholson student paper award.