Abstract
Consider a convex polyhedral set represented by a system of linear inequalities. A prime representation of the polyhedron is one that contains no redundant constraints. We present a sharp upper bound on the difference between the cardinalities of any two primes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Karwan, M. H., Lofti, V., Telgen, J., andZionts, S., Editors,Redundancy in Mathematical Programming: A State of the Art Survey, Springer-Verlag, Berlin, Germany, 1983.
Caron, R. J., McDonald, J. F., andPonic, C. M.,A Degenerate Extreme Point Strategy for the Classification of Linear Constraints as Redundant or Necessary, Journal of Optimization Theory and Applications, Vol. 62, No. 2, 1989 (to appear).
Boneh, A.,Identification of Redundancy by a Set-Covering Equivalence, Operational Research '84, Edited by J. P. Brans, Elsevier, Amsterdam, The Netherlands, pp. 407–422, 1984.
Telgen, J.,Minimal Representation of Convex Polyhedral Sets, Journal of Optimization Theory and Applications, Vol. 38, pp. 1–24, 1982.
Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.
Author information
Authors and Affiliations
Additional information
Communicated by D. F. Shanno
This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant Nos. A8807, A4625, and A7742.
Rights and permissions
About this article
Cite this article
Boneh, A., Caron, R.J., Lemire, F.W. et al. Note on prime representations of convex polyhedral sets. J Optim Theory Appl 61, 137–142 (1989). https://doi.org/10.1007/BF00940849
Issue Date:
DOI: https://doi.org/10.1007/BF00940849