首页    期刊浏览 2024年11月08日 星期五
登录注册

文章基本信息

  • 标题:On unions and dominants of polytopes
  • 本地全文:下载
  • 作者:Egon BALAS ; Alexander BOCKMAYR ; Nicolai PISARUK
  • 期刊名称: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.
  • 关键词:Unions of Polytopes, Cardinality Constraints, Separation, Convex Hulls, Dominant, Matroids, Polymatroids .
国家哲学社会科学文献中心版权所有