Sequential Competitive Facility Location: Exact and Approximate Algorithms

DOI10.1287/OPRE.2022.2339arXiv2103.04259OpenAlexW3134116700MaRDI QIDQ6198744FDOQ6198744

Authors: Mingyao Qi, Ruiwei Jiang, Siqian Shen 

Publication date: 20 March 2024

Published in: Operations Research (Search for Journal in Brave)

Abstract: We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation and exploit the problem structures to derive two valid inequalities, based on submodularity and concave overestimation, respectively. We use the two valid inequalities in a branch-and-cut algorithm to find globally optimal solutions. Then, we propose an approximation algorithm to find good-quality solutions with a constant approximation guarantee. We develop several extensions by considering general facility-opening costs, outside competitors, as well as diverse facility-planning decisions, and discuss solution approaches for each extension. We conduct numerical studies to demonstrate that the exact algorithm significantly accelerates the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods, and the approximation algorithm can quickly find high-quality solutions. We derive managerial insights based on sensitivity analysis of different settings that affect customers' probabilistic choices and the ensuing demand.

Full work available at URL: https://arxiv.org/abs/2103.04259

Recommendations

• Approximate algorithms for the competitive facility location problem
• scientific article; zbMATH DE number 6006831
• Bilevel models on the competitive facility location problem
• Exact method for the capacitated competitive facility location problem
• Approximation of the competitive facility location problem with MIPs

zbMATH Keywords

approximation algorithmsubmodularitybranch-and-cutmixed integer nonlinear programmingcompetitive facility locationconcave overestimation

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonlinear programming (90C30) Cooperative games (91A12) Mixed integer programming (90C11) Discrete location and assignment (90B80)

This page was built for publication: Sequential Competitive Facility Location: Exact and Approximate Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6198744)