Optimizing over the first Chvátal closure
Optimizing over the first Chvátal closure
复制标题
对第一个 Chvátal 闭包进行优化
DOI：
10.1007/s10107-006-0054-8
复制
发表时间：
2005
影响因子：
2.7
通讯作者：
Andrea Lodi
中科院分区：
文献类型：
--
作者：
M. Fischetti;Andrea Lodi
在实践中，精确优化泛型ILP的第一个Chvátal闭包有多难？完整性差距的哪一部分可以通过这种方式闭合，例如，在MIPLIB库中解决一些难题当一个特定的组合问题被解决时，第一闭包优化可以作为一个研究（离线）工具来猜测一些相关的不等式类的结构吗？在本文中，我们给出了答案，上述问题的基础上，广泛的计算分析。我们的方法是通过MIP模型对秩为1的Chvátal-Gomory分离问题进行建模，该问题被认为是NP难的，然后通过通用MIP求解器来解决MIP模型。据我们所知，这种方法从来没有实现和计算评估以前的作者，虽然它提供了一个非常有用的分离工具，一般的ILP问题。我们报告了MIPLIB 3.0和2003中的一组ILP问题的第一个Chvátal闭包的最优值。我们还报告，第一次，从MIPLIB 2003年，即nsrand-ipx，通过使用我们的切割分离程序来预处理原始ILP模型获得一个非常困难的情况下的最优解。最后，我们描述了一类新的ATSP方面发现我们的分离过程的帮助下。
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? Can the first-closure optimization 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 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 and 2003. We also report, for the first time, the optimal solution of a very hard instance from MIPLIB 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.