Abstract
A system of linear inequality and equality constraints determines a convex polyhedral set of feasible solutionsS. We consider the relation of all individual constraints toS, paying special attention to redundancy and implicit equalities. The main theorem derived here states that the total number of constraints together determiningS is minimal if and only if the system contains no redundant constraints and/or implicit equalities. It is shown that the existing theory on the representation of convex polyhedral sets is a special case of the theory developed here.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Telgen, J.,Redundancy and Linear Programs, Erasmus University, Rotterdam, Holland, PhD Thesis, 1979.
Dantzig, G. B.,Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1963.
Farkas, J.,Über die Theorie der Einfachen Ungleichungen, Journal für Reine und Angewandte Mathematik, Vol. 124, pp. 1–27, 1902.
Motzkin, T. S.,Beiträge zur Theorie der Linearen Ungleichungen, Basel University, PhD Thesis, 1936.
Kuhn, H. W., andTucker, A. W., Editors,Linear Inequalities and Related Systems, Princeton University Press, Princeton, New Jersey, 1956.
Tschernikow, S. M.,Lineare Ungleichungen, VEB Deutscher Verlag der Wissenschaften, Berlin, Germany, 1966 (translated by H. Weinert).
Boot, J. C. G.,On Trivial and Binding Constraints in Programming Problems, Management Science, Vol. 8, pp. 419–441, 1962.
Charnes, A., Cooper, W. W., andThompson, G. L.,Some Properties of Redundant Constraints and Extraneous Variables in Direct and Dual Linear Programming Problems, Operations Research, Vol. 10, pp. 711–723, 1962.
Thompson, G. L., Tonge, F. M., andZionts, S.,Techniques for Removing Nonbinding Constraints and Extraneous Variables from Linear Programming Problems, Management Science, Vol. 12, pp. 588–608, 1966.
Robinson, S. M.,Stability Theory for Systems of Inequalities, SIAM Journal of Numerical Analysis, Vol. 12, pp. 754–769, 1975.
Shefi, A.,Reduction of Linear Inequality Constraints and Determination of All Feasible Extreme Points, Stanford University, PhD Thesis, 1969.
Luenberger, D. G.,Introduction to Linear and Nonlinear Programming, Addison-Wesley, Reading, Massachusetts, 1973.
Eckhardt, U.,Semidefinite Lineare Komplementärprobleme, RWTH Aachen, Habilitationsschrift, 1977.
Eckhardt, U.,Representation of Convex Sets, Proceedings of the International Symposium on Extremal Methods and Systems Analysis, Austin, Texas, 1979.
Llewellyn, R. W.,Linear Programming, Holt, Rinehart, and Winston, New York, NY, 1964.
Zionts, S.,Size Reduction Techniques of Linear Programming and Their Application, Carnegie Institute of Technology, PhD Thesis, 1965.
Eckhardt, U.,Redundante Ungleichungen bei Linearen Ungleichungssysteme, Unternehmensforschung, Vol. 12, pp. 279–286, 1971.
Mattheis, T. H.,An Algorithm for Determining Irrelevant Constraints and All Vertices in Systems of Linear Inequalities, Operations Research, Vol. 21, pp. 247–260, 1973.
Gal, T.,Zur Identifikation Redundanter Nebenbedingungen in Linearen Programmen, Zeitschrift für Operations Research, Vol. 19, pp. 19–28, 1975.
Gal, T.,Redundancy in Systems of Linear Inequalities Revisited, Fernuniversität Hagen, Working Paper No. 19, 1978.
Boneh, A., andGolan, A.,Constraints Redundancy and Feasible Region Boundedness by Random Feasible Point Generator, Technion, Haîfa, Israel, Technical Report, 1979.
Zimmerman, H. J., andGal, T.,Redundanz und Ihre Bedeutung für Betriebliche Optimierungsentscheidungen, Zeitschrift für Betriebswirtschaft, Vol. 45, pp. 221–236, 1975.
Spronk, J., andTelgen, J.,A Note on Multiple Objective Programming and Redundancy, Erasmus University, Rotterdam, Holland, Center for Research in Business Economics, Report No. 7906, 1979.
Telgen, J.,Overbodige en Niet-Bindende Restricties in Lineare Programmerings Problemen, Bedrijfskunde, Vol. 51, pp. 168–173, 1979.
Karwan, M. H., Telgen, J., andZionts, S.,Redundancy in Mathematical Programming, Springer Verlag, New York, New York, 1982.
Eckhardt, U.,Theorems on the Dimension of Convex Sets, Linear Algebra and Its Aplications, Vol. 12, pp. 63–76, 1975.
Additional information
Communicated by O. L. Mangasarian
The author is indebted to Dr. A. C. F. Vorst (Erasmus University, Rotterdam, Holland) for stimulating discussions and comments, which led to considerable improvements in many proofs. Most of the material in this paper originally appeared in the author's dissertation (Ref. 1). The present form was prepared with partial support from a NATO Science Fellowship for the Netherlands Organization for the Advancement of Pure Research (ZWO) and a CORE Research Fellowship.
Rights and permissions
About this article
Cite this article
Telgen, J. Minimal representation of convex polyhedral sets. J Optim Theory Appl 38, 1–24 (1982). https://doi.org/10.1007/BF00934319
Issue Date:
DOI: https://doi.org/10.1007/BF00934319