Abstract
The paper presents an approach to bi-level programming using a duality gap—penalty function format. A new exact penalty function exists for obtaining a global optimal solution for the linear case, and an algorithm is given for doing this, making use of some new theoretical properties. For each penalty parameter value, the central optimisation problem is one of maximising a convex function over a polytope, for which a modification of an algorithm of Tuy (1964) is used. Some numerical results are given. The approach has other features which assist the actual decisionmaking process, which make use of the natural roles of duality gaps and penalty parameters. The approach also allows a natural generalization to nonlinear problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aiyoshi, E. and K. Shimizu (1984), A Solution Method for the Static Constrained Stackelberg Problem via Penalty Method,IEEE Transactions on Automatic Control 29(12), 1111–1114.
Anandalingam, G. (1988), A Mathematical Programming Model of Multi-Level Hierarchical Systems,Journal of the Operational Research Society 39(6), 1021–1033.
Anandalingam, G., R. Mathieu, L. Pittard, and N. Sinha (1989), Artificial Intelligence Based Approaches for Hierarchical Optimization, in R. Shardaet al. (eds.),Impact of Recent Computer Advances on Operations Research, North-Holland, NY.
Anandalingam, G. and White, D. J. (1990), A Solution Method for the Linear Static Stackelberg Problem Using Penalty Functions,IEEE Transactions on Automatic Control 35(10), 1170–1173.
Bard, J. F. (1983), An Efficient Point Algorithm for a Linear Two-Stage Optimization Problem,Operations Research, July–August, 670–684.
Bard, J. F. (1984), An Investigation of the Linear Three Level Programming Problem,IEEE Transactions on Systems, Man, and Cybernetics 14(5), 711–717.
Bard, J. F. and Moore, J. J. (1990), A Branch-and-Bound Algorithm for the Bilevel Linear Programming Problem,SIAM Journal of Scientific and Statistical Computing 11(2), 281–292.
Bazaraa, M. and C. M. Shetty (1979),Nonlinear Programming: Theory and Algorithms, Wiley, New York.
Bertsekas, D. P. and E. Gafni (1982), Projection Method for Variational Inequalities and Application to a Traffic Assignment Problem,Mathematical Programming Study 17, 139–159.
Bialas, W. F. and M. H. Karwan (1982), On Two-Level Linear Programming,Management Science 30(8), 1004–1020.
Candler, W. and R. Townsley (1982), A Linear Two-Level Programming Problem,Computers and Operations Research 9(1), 59–76.
Dantzig, G. B. and P. Wolfe (1960), Decomposition Principle for Linear Programs,Operations Research 8(1), 101–111.
Fortuny-Amat, J. and B. McCarl (1981), A Representative and Economic Interpretation of a Two Level Programming Problem,Journal of the Operational Research Society 32, 783–792.
Geoffrion, A. M. (1971), Duality in Nonlinear Programming: A Simplified Application Oriented Development,SIAM Review 13(1), 1–37.
Glover, F. and D. Klingman (1973), Concave Programming Applied to a Special Class of 0–1 Integer Programs,Operations Research 21, 135–140.
Harker, P. T. (1986), Alternative Models of Spatial Competition,Operations Research 34, 410–425.
Horst, R. and H. Tuy (1990),Global Optimization: Deterministic Approaches, Springer Verlag, Berlin.
Judice, J. and A. M. Faustino (1988), The Solution of the Linear Bi-Level Programming Problem Using the Linear Complementarity Problem,Investigacao Operacional 8, 77–95.
Marcotte, P. (1983), Network Optimization with Continuous Control Parameters,Transportation Science 17(2), 181–197.
Rockafeller, R. T. (1970),Convex Analysis, Princeton University Press, Princeton, NJ.
Shimizu, K. and E. Aiyoshi (1981), A New Computational Method for Stackelberg and Mini-Max Problems by the Use of a Penalty Method,IEEE Transactions on Automatic Control 26(2), 460–466.
Stackelberg, H. von (1982),The Theory of the Market Economy, Oxford University Press, Oxford.
Tobin, R. L. and T. L. Friesz (1986), Spatial Competition Facility Location Models: Definition, Formulation and Solution Approach,Annals of Operations Research 6, 49–74.
Tuy, H. (1964), Concave Programming under Linear Constraints,Soviet Mathematics 5, 1437–1440.
Wendell, R. E. and A. P. Hurter Jr. (1976), Minimization of a Non-Separable Objective Function Subject to Disjoint Constraints,Operations Research 24(4), 643–656.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
White, D.J., Anandalingam, G. A penalty function approach for solving bi-level linear programs. J Glob Optim 3, 397–419 (1993). https://doi.org/10.1007/BF01096412
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01096412