Geodesic
A branch, bound, and cuts algorithm for the dynamic competitive facility location problem
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 5-26 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider a dynamic competitive facility location problem modeling an interaction of two competing parties (Leader and Follower) who place their facilities within a planning horizon split into several time periods. The Leader is assumed to open his/her facilities at the beginning of the planning horizon and does not change his/her decision later, while the Follower can modify his/her choice within each time period. We propose an algorithm that computes the best Leader’s decision and is built on the base of the branch-and-bound computational scheme. To compute upper bounds, a special relaxation of the initial bilevel problem strengthened with additional constraints (cuts) is used. The paper describes the construction of these constraints while utilizing auxiliary optimization problems; this provides the strongest cuts. On an instance of a dynamic competitive facility location on a network with three vertices, we demonstrate that the model is capable to take into account information regarding the changes of problem’s parameters along the time period. An implementation of the branch-and-bound algorithm shows a significant benefit from using the cuts specially designed for dynamic competitive models: it improves the upper bound’s quality and reduces the number of nodes in the branching tree. Illustr. 2, bibliogr. 8.
Keywords: competitive facility location problem, bilevel mathematical programming, exact method, Stackelberg game. 
@article{DA_2024_31_4_a0,
     author = {V. L. Beresnev and A. A. Melnikov},
     title = {A~branch, bound, and cuts algorithm for~the~dynamic competitive facility location~problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--26},
     year = {2024},
     volume = {31},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_4_a0/}
}
TY  - JOUR
AU  - V. L. Beresnev
AU  - A. A. Melnikov
TI  - A branch, bound, and cuts algorithm for the dynamic competitive facility location problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 5
EP  - 26
VL  - 31
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_4_a0/
LA  - ru
ID  - DA_2024_31_4_a0
ER  - 
%0 Journal Article
%A V. L. Beresnev
%A A. A. Melnikov
%T A branch, bound, and cuts algorithm for the dynamic competitive facility location problem
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 5-26
%V 31
%N 4
%U http://geodesic.mathdoc.fr/item/DA_2024_31_4_a0/
%G ru
%F DA_2024_31_4_a0
V. L. Beresnev; A. A. Melnikov. A branch, bound, and cuts algorithm for the dynamic competitive facility location problem. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 4, pp. 5-26. http://geodesic.mathdoc.fr/item/DA_2024_31_4_a0/

[1] Stackelberg H., The theory of the market economy, Oxford Univ. Press, Oxford, 1952, 289 pp.

[2] Mishra M., Singh S. P., Gupta M. P., “Location of competitive facilities: A comprehensive review and future research agenda”, Benchmarking, 30:4 (2022), 1171–1230 | DOI

[3] Eiselt H. A., Drezner Z., “Competitive location models: A review”, Eur. J. Oper. Res., 316:1 (2024), 5–18 | DOI | MR

[4] Santos-Penate D. R., Suarez-Vega R., Dorta-Gonzalez P., “The leader — follower location model”, Netw. Spat. Econ., 7 (2007), 45–61 | DOI | MR

[5] V. L. Beresnev and A. A. Melnikov, “Additional constraints for dynamic competitive facility location problem”, J. Appl. Ind. Math., 17:3 (2023), 483–490 | DOI | DOI | MR

[6] Current J., Ratick S., ReVelle C., “Dynamic facility location when the total number of facilities is uncertain: A decision analysis approach”, Eur. J. Oper. Res., 110:3 (1998), 597–609 | DOI

[7] Dempe S., “Bilevel optimization: Theory, algorithms, applications and a bibliography”, Bilevel optimization: Advances and next challenges, Springer, Cham, 2020, 581–672 | DOI | MR

[8] Beresnev V. L., Melnikov A. A., “Approximation of the competitive facility location problem with MIPs”, Comput. Oper. Res., 104 (2019), 139–148 | DOI | MR