Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2016, 10:1, 61-68
Volume 23, No 1, 2016, P. 35-50
UDC 519.85
V. L. Beresnev and A. A. Melnikov
A capacitated competitive facility location problem
Abstract:
We consider a mathematical model relative to competitive location problems. In such problems, there are two competing sides which subsequently open their facilities aiming to “capture” clients and maximize profit. In our model, we assume that capacitiy of facilities are bounded. The model is formulated as a bi-level integer mathematical program and we study the problem of obtaining its optimal (cooperative) solution. It is shown that the problem can be reformulated as a problem of maximization of a pseudo-Boolean function with the number of arguments equal to the number of places available for facility opening. We propose an algorithm for calculation of an upper bound for values that the function takes on subsets which are specified by partial (0,1)-vectors.
Bibl. 15.
Keywords: bi-level programming, upper bound, competitive facility location.
DOI: 10.17377/daio.2016.23.493
Vladimir L. Beresnev 1,2
Andrey A. Melnikov 1,2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: beresnev@math.nsc.ru, melnikov@math.nsc.ru
Received 20 May 2015
Revised 22 June 2015
References
[1] V. L. Beresnev, Diskretnye zadachi razmeshcheniya i polinomy ot bulevykh peremennykh (Discrete Location Problems and Polynomials of Boolean Variables), Izd. Inst. Mat., Novosibirsk, 2005.[2] V. L. Beresnev, Local search algorithms for the problem of competitive location of enterprises, Avtom. Telemekh., No. 3, 12–27, 2012. Translated in Autom. Remote Control, 73, No. 3, 425–439, 2012.
[3] V. L. Beresnev, On the competitive facility location problem with a free choice of suppliers, Avtom. Telemekh., No. 4, 94–105, 2014. Translated in Autom. Remote Control, 75, No. 4, 668–676, 2014.
[4] V. L. Beresnev, E. N. Goncharov, and A. A. Mel’nikov, Local search with a generalized neighborhood in the optimization problem for pseudo-Boolean functions, Diskretn. Anal. Issled. Oper., 18, No. 4, 3–16, 2011. Translated in J. Appl. Ind. Math., 6, No. 1, 22–30, 2012.
[5] V. L. Beresnev and A. A. Mel’nikov, Approximate algorithms for the competitive facility location problem, Diskretn. Anal. Issled. Oper., 17, No. 6, 3–19, 2010. Translated in J. Appl. Ind. Math., 5, No. 2, 180–190, 2011.
[6] V. L. Beresnev and A. A. Mel’nikov, The branch-and-bound algorithm for a competitive facility location problem with the prescribed choice of suppliers, Diskretn. Anal. Issled. Oper., 21, No. 2, 3–23, 2014. Translated in J. Appl. Ind. Math., 8, No. 2, 177–189, 2014.
[7] A. V. Kononov, Yu. A. Kochetov, and A. V. Plyasunov, Competitive facility location models, Zh. Vychisl. Mat. Mat. Fiz., 49, No. 6, 1037–1054, 2009. Translated in Comput. Math. Math. Phys., 49, No. 6, 994–1009, 2009.
[8] A. A. Mel’nikov, Randomized local search for the discrete competitive facility location problem, Avtom. Telemekh., No. 4, 134–152, 2014. Translated in Autom. Remote Control, 75, No. 4, 700–714, 2014.
[9] A. V. Plyasunov and A. A. Panin, The pricing problem. Part I: Exact and approximate algorithms, Diskretn. Anal. Issled. Oper., 19, No. 5, 83–100, 2012. Translated in J. Appl. Ind. Math., 7, No. 2, 241-251, 2013.
[10] A. V. Plyasunov and A. A. Panin, The pricing problem. Part II: Computational complexity, Diskretn. Anal. Issled. Oper., 19, No. 6, 56–71, 2012. Translated in J. Appl. Ind. Math., 7, No. 3, 420-430, 2013.
[11] V. L. Beresnev, Branch-and-bound algorithm for a competitive facility location problem, Comput. Oper. Res., 40, No. 8, 2062–2070, 2013.
[12] S. Dempe, Foundations of Bilevel Programming, Kluwer Acad. Publ., Dordrecht, 2002.
[13] P. L. Hammer and S. Rudeanu, Pseudo-Boolean programming, Oper. Res., 17, No. 2, 233–261, 1969.
[14] J. Krarup and P. M. Pruzan, The simple plant location problem: Survey and synthesis, Eur. J. Oper. Res., 12, No. 1, 36–81, 1983.
[15] H. von Stackelberg, The Theory of the Market Economy, Hedge, London, 1952.
