On unions and dominants of polytopes
Egon Balas,
Alexander Bockmayr,
Nicolai Pisaruk and
Laurence Wolsey
No 2002008, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)
Abstract:
A well-known result on unions of polyhedra in the same space gives an extended formulation 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.
Keywords: unions of polytopes; cardinality constraints; separation; convex hulls; dominant; matroids; polymatroids. (search for similar items in EconPapers)
Date: 2002-02
References: Add references at CitEc
Citations:
Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2002.html (text/html)
Related works:
Working Paper: On unions and dominants of polytopes (2004)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2002008
Access Statistics for this paper
More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().