Abstract
In this paper, a linear bilevel programming problem (LBP) is considered. Local optimality conditions are derived. They are based on the notion of equilibrium point of an exact penalization for LBP. It is described how an equilibrium point can be obtained with the simplex method. It is shown that the information in the simplex tableaux can be used to get necessary and sufficient local optimality conditions for LBP. Based on these conditions, a simplex type algorithm is proposed, which attains a local solution of LBP by moving in equilibrium points. A numerical example illustrates how the algorithm works. Some computational results are reported.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Audet, C., et al. (1999). “A Symetrical Linear Maxmin Approach to Disjoint Bilinear Programming.” Mathematical Programming 85, 573–592.
Amouzegar, M. and K. Moshirvaziri. (1998). “A Penalty Method for Linear Bilevel Programming Problems.” In A. Migdalas, P. Pardalos, and P. Värbrand (eds.), Multilevel Optimization: Algorithms and Applications, Kluwer Acad. Plublishers, Vol. 20, pp. 251–271.
Bard, J.F. (1984). “An Investigation of the Linear Three Level Programming Problem.” IEEE Transactions on Systems, Man and Cybernetics 14(5), 711–717.
Bazaraa, M.S., J.J. Jarvis, and H.D. Sherali. (1990). Linear Programming and Network Flows, 2nd edition, New York, Wiley.
Benson, H. (1989). “On the Structure and Properties of a Linear Multilevel Programming Problem.” J. Optimization Theory and Applications 60, 353–373.
Bialas, W.F. and M.H. Karwan. (1984). “Two-Level Linear Programming.” Manegement Science 30(8), 1004–1020.
Calamai, P. and L. Vicente. (1993). “Generating Linear and Linear-Quadratic Bilevel Programming Problems.” SIAM J. Scientific and Statistical Computing 14, 770–782.
Campêlo, M. (1999). “Programação Linear em Dois Níveis: Uma abordagem Teórica e computacional.” PhD Thesis, Universidade Federal do Rio de Janeiro, Brazil (Portuguese).
Campêlo, M. and S. Scheimberg. (2001). “Theoretical and Computational Results for a Linear Bilevel Problem.” In N. Hadjisavvas and P. Pardalos (eds.), Advances in Convex Analysis and Global Optimization, Kluwer Acad. Publishers. Vol. 54, pp. 269–281.
Campêlo, M. and S. Scheimberg. (2005). “A Study of Local Solutions in Linear Bilevel Programming.” J. Optimization Theory and Applications 125(1), 63–84.
Hansen, P., B. Jaumard, and G. Savard. (1992). “New Branch-and-Bound Rules for Linear Bilevel Programming.” SIAM J. Scientific and Statistical Computing 13(5), 1194–1217.
Júdice, J. and A. Faustino. (1992). “A Sequential LCP method for Bilevel Linear Programming.” Annals of Operations Research 34, 89–106.
Konno, H. (1976). “A Cutting Plane Algorithm for Solving Bilinear Programs.” Mathematical Programming 11, 14–27.
Luo, Z.-Q., et al. (1996). “Exact Penalization and Stationary Conditions of Mathematical Programs with Equilibrium Constraints.” Mathematical Programming 75, 19–76.
Migdalas, A., P. Pardalos, and P. Värbrand, (eds.) (1998). Multilevel Optimization: Algorithms and Applications, Nonconvex Optimization and its Applications, Kluwer Acad. Plublishers, Vol. 20.
Sabóia, C.H., M. Campêlo, and S. Scheimberg. (2004). “A Computational Study of Global Algorithms for Linear Bilevel Programming.” Numerical Algorithms 35, 155–173.
Tuy, H. and S. Ghannadan. (1998). “A New Branch-and-Bound Method for Bilevel Linear Programs.” In A. Migdalas, P. Pardalos, and P. Värbrand (eds.), Multilevel Optimization: Algorithms and Applications, Kluwer Acad. Publishers, Vol. 20, pp. 231–249.
Vicente L. and P. Calamai. (1994). “Bilevel and Multilevel Programming: A Bibliography Review.” J. Global Optimization 5, 291–306.
White, D.J. and G. Anandalingam. (1993). “A Penalty Function Approach for Solving Bi-Level Linear Programs.” J. Global Optimization 3, 397–419.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Campêlo, M., Scheimberg, S. A Simplex Approach for Finding Local Solutions of a Linear Bilevel Program by Equilibrium Points. Ann Oper Res 138, 143–157 (2005). https://doi.org/10.1007/s10479-005-2450-5
Issue Date:
DOI: https://doi.org/10.1007/s10479-005-2450-5