Abstract
Many decision-making situations involve multiple planners with different, and sometimes conflicting, objective functions. One type of model that has been suggested to represent such situations is the linear multilevel programming problem. However, it appears that theoretical and algorithmic results for linear multilevel programming have been limited, to date, to the bounded case or the case of when only two levels exist. In this paper, we investigate the structure and properties of a linear multilevel programming problem that may be unbounded. We study the geometry of the problem and its feasible region. We also give necessary and sufficient conditions for the problem to be unbounded, and we show how the problem is related to a certain parametric concave minimization problem. The algorithmic implications of the results are also discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bracken, J., Falk, J. E., andMiercort, F. A.,A Strategic Weapons Exchange Allocation Model, Operations Research, Vol. 25, pp. 968–976, 1977.
Cassidy, R. G., Kirby, M. J. L., andRaike, W. M.,Efficient Distribution of Resources through Three Levels of Government, Management Science, Vol. 17, pp. B462-B473, 1971.
Fortuny-Amat, J., andMcCarl, B.,A Representation and Economic Interpretation of a Two-Level Programming Problem, Journal of the Operational Research Society, Vol. 32, pp. 783–792, 1981.
Candler, W., andTownsley, R.,A Linear Two-Level Programming Problem, Computers and Operations Research, Vol. 9, pp. 59–76, 1982.
Bard, J. F.,Geometric and Algorithmic Developments for a Hierarchical Planning Problem, European Journal of Operational Research, Vol. 19, pp. 372–383, 1985.
Jeroslow, R. G.,The Polynomial Hierarchy and a Simple Model for Competitive Analysis, Mathematical Programming, Vol. 32, pp. 146–164, 1985.
Bard, J. F., andFalk, J. E.,An Explicit Solution to the Multi-Level Programming Problem, Computers and Operations Research, Vol. 9, pp. 77–100, 1982.
Bialas, W. F., andKarwan, M. H.,On Two-Level Optimization, IEEE Transactions on Automatic Control, Vol. AC-27, pp. 211–214, 1982.
Bard, J. F.,Optimality Conditions for the Bilevel Programming Problem, Naval Research Logistics Quarterly, Vol. 31, pp. 13–26, 1984.
Bard, J. F.,An Efficient Algorithm for a Linear Two-Stage Optimization Problem, Operations Research, Vol. 31, pp. 670–684, 1983.
Bialas, W. F., andKarwan, M. H.,Two-Level Linear Programming, Management Science, Vol. 30, pp. 1004–1020, 1984.
Bard, J. F.,An Algorithm for Solving the General Bilevel Programming Problem, Mathematics of Operations Research, Vol. 8, pp. 260–272, 1983.
Spivey, W. A., andThrall, R. M.,Linear Optimization, Holt, Rinehart, and Winston, New York, New York, 1970.
Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.
Hogan, W. W.,Point-to-Set Maps in Mathematical Programming, SIAM Review, Vol. 15, pp. 591–603, 1973.
Naccache, P. H.,Connectedness of the Set of Nondominated Outcomes in Multicriteria Optimization, Journal of Optimization Theory and Applications, Vol. 25, pp. 459–467, 1978.
Martos, B.,The Direct Power of Adjacent Vertex Programming Methods, Management Science, Vol. 12, pp. 241–252, 1965.
Epelman, M. S.,On a Property of Polyhedral Sets, Mathematical Programming, Vol. 16, pp. 371–373, 1979.
Benson, H. P.,A Finite Algorithm for Concave Minimization over a Polyhedron, Naval Research Logistics Quarterly, Vol. 32, pp. 165–177, 1985.
Cabot, A. V.,Variations on a Cutting Plane Method for Solving Concave Minimization Problems with Linear Constraints, Naval Research Logistics Quarterly, Vol. 21, pp. 265–274, 1974.
Carrillo, M. J.,A Relaxation Algorithm for the Minimization of a Quasiconcave Function on a Convex Polyhedron, Mathematical Programming, Vol. 13, pp. 69–80, 1977.
Falk, J. E., andHoffman, K. R.,A Successive Underestimation Method for Concave Minimization Problems, Mathematics of Operations Research, Vol. 1, pp. 251–259, 1976.
Majthay, A., andWhinston, A.,Quasiconcave Minimization Subject to Linear Constraints, Discrete Mathematics, Vol. 9, pp. 35–59, 1974.
Thoai, N. V., andTuy, H.,Convergent Algorithms for Minimizing a Concave Function, Mathematics of Operations Research, Vol. 5, pp. 556–566, 1980.
Zwart, P. B.,Global Maximization of a Convex Function with Linear Inequality Constraints, Operations Research, Vol. 22, pp. 602–609, 1974.
Author information
Authors and Affiliations
Additional information
Communicated by P. L. Yu
This research was supported by National Science Foundation Grant No. ECS-85-15231.
Rights and permissions
About this article
Cite this article
Benson, H.P. On the structure and properties of a linear multilevel programming problem. J Optim Theory Appl 60, 353–373 (1989). https://doi.org/10.1007/BF00940342
Issue Date:
DOI: https://doi.org/10.1007/BF00940342