Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 29, No 3, 2022, P. 7-23
UDC 519.8+518.25
V. L. Beresnev and A. A. Melnikov
Computing an upper bound in the two-stage bi-level competitive location model
Abstract:
We consider a competitive facility location problem with uncertainty represented by a finite number of possible demand scenarios. The problem is formulated as a bi-level model built on the base of a Stackelberg game and classic facility location model formalizing the players’ decision process. In the bi-level model, the first player (Leader) has two options to open a facility. We assume that a Leader’s facility could be opened either before the actual demand scenario is revealed or after the revelation. The fixed costs associated with the facility opening are lower in the first case. Thus the fixed costs could be reduced by making a preliminary location decision on the first stage and adjusting it on the second.
We suggest a procedure to compute an upper bound for the Leader’s profit value. The approach is based on using a family of auxiliary bilevel subproblems. Optimal solutions of the subproblems form a feasible solution of the initial problem. The upper bound is computed by applying a cut generation procedure to strengthen high-point relaxations of the subproblems.
Tab. 1, illustr. 1, bibliogr. 10.
Keywords: Stackelberg game, binary customer’s behavior rule, bilevel location model, pessimistic optimal solution.
DOI: 10.33048/daio.2022.29.740
Vladimir L. Beresnev 1
Andrey A. Melnikov 1
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
e-mail: beresnev@math.nsc.ru, melnikov@math.nsc.ru
Received May 16, 2022
Revised May 18, 2022
Accepted May 19, 2022
References
[1] V. L. Beresnev, On the competitive facility location problem with a free choice of suppliers, Avtom. Telemekh., No. 4, 93–106 (2014) [Russian] [Autom. Remote Control 75 (4), 668–676 (2014)].[2] M. G. Ashtiani, A. Makui, and R. Ramezanian, A robust model for a leader-follower competitive facility location problem in a discrete space, Appl. Math. Model. 37 (1–2), 62–71 (2013).
[ 3] W. Yu, A leader-follower model for discrete competitive facility location problem under the partially proportional rule with a threshold, PLOS ONE 14 (12), ID e0225693, 16 p. (2019).
[4] S. V. Ivanov and M. V. Morozova, Stochastic problem of competitive location of facilities with quantile criterion, Avtom. Telemekh., No. 3, 109–122 (2016) [Russian] [Autom. Remote Control 77 (3), 451–461 (2016)].
[5] V. L. Beresnev and A. A. Melnikov, $\epsilon$-Constraint method for bi-objective competitive facility location problem with uncertain demand scenario, EURO J. Comput. Optim. 8 (1), 33–59 (2020).
[6] S. V. Ivanov and V. N. Akmaeva, Two-stage stochastic facility location model with quantile criterion and choosing reliability level, Vestn. YuUrGU, Ser. Mat. Model. Program. 14 (3), 5–17 (2021).
[7] V. L. Beresnev and A. A. Melnikov, Approximation of the competitive facility location problem with MIPs, Comput. Oper. Res. 104, 139–148 (2019).
[8] J. T. Moore and J. F. Bard, The mixed integer linear bilevel programming problem, Oper. Res. 38 (5), 911–921 (1990).
[9] V. L. Beresnev, Branch-and-bound algorithm for a competitive facility location problem, Comput. Oper. Res. 40 (8), 2062–2070 (2013).
[10] Gurobi optimizer reference manual (Gurobi Optimization, Beaverton, 2021).
Available at www.gurobi.com/documentation/9.5/refman/index.html (accessed May 16, 2022).
