Abstract
In this paper, a linear bilevel programming problem (LBP) is considered. Local optimality in LBP is studied via two related problems (P) and P(M). Problem (P) is a one-level model obtained by replacing the innermost problem of LBP by its KKT conditions. Problem P(M) is a penalization of the complementarity constraints of (P) with a penalty parameter M. Characterizations of a (strict) local solution of LBP are derived. In particular, the concept of equilibrium point of P(M) is used to characterize the local optima of (P) and LBP.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J.F. BARD (1983) ArticleTitleAn Efficient Point Algorithm for a Linear Two-Stage Optimization Problem Operations Research 31 670–684
W.F. BIALAS M.H. KARWAN (1984) ArticleTitleTwo-Level Linear Programming Management Science 30 1004–1020
J.J. JÚDICE A.M. FAUSTINO (1992) ArticleTitleA Sequential LCP Method for Bilevel Linear Programming Annals of Operations Research 34 89–106
D.J. WHITE G. ANANDALINGAM (1993) ArticleTitleA Penalty Function Approach for Solving Bilevel Linear Programs Journal of Global Optimization. 3 397–419
M. AMOUZEGAR K. MOSHIRVAZIRI (1998) A Penalty Method for Linear Bilevel Programming Problems A. Migdalas P. M. Pardalos P. Värbrand Particle271 (Eds) Multilevel Optimization: Algorithms and Applications Kluwer Academic Publishers Dordrecht, Holland 251–271
M. CAMPÊLO S. SCHEIMBERG (2001) Theoretical and Computational Results for a Linear Bilevel Problem N. Hadjisavvas P. M. Pardalos (Eds) Advances in Convex Analysis and Global Optimization Kluwer Academic Publishers Dordrecht, Holland 269–281
B. HANSENP. JAUMARD G. SAVARD (1992) ArticleTitleNew Branch-and-Bound Rules for Linear Bilevel Programming SIAM Journal on Scientific and Statistical Computing. 13 1194–1217
L.N. VICENTE P.H. CALAMAI (1994) ArticleTitleBilevel and Multilevel Programming A Bibliography Review Journal of Global Optimization 5 291–306
K. SHIMIZU Y. ISHIZUKA J. BARD (1997) Nondifferentiable and Two-Level Mathematical Programming Kluwer Academic Publishers Dordrecht, Holland
MIGDALAS, A., PARDALOS, P. M., and VÄRBRAND, P., Editors, Multilevel Optimization: Algorithms and Applications, Nonconvex Optimization and Its Applications, Kluwer Academic Plublishers, Dordrecht, Holland, Vol. 20, 1998.
S. DEMPE (2002) Foundations of Bilevel Programming, Nonconvex Optimization and Its Applications Kluwer Academic Publishers Dordrecht, Holland
Z. Q. LUO J.S. PANG D. RALPH (1996) Mathematical Programs with Equilibrium Constraints Cambridge University Press Cambridge, UK
P. CALAMAI L. VICENTE (1993) ArticleTitleGenerating Linear and Linear-Quadratic Bilevel Programming Problems SIAM Journal on Scientific and Statistical Computing. 14 770–782
J.F. BARD (1984) ArticleTitleAn Investigation of the Linear Three-Level Programming Problem IEEE Transactions on Systems Man, and Cybernetics. 14 711–717
H. ÖNAL (1993) ArticleTitleA Modified Simplex Approach for Solving Bilevel Linear Programming Problems European Journal of Operational Research. 67 126–135
Q. LUO Z. S. PANG J. D. RALPH Q. WU S. (1996) ArticleTitleExact Penalization and Stationary Conditions for Mathematical Programs with Equilibrium Constraints Mathematical Programming 75 19–76
O.L. MANGASARIAN J.S. PANG (1997) ArticleTitleExact Penalty Functions for Mathematical Programs with Linear Complementary Constraints Optimization. 42 1–8
S. SCHOLTES M. STÖHR (1999) ArticleTitleExact Penalization of Mathematical Programs with Equilibrium Constraints SIAM Journal on Control and Optimization. 37 617–652
M. S. BAZARAA H. D. SHERALY C. M. SHETTY (1993) Nonlinear Programming Theory and Algorithms John Wiley and Sons Singapore, Republic of Singapore
H. BENSON (1989) ArticleTitleOn the Structure and Properties of a Linear Multilevel Programming Problem Journal of Optimization Theory and Applications. 60 353–373
CAMPÊLO, M., Linear Bilevel Programming: A Theoretical and Computational Approach, PhD Thesis, Universidade Federal do Rio de Janeiro, 1999 (in Portuguese).
H. KONNO (1976) ArticleTitleA Cutting Plane Algorithm for Solving Bilinear Programs Mathematical Programming. 11 14–27
R. HORST H. TUY (1990) Global Optimization: Deterministic Approaches Springer Verlag Berlin, Germany
B. AUDETC.HANSENP. JAUMARD G. SAVARD (1999) ArticleTitleA Symmetrical Linear Maxmin Approach to Disjoint Bilinear Programming Mathematical Programming. 85 573–592
Author information
Authors and Affiliations
Additional information
Research partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), Brazil. The authors thank theanonymous referees for careful reading and useful suggestions.
Rights and permissions
About this article
Cite this article
Campêlo, M., Scheimberg, S. A Study of Local Solutions in Linear Bilevel Programming. J Optim Theory Appl 125, 63–84 (2005). https://doi.org/10.1007/s10957-004-1711-9
Issue Date:
DOI: https://doi.org/10.1007/s10957-004-1711-9