Mod-2 Cuts Generation Yields the Convex Hull of Bounded Integer Feasible Sets
Mod-2 Cuts Generation Yields the Convex Hull of Bounded Integer Feasible Sets
复制标题
DOI：
10.1137/04061831x
复制
发表时间：
2006-12
期刊：
影响因子：
--
通讯作者：
C. Gentile;P. Ventura;R. Weismantel
中科院分区：
文献类型：
--
作者：
C. Gentile;P. Ventura;R. Weismantel
本文主要研究线性不等式组的所有整数解的凸船体的外部描述。它表明，如果给定的系统包含下，上界的变量，那么凸船体可以通过迭代生成所谓的模-2切割只。这个事实是令人惊讶的，甚至可能是违反直觉的，因为存在许多整数舍入切割不是mod-2，即，可表示为给定约束系统的$\{0，\frac {1}{2}\}$组合。然而，关键是，一般来说，需要比传统整数舍入过程更多轮的mod-2切割生成来产生最终描述。
This paper focuses on the outer description of the convex hull of all integer solutions to a given system of linear inequalities. It is shown that if the given system contains lower and upper bounds for the variables, then the convex hull can be produced by iteratively generating so-called mod-2 cuts only. This fact is surprising and might even be counterintuitive, since many integer rounding cuts exist that are not mod-2, i.e., representable as the $\{0,\frac{1}{2}\}$ combination of the given constraint system. The key, however, is that in general many more rounds of mod-2 cut generation are necessary to produce the final description than in the traditional integer rounding procedure.