On The Convergence Of The Affine Hull Of The Chvatal-Gomory Closures

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.


Published in:
Siam Journal On Discrete Mathematics, 27, 3, 1492-1502
Year:
2013
Publisher:
Philadelphia, Siam Publications
ISSN:
0895-4801
Keywords:
Laboratories:




 Record created 2013-12-09, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)