期刊名称:CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度:2002
卷号:2002
出版社:Center for Operations Research and Econometrics (UCL), Louvain
摘要:A well-known result on unions of polyhedra in the same space gives an ex-
tended 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 character-
ized. 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.