Skip to Main content Skip to Navigation
Journal articles

On unions and dominants of polytopes

Abstract : A well-known result on unions of polyhedra in the same space gives an extended formulation in a higher-dimensional space whose projection is the convex hull of the union. Here in contrast we study the unions of polytopes in different spaces, giving a complete description of the convex hull without additional variables. When the underlying polytopes are monotone, the facets are described explicitly, generalizing results of Hong and Hooker on cardinality rules, and an efficient separation algorithm is proposed. These results are based on an explicit representation of the dominant of a polytope, and an algorithm for the separation problem for the dominant. For non-monotone polytopes, both the dominant and the union are characterized. We also give results on the unions of polymatroids both on disjoint ground sets and on the same ground set generalizing results of Conforti and Laurent.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00100114
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 10:14:15 AM
Last modification on : Friday, February 26, 2021 - 3:28:04 PM

Identifiers

  • HAL Id : inria-00100114, version 1

Collections

Citation

Egon Balas, Alexander Bockmayr, Nicolai Pisaruk, Laurence Wolsey. On unions and dominants of polytopes. Mathematical Programming, Springer Verlag, 2004, 99 (2), pp.223-239. ⟨inria-00100114⟩

Share

Metrics

Record views

133