ON THE CONVERGENCE OF THE AFFINE HULL OF THE CHVATAL-GOMORY CLOSURES
ON THE CONVERGENCE OF THE AFFINE HULL OF THE CHVATAL-GOMORY CLOSURES
复制标题
DOI：
10.1137/120898371
复制
发表时间：
2013-01-01
影响因子：
0.8
通讯作者：
Faenza, Yuri
中科院分区：
文献类型：
--
作者：
Averkov, Gennadiy;Conforti, Michele;Faenza, Yuri
鉴于R-N的整体多面体P子集和一个与P相同的整数点的R-N的Ronational Polyhedron Q子集，我们研究必须在Q上执行多少个chvatal-Gomory闭合算子的迭代，才能获得载体中包含的polyhedron我们的船体表明，如果p在其相对内部包含一个整数点，那么这种迭代可以仅取决于n的函数来界定。另一方面，我们证明，如果p不是全维且不包含其相对内部的整数点，则在迭代次数上没有有限的绑定。
Given an integral polyhedron P subset of R-n and a rational polyhedron Q subset of R-n containing the same integer points as P, we investigate how many iterations of the Chvatal-Gomory closure operator have to be performed on Q to obtain a polyhedron contained in the affine hull of P. We show that if P contains an integer point in its relative interior, then such a number of iterations can be bounded by a function depending only on n. On the other hand, we prove that if P is not full-dimensional and does not contain any integer point in its relative interior, then no finite bound on the number of iterations exists.