Sequential Competitive Facility Location: Exact and Approximate Algorithms

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 U) and Ruiwei Jiang (U of Michigan).

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

---

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.

---