A capacitated competitive facility location problem

详细信息    查看全文

• 作者：V. L. Beresnev ; A. A. Melnikov
• 关键词：bilevel programming ; upper bound ; competitive facility location
• 刊名：Journal of Applied and Industrial Mathematics
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：10
• 期：1
• 页码：61-68
• 全文大小：530 KB
• 参考文献：1.V. L. Beresnev, Discrete Location Problems and Polynomials of Boolean Variables (Inst. Mat., Novosibirsk, 2005) [in Russian].MATH
  2.V. L. Beresnev, “Local Search Algorithms for the Problem of Competitive Location of Enterprises,” Avtomat. i Telemekh. No. 3, 12–27 (2012) [Automat. Remote Control 73 (3), 425–439 2012].MathSciNet MATH
  3.V. L. Beresnev, “On the Competitive Facility Location Problem with a Free Choice of Suppliers,” Avtomat. i Telemekh. No. 4, 94–105 (2014) [Automat. Remote Control 75 (4), 668–676 2014].MathSciNet MATH
  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,” Diskret. Anal. Issled. Oper. 18 (4), 3–16 (2011) [J. Appl. Indust. Math. 6 (1), 22–30 2012].MATH
  5.V. L.Beresnev and A. A. Mel’nikov, “ApproximateAlgorithms for the Competitive Facility Location Problem,” Diskret. Anal. Issled. Oper. 17 (6), 3–19 (2010) [J. Appl. Indust. Math. 5 (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,” Diskret. Anal. Issled. Oper. 21 (2), 3–23 (2014) [J. Appl. Indust. Math. 8 (2), 177–189 2014].MathSciNet MATH
  7.A. V. Kononov, Yu. A. Kochetov, and A. V. Plyasunov, “Competitive Facility Location Models,” Zh. Vychisl. Mat. Mat. Fiz. 49 (6), 1037–1054 (2009) [Comput. Math. Math. Phys. 49 (6), 994–1009 2009].MathSciNet MATH
  8.A. A. Mel’nikov, “Randomized Local Search for the Discrete Competitive Facility Location Problem,” Avtomat. i Telemekh. No. 4, 134–152 (2014) [Automat. Remote Control 75 (4), 700–714 2014].MathSciNet MATH
  9.A.V. Plyasunov and A. A. Panin, “The Pricing Problem. Part I: Exact and Approximate Algorithms,” Diskret. Anal. Issled. Oper. 19 (5), 83–100 (2012) [J. Appl. Indust. Math. 7 (2), 241-251 (2013)].MATH
  10.A. V. Plyasunov and A. A. Panin, “The Pricing Problem. Part II: Computational Complexity,” Diskret. Anal. Issled. Oper. 19 (6), 56–71 (2012) [J. Appl. Indust. Math. 7 (3), 420-430 (2013)].MathSciNet MATH
  11.V. L. Beresnev, “Branch-and-Bound Algorithm for a Competitive Facility Location Problem,” Comput. Oper. Res. 40 (8), 2062–2070 (2013).MathSciNet CrossRef
  12.S. Dempe, Foundations of Bilevel Programming (Kluwer Acad. Publ., Dordrecht, 2002).MATH
  13.P. L. Hammer and S. Rudeanu, “Pseudo-Boolean Programming,” Oper. Res. 17 (2), 233–261 (1969).MathSciNet CrossRef MATH
  14.J. Krarup and P.M. Pruzan, “The Simple Plant Location Problem: Survey and Synthesis,” European J.Oper. Res. 12 (1), 36–81 (1983).MathSciNet CrossRef MATH
  15.H. von Stackelberg, The Theory of the Market Economy (Hedge, London, 1952).
  
• 作者单位：V. L. Beresnev (1) (2)
  A. A. Melnikov (1) (2)
  
  1. Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia
  2. Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematics
  Russian Library of Science
  
• 出版者：MAIK Nauka/Interperiodica distributed exclusively by Springer Science+Business Media LLC.
• ISSN：1990-4797

文摘

We consider a mathematical model similar in a sense to competitive location problems. There are two competing parties that sequentially open their facilities aiming to “capture” customers and maximize profit. In our model, we assume that facilities’ capacities are bounded. The model is formulated as a bilevel integer mathematical program, and we study the problem of obtaining its optimal (cooperative) solution. It is shown that the problem can be reformulated as that 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 calculating an upper bound for values that the function takes on subsets which are specified by partial (0, 1)-vectors.