RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., 2008, Volume 15, Number 4, Pages 3–24 (Mi da537)

Upper bounds for goal functions of discrete competitive facility location problems

V. L. Beresnev

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: 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, optimal solution, pseudo-Boolean function.

Full text: PDF file (305 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2009, 3:4, 419–432

Bibliographic databases:

UDC: 519.87

Citation: V. L. Beresnev, “Upper bounds for goal functions of discrete competitive facility location problems”, Diskretn. Anal. Issled. Oper., 15:4 (2008), 3–24; J. Appl. Industr. Math., 3:4 (2009), 419–432

Citation in format AMSBIB
\Bibitem{Ber08} \by V.~L.~Beresnev \paper Upper bounds for goal functions of discrete competitive facility location problems \jour Diskretn. Anal. Issled. Oper. \yr 2008 \vol 15 \issue 4 \pages 3--24 \mathnet{http://mi.mathnet.ru/da537} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2543596} \zmath{https://zbmath.org/?q=an:1249.90095} \transl \jour J. Appl. Industr. Math. \yr 2009 \vol 3 \issue 4 \pages 419--432 \crossref{https://doi.org/10.1134/S1990478909040012} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77749255765} 

• http://mi.mathnet.ru/eng/da537
• http://mi.mathnet.ru/eng/da/v15/i4/p3

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. J. Appl. Industr. Math., 4:2 (2010), 147–157
2. V. L. Beresnev, A. A. Melnikov, “Priblizhennye algoritmy dlya zadachi konkurentnogo razmescheniya predpriyatii”, Diskretn. analiz i issled. oper., 17:6 (2010), 3–19
3. V. L. Beresnev, E. N. Goncharov, A. A. Mel'nikov, “Local search over generalized neighborhood for an optimization problem of pseudo-Boolean functions”, J. Appl. Industr. Math., 6:1 (2012), 22–30
4. A. V. Naumov, I. M. Bobylev, “On the two-stage problem of linear stochastic programming with quantile criterion and discrete distribution of the random parameters”, Autom. Remote Control, 73:2 (2012), 265–275
5. V. L. Beresnev, “Local search algorithms for the problem of competitive location of enterprises”, Autom. Remote Control, 73:3 (2012), 425–439
6. Beresnev V., “Branch-and-Bound Algorithm for a Competitive Facility Location Problem”, Comput. Oper. Res., 40:8 (2013), 2062–2070
7. S. V. Ivanov, “Bilevel stochastic linear programming problems with quantile criterion”, Autom. Remote Control, 75:1 (2014), 107–118
8. V. L. Beresnev, A. A. Melnikov, “Branch-and-bound method for the competitive facility location problem with prescribed choice of suppliers”, J. Appl. Industr. Math., 8:2 (2014), 177–189
9. A. A. Mel'nikov, “Computational complexity of the discrete competitive facility location problem”, J. Appl. Industr. Math., 8:4 (2014), 557–567
10. Rahmani A., MirHassani S.A., “Lagrangean Relaxation-Based Algorithm For Bi-Level Problems”, Optim. Method Softw., 30:1 (2015), 1–14
11. MirHassani S.A., Raeisi S., Rahmani A., “Quantum Binary Particle Swarm Optimization-Based Algorithm For Solving a Class of Bi-Level Competitive Facility Location Problems”, Optim. Method Softw., 30:4 (2015), 756–768
12. S. V. Ivanov, M. V. Morozova, “Stochastic problem of competitive location of facilities with quantile criterion”, Autom. Remote Control, 77:3 (2016), 451–461
13. Karakitsiou A., Migdalas A., “Locating Facilities in a Competitive Environment”, Optim. Lett., 11:5 (2017), 929–945
14. Aras N., Kucukaydin H., “Bilevel Models on the Competitive Facility Location Problem”, Spatial Interaction Models: Facility Location Using Game Theory, Springer Optimization and Its Applications, 118, eds. Mallozzi L., DAmato E., Pardalos P., Springer, 2017, 1–19
15. Rahmani A., Yousefikhoshbakht M., “An Effective Branch-and-Cut Algorithm in Order to Solve the Mixed Integer Bi-Level Programming”, Int. J. Prod. Manag. Engineering, 5:1 (2017), 1–10
16. Nasiri M.M., Mahmoodian V., Rahbari A., Farahmand Sh., “A Modified Genetic Algorithm For the Capacitated Competitive Facility Location Problem With the Partial Demand Satisfaction”, Comput. Ind. Eng., 124 (2018), 435–448
•  Number of views: This page: 538 Full text: 130 References: 36 First page: 8