Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube*
Bounds on the Chvátal Rank of
Polytopes in the 0/1-Cube*
复制标题
Chvátal 等级的界限
DOI：
10.1007/s00493-003-0020-5
复制
发表时间：
2003
期刊：
影响因子：
1.1
通讯作者：
Andreas S. Schulz
中科院分区：
文献类型：
--
作者：
F. Eisenbrand;Andreas S. Schulz
Gomory 和 Chvátal 的剖切平面程序证明
递归地验证整数线性不等式的有效性
给定多面体的外壳。多面体的 Chvátal 阶
是获得所有有效不等式所需的轮数。
众所周知，Chvátal 等级可以任意大，
即使多面体是有界的，如果它是二维的，并且
如果它的整数壳是 0/1 多面体。我们证明了多面体的 Chvátal 秩
许多组合优化问题的常见松弛
相当小；事实上，我们证明了每个的排名
n 维 0/1 立方体中包含的多胞体最多为
n2
(1+log n)。此外，我们还
证明 0/1 立方体中任意多胞形的秩
整数包由常数不等式定义
系数是 O(n)。最后，我们提供了包含在
Chvátal 等级至少为 (1 + ε) 的 0/1 立方体
n，对于某些 ε > 0。
Gomory’s and Chvátal’s cutting-plane procedure proves
recursively the validity of linear inequalities for the integer
hull of a given polyhedron. The Chvátal rank of the polyhedron
is the number of rounds needed to obtain all valid inequalities.
It is well known that the Chvátal rank can be arbitrarily large,
even if the polyhedron is bounded, if it is 2-dimensional, and
if its integer hull is a 0/1-polytope.We show that the Chvátal rank of polyhedra featured in
common relaxations of many combinatorial optimization problems
is rather small; in fact, we prove that the rank of every
polytope contained in the n-dimensional 0/1-cube is at most
n2
(1+log n). Moreover, we also
demonstrate that the rank of any polytope in the 0/1-cube whose
integer hull is defined by inequalities with constant
coefficients is O(n).Finally, we provide a family of polytopes contained in the
0/1-cube whose Chvátal rank is at least (1 + ε)
n, for some ε > 0.