Abstract
Projection of a polyhedron involves the use of a cone whose extreme rays induce the inequalities defining the projection. These inequalities need not be facet defining. We introduce a transformation that produces a cone whose extreme rays induce facets of the projection.
Similar content being viewed by others
References
E. Balas, S. Ceria, and G. Cornuéjols, "A lift-and-project cutting plane algorithm for mixed 0-1 programs," Mathematical Programming, vol. 58, pp. 295-324, 1993.
E. Balas and W.R. Pulleyblank, "The perfectly matchable subgraph polytope of a bipartite graph," Networks, vol. 13, pp. 495-516, 1983.
E. Balas and W.R. Pulleyblank, "The perfectly matchable subgraph polytope of an arbitrary graph," Combinatorica, vol. 9, pp. 321-337, 1989.
M.O. Ball, W.G. Liu, and W.R. Pulleyblank, “Two terminal steiner tree polyhedra," Report No. 87466-OR, Institüt für Ökonometrie und Operations Research Bonn, 1987.
M.X. Goemans, "Polyhedral description of trees and arborescences,” in Integer Programming and Combinatorial Optimization (Proceedings of IPCO 2), E. Balas, G. Cornuéjols, and R. Kannan (Eds.), Carnegie Mellon University, 1992, pp. 1-14.
L. Lovász and A. Schrijver, "Cones of matrices and set-functions and 0-1 optimization," SIAM Journal on Optimization, vol. 1, pp. 166-190, 1991.
G.L. Nemhauser and L. Wolsey, Integer and Combinatorial Optimization, Wiley, 1988.
M. Queyranne and Y. Wang, "Single machine scheduling polyhedra with precedence constraints," Mathematics of Operations Research, vol. 16, pp. 1-20, 1991.
R.L. Rardin and L.A. Wolsey, "Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems," European Journal of Operational Research, vol. 71, pp. 95-109, 1993.
H. Sherali and W. Adams, "A hierarchy of relaxations between the continuous and convenx hull representations for zero-one programming problems," SIAM Journal on Discrete Mathematics, vol. 3, pp. 411-430, 1990.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Balas, E. Projection with a Minimal System of Inequalities. Computational Optimization and Applications 10, 189–193 (1998). https://doi.org/10.1023/A:1018368920203
Issue Date:
DOI: https://doi.org/10.1023/A:1018368920203