Cuong Le, Tien Mai, Ngan Ha Duong, Minh Hoang Ha
arXiv 22 Dec 2024 · Mathematics — Optimization
arXiv:2412.17021 · PDF · DOI · OpenAlex · Extracted main text
We study a competitive facility location problem, where customer behavior is modeled and predicted using a discrete choice random utility model. The goal is to strategically place new facilities to maximize the overall captured customer demand in a competitive marketplace. In this work, we introduce two novel considerations. First, the total customer demand in the market is not fixed but is modeled as an increasing function of the customers' total utilities. Second, we incorporate a new term into the objective function, aiming to balance the firm's benefits and customer satisfaction. Our new formulation exhibits a highly nonlinear structure and is not directly solved by existing approaches. To address this, we first demonstrate that, under a concave market expansion function, the objective function is concave and submodular, allowing for a $(1-1/e)$ approximation solution by a simple polynomial-time greedy algorithm. We then develop a new method, called Inner-approximation, which enables us to approximate the mixed-integer nonlinear problem (MINLP), with arbitrary precision, by an MILP without introducing additional integer variables. We further demonstrate that our inner-approximation method consistently yields lower approximations than the outer-approximation methods typically used in the literature. Moreover, we extend our settings by considering a general (non-concave) market-expansion function and show that the Inner-approximation mechanism enables us to approximate the resulting MINLP, with arbitrary precision, by an MILP. To further enhance this MILP, we show how to significantly reduce the number of additional binary variables by leveraging concave areas of the objective function. Extensive experiments demonstrate the efficiency of our approaches.
appendix boundary found by appendix_command · 70% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Mai, T. and Lodi, A (2020) A multicut outer-approximation approach for competitive facility location under random utilities self | 1.000 | 13 | 6 | 100% |
| 2 | Train, K. E (2009) Discrete choice methods with simulation | 1.000 | 6 | 4 | 100% |
| 3 | Aboolian, R., Berman, O., and Krass, D (2007) Competitive facility location model with concave demand | 1.000 | 5 | 4 | 100% |
| 4 | Ljubić, I. and Moreno, E (2018) Outer approximation and submodular cuts for maximum capture facility location problems with random utilities | 1.000 | 5 | 4 | 100% |
| 5 | Duran, M. A. and Grossmann, I. E (1986) An outer-approximation algorithm for a class of mixed-integer nonlinear programs | 1.000 | 5 | 3 | 100% |
| 6 | Dam, T. T., Ta, T. A., and Mai, T (2022) Submodularity and local search approaches for maximum capture problems under generalized extreme value models self | 0.928 | 4 | 3 | 100% |
| 7 | Lin, Y. H., Tian, Q., and Zhao, Y (2022) Locating facilities under competition and market expansion: Formulation, optimization, and implications | 0.928 | 4 | 3 | 100% |
| 8 | Benati, S. and Hansen, P (2002) The maximum capture problem with random utilities: Problem formulation and algorithms | 0.843 | 3 | 3 | 100% |
| 9 | Aboolian, R., Berman, O., and Krass, D (2007) Competitive facility location and design problem | 0.737 | 3 | 2 | 100% |
| 10 | Haase, K (2009) Discrete location planning | 0.644 | 4 | 1 | 100% |
Showing the top 10 of 35 scored citations.