On the convex hull of the union of certain polyhedra

On the convex hull of the union of certain polyhedra

0.00 Avg rating0 Votes
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:
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.