On the Chvátal Rank of Certain Inequalities
On the Chvátal Rank of Certain Inequalities
复制标题
论某些不等式的 Chvátal 等级
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
Yaoguang Wang
中科院分区：
文献类型：
--
作者：
M. Hartmann;M. Queyranne;Yaoguang Wang
对多面体P的整船体有效的具有整分量的不等式ax ≤ B的Chvatal秩是得到给定不等式所需的Gomory-Chvatal切割平面的最小轮数。若B是线性规划max{ax：x ∈ P}的最优值z（a）的整数部分，则Chvatal秩至多为1.我们表明，与其他作者所陈述或暗示的相反，后一种陈述的匡威命题，即Chvatal秩至少为2，如果B小于z（a）的整数部分，一般不成立。我们建立简单的条件，这意味着是有效的，并将这些条件应用到几类旅行推销员多面体的方面诱导不等式。
The Chvatal rank of an inequality ax ≤ b with integral components and valid for the integral hull of a polyhedron P, is the minimum number of rounds of Gomory-Chvatal cutting planes needed to obtain the given inequality. The Chvatal rank is at most one if b is the integral part of the optimum value z(a) of the linear program max{ax : x ∈ P}. We show that, contrary to what was stated or implied by other authors, the converse to the latter statement, namely, the Chvatal rank is at least two if b is less than the integral part of z(a), is not true in general. We establish simple conditions for which this implication is valid, and apply these conditions to several classes of facet-inducing inequalities for travelling salesman polytopes.