Optimizing over the first Chvàtal closure

Abstract

How difficult is, in practice, to optimize exactly over the first Chvàtal closure of a generic ILP? Which fraction of the integrality gap can be closed this way, e.g., for some hard problems in the MIPLIB library? Does it pay to insist on rank-1 Chvàtal-Gomory inequalities until no such inequality is violated, or one should better follow the usual strategy of generating (mixed-integer) Gomory cuts of any rank from the optimal tableau rows? How effective is this general-purpose approach for solving matching problems, where the first Chvàtal closure coincides with the integer hull? Can this approach be useful as a research (off-line) tool to guess the structure of some relevant classes of inequalities, when a specific combinatorial problem is addressed? In this paper we give, for the first time, concrete answers to the above questions, based on an extensive computational analysis. Our approach is to model the rank-1 Chvàtal-Gomory separation problem, which is known to be NP-hard, through a MIP model, which is then solved through a general-purpose MIP solver. As far as we know, this approach was never implemented and evaluated computationally by previous authors, though it gives a very useful separation tool for general ILP problems. We report the optimal value over the first Chvàtal closure for a set of ILP problems from MIPLIB 3.0. We also report, for the first time, the optimal solution of a very hard instance from MIPIB 2003, namely nsrand-ipx, obtained by using our cut separation procedure to preprocess the original ILP model. Finally, we describe a new class of ATSP facets found with the help of our separation procedure. © Springer-Verlag Berlin Heidelberg 2005.