On the Convex Hull of the Union of Certain Polyhedra
Abstract
This document considers a finite collection of polyhedra whose defining linear systems differ only in their right hand sides. Jeroslow and Blair specified conditions under which the convex hull of the union of these polyhedra is defined by a system whose left hand side is the common left hand side of the individual systems, and whose right hand side is a convex combination of the individual right hand sides. The author gives a new sufficient condition for this property to hold, which is often easier to recognize. In particular, it is shows that the condition is satisfied for polyhedra whose defining systems involve the node-arc incidence matrices of directed graphs, with certain right hand sides also derived as a special case is the compact linear characterization of the two terminal Steiner tree polytope given in Ball, Liu and Pulleyblank.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1988
- Accession Number
- ADA197982
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University