Article ID: | iaor1988697 |
Country: | Netherlands |
Volume: | 7 |
Issue: | 6 |
Start Page Number: | 279 |
End Page Number: | 283 |
Publication Date: | Dec 1988 |
Journal: | Operations Research Letters |
Authors: | Balas Egon |
We consider a finite collection of polyhedra whose defining linear systems differ only in their right hand aides. 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. We give a new sufficient condition for this property to hold, which is often easier to recognize. In particular, we show that the condition is satisfied for polyhedra whose defining systems involve the node-arc incidence matrices of directed graphs, with certain right hand sides. We also derive as a special case the compact linear characterization of the two terminal Steiner tree polytope given by Ball, Liu and Pulleyblank.