Geodesic
Upper bounds for goal functions of discrete competitive facility location problems
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 4, pp. 3-24.

Voir la notice de l'article provenant de la source Math-Net.Ru

The facility location problems in the presence of competition are considered, when two competitive firms open facilities sequentially and each client selects one of the open facilities according to his preferences and profits either the first firm (Leader) or the second (Follower). The problem is to find a facility location for the Leader which maximizes its profits with the optimal reaction of the Follower taken into account. The formulations which differ in the Follower's goal function are considered. The models are formulated as bilevel linear integer programming problems and equivalent formulations of these problems are presented in the form of the bilevel pseudo-Boolean programming. A polynomial time algorithm for the problems is presented in the case, where facilities and clients are points of a path. A method of construction of an upper bound for optimal values of the Leader's profit is proposed. The corresponding algorithm consists in construction of an auxiliary pseudo-Boolean function and computing an optimal solution yielding minimal value of this function. Computational results illustrate the good performance of the upper bound for the test examples of the problem on a path. Table 1, illustr. 1, bibl. 15.
Keywords: bilevel programming problem, upper bound, pseudo-Boolean function.
Mots-clés : optimal solution 
@article{DA_2008_15_4_a0,
     author = {V. L. Beresnev},
     title = {Upper bounds for goal functions of discrete competitive facility location problems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--24},
     publisher = {mathdoc},
     volume = {15},
     number = {4},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_4_a0/}
}
TY  - JOUR
AU  - V. L. Beresnev
TI  - Upper bounds for goal functions of discrete competitive facility location problems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 3
EP  - 24
VL  - 15
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_4_a0/
LA  - ru
ID  - DA_2008_15_4_a0
ER  - 
%0 Journal Article
%A V. L. Beresnev
%T Upper bounds for goal functions of discrete competitive facility location problems
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 3-24
%V 15
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2008_15_4_a0/
%G ru
%F DA_2008_15_4_a0
V. L. Beresnev. Upper bounds for goal functions of discrete competitive facility location problems. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 4, pp. 3-24. http://geodesic.mathdoc.fr/item/DA_2008_15_4_a0/

[1] Alekseeva E. V., Kochetov Yu. A., “Geneticheskii lokalnyi poisk dlya zadachi o $p$-mediane s predpochteniyami klientov”, Diskret. analiz i issled. operatsii. Ser. 2, 14:1 (2007), 3–13 | MR

[2] Bellman R., Dreifus S., Prikladnye zadachi dinamicheskogo programmirovaniya, Nauka, M., 1965, 460 pp. | Zbl

[3] Beresnev V. L., Diskretnye zadachi razmescheniya i polinomy ot bulevykh peremennykh, Izd-vo In-ta matematiki, Novosibirsk, 2005, 408 pp.

[4] Campos C., Moreno J. A., “Multiple voting location problems”, Eur. J. Oper. Res. (to appear)

[5] Canovas L., Garsia S., Labbe M., Marin A., “A stengthened formulation for the simple plant location problems with order”, Oper. Res. Letters, 35 (2007), 141–150 | DOI | MR | Zbl

[6] Eiselt H. A., Laporte G., “Sequential location problems”, Eur. J. Oper. Res., 96 (1996), 217–231 | DOI

[7] Dempe S., Foundations of bilevel programming, Kluwer Ac. Publ., Dordrecht, 2002, 332 pp. | MR | Zbl

[8] Dobson G., Karmarkar U., “Competitive location on a network”, Oper. Res., 35 (1987), 565–574 | DOI | MR | Zbl

[9] Drezner Z., Hamacher H. W. (eds.), Facility location: applications and theory, Springer-Verl., Berlin, 2002, 457 pp. | MR

[10] Hammer P. L., Rudeanu S., Boolean method in operations research and related areas, Springer, Berlin, 1968, 330 pp. | MR | Zbl

[11] Mirchandani P. B., Francis R. L., Discrete location theory, John Wiley and Sons, New York, 1990, 555 pp. | MR | Zbl

[12] Plastria F., “Static competitive facility location: An overview of optimization approaches”, Eur. J. Oper. Res., 129 (2001), 461–470 | DOI | MR | Zbl

[13] Plastria F., Vanhaverbeke L., “Discrete models for competitive location with foresight”, Comput. Oper. Res., 35 (2008), 683–700 | DOI | Zbl

[14] Santos-Penãte D. R., Suárez-Vega R., Dorta-González P., “The leader – follower location model”, Networks and Spatial Economics, 7 (2007), 45–61 | DOI | MR | Zbl

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