Abstract
The purpose of this paper is to elaborate on the difficulties accompanying the development of efficient algorithms for solving the bilevel programming problem (BLPP). We begin with a pair of examples showing that, even under the best of circumstances, solutions may not exist. This is followed by a proof that the BLPP is NP-hard.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bard, J. F.,Optimality Conditions for the Bilevel Programming Problem, Naval Research Logistics Quarterly, Vol. 31, pp. 13–26, 1984.
Hasen, P., Jaumard, B., andSavard, G.,A Variable Elimination Algorithm for Bilevel Programming, RUTCOR Research Report RRR-17-89, Rutgers University, New Brunswick, New Jersey, 1989.
Jeroslow, R. G.,The Polynomial Hierarchy and a Simple Model for Competitive Analysis, Mathematical Programming, Vol. 32, pp. 146–164, 1985.
Hogan, W. W.,Point-to-Set Maps in Mathematical Programming, SIAM Review, Vol. 15, pp. 591–603, 1973.
Garey, M. R. andJohnson, D. S.,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York, New York, 1979.
Ben-Ayed, O., andBlair, C. E.,Computational Difficulties of Bilevel Programming, Working Paper WP-1432, College of Commerce and Business Administration, University of Illinois, Urbana, Illinois, 1988.
Author information
Authors and Affiliations
Additional information
Communicated by M. Avriel
This work was partially supported by a grant from the Advanced Research Program of the Texas Higher Education Coordinating Board.
Rights and permissions
About this article
Cite this article
Bard, J.F. Some properties of the bilevel programming problem. J Optim Theory Appl 68, 371–378 (1991). https://doi.org/10.1007/BF00941574
Issue Date:
DOI: https://doi.org/10.1007/BF00941574