On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2}
On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2}
复制标题
关于多面体的设置：II。
作者：
E. Balas;S. Ng
在早期的一篇论文(数学规划43()57-69)中，我们刻画了由系数等于0、1或2的不等式定义的覆盖多面体的刻划。在本文中，我们将这种刻画与刻面提升理论联系起来。特别地，我们引入了一类只有三个非零系数的低维多面体及其相关的不等式，它们的提升得到了上面这类中的所有有效的不等式，提升系数由闭合形式的表达式给出。
In an earlier paper (Mathematical Programming 43 (1989) 57–69) we characterized the class of facets of the set covering polytope defined by inequalities with coefficients equal to 0, 1 or 2. In this paper we connect that characterization to the theory of facet lifting. In particular, we introduce a family of lower dimensional polytopes and associated inequalities having only three nonzero coefficients, whose lifting yields all the valid inequalities in the above class, with the lifting coefficients given by closed form expressions.