Abstract
We consider the bilevel mixed integer location and pricing problems. Each problem is determined by the optimization problems of the upper and lower levels of which the first describes the choice of location and pricing, while the second models the reaction of the customers on the upper-level solution. The article focuses on studying the computational complexity of bilevel problems with various pricing strategies: uniform, mill, and discriminatory pricing. We show that, for an arbitrary pricing strategy, the corresponding optimization problem is NP-hard in the strong sense, belongs to the class Poly-APX, and is complete in it with respect to AP-reducibility.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (San Francisco, Freeman, 1979; Mir, Moscow, 1982).
Yu. A. Kochetov and A. V. Plyasunov, “Polynomially Solvable Class of the Problems of Bilevel Linear Programming,” Diskret. Anal. Issled. Oper. Ser. 2, 1(2), 23–33 (1997).
A. A. Panin and A. V. Plyasunov, “The Pricing Problem. I: Exact and Approximate Algorithms,” Diskret. Anal. Issled. Oper. 19(2), 31–40 (2012) [J. Appl. Industr. Math. 7 (2), 241–251 (2013)].
A. A. Panin and A.V. Plyasunov, “The Pricing Problem. II: Computational Complexity,” Diskret. Anal. Issled. Oper. 19(6), 56–71 (2012) [J. Appl. Industr. Math. 7 (3), 420–430 (2013)].
R. Aboolian, O. Berman, and D. Krass, “Competitive Facility Location Model with Concave Demand,” European J. Oper. Res. 181, 598–619 (2007).
R. Aboolian, O. Berman, and D. Krass, “Optimizing Pricing and Location Decisions for Competitive Service Facilities Charging Uniform Price,” J. Oper. Res. Soc. 59, 1506–1519 (2008).
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (Springer, Berlin, 1999).
C. Bazgan, B. Escoffer, V. Th. Paschos, “Completeness in Standard and Differential Approximation Classes: Poly-(D)APX- and (D)PTAS-Completeness,” Theor. Comput. Sci. 339, 272–292 (2005).
M. Bouhtou, A. Grigoriev, A. F. Van Der Kraaij, S. Van Hoesel, F. Spieksma, and M. Uetz, “Pricing Bridges to Cross a River,” Naval Res. Logistics. 54(4), 411–420 (2007).
P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan, “Structure in Approximation Classes,” SIAM J. Comput. 28(5), 1759–1782 (1999).
A. Dasci and G. Laporte, “Location and Pricing Decisions of a Multistore Monopoly in a Spatial Market,” J. Region. Sci. 44, 489–515 (2004).
S. J. Dempe, Foundations of Bilevel Programming (Kluwer Acad. Publ., Dordrecht, 2002).
H. A. Eiselt and V. Marianov, Foundations of Location Analysis (Springer, New York, 2011).
A. Grigoriev, J. van Loon, M. Sviridenko, M. Uetz, and T. Vredeveld, “Optimal Bundle Pricing with Monotonicity Constraint,” Oper. Res. Lett. 36(5), 609–614 (2008).
P. Hanjoul, P. Hansen, D. Peeters, and J.-F. Thisse, “Uncapacitated Plant Location under Alternative Spatial Price Policies,” Market Sci. 36, 41–57 (1990).
D. Serra and C. ReVelle, “Competitive Locations and Pricing on Networks,” Geograph. Anal. 31, 109–129 (1999).
X. Vives, Oligopoly Pricing: Old Ideas and New Tools (MIT Press, Cambridge, A, 1999).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © A.A. Panin, A.V. Plyasunov, 2014, published in Diskretnyi Analiz i Issledovanie Operatsii, 2014, Vol. 21, No. 5, pp. 54–66.
Rights and permissions
About this article
Cite this article
Panin, A.A., Plyasunov, A.V. On complexity of the bilevel location and pricing problems. J. Appl. Ind. Math. 8, 574–581 (2014). https://doi.org/10.1134/S1990478914040152
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1990478914040152