Tighter Representations for Set Partitioning Problems
Tighter Representations for Set Partitioning Problems
复制标题
集合划分问题的更紧密表示
DOI：
10.1016/0166-218x(95)00060-5
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Youngho Lee
中科院分区：
文献类型：
--
作者：
H. Sherali;Youngho Lee
在本文中，我们考虑集合划分多胞体，并首先应用 Sherali 和 Adams（1990，1994）的重构线性化技术，通过利用该多胞体的结构来生成专门的松弛层次。然后，我们展示了该多面体的几个已知的有效不等式类，以及相关的紧缩和组合规则，在该层次结构的第一级和第二级松弛中自动捕获。因此，这些放松为广泛的此类不平等现象提供了一个统一的框架。此外，从生成更严格的松弛的角度来看，可以仅实现这些松弛的部分形式，该松弛删除了集合划分问题的基础线性规划解决方案，基于对于该问题的最优分数的变量。
In this paper, we consider the set partitioning polytope and we begin by applying the reformulation-linearization technique of Sherali and Adams (1990, 1994) to generate a specialized hierarchy of relaxations by exploiting the structure of this polytope. We then show that several known classes of valid inequalities for this polytope, as well as related tightening and composition rules, are automatically captured within the first- and second-level relaxations of this hierarchy. Hence, these relaxations provide a unifying framework for a broad class of such inequalities. Furthermore, it is possible to implement only partial forms of these relaxations from the viewpoint of generating tighter relaxations that delete the underlying linear programming solution to the set partitioning problem, based on variables that are fractional at an optimum to this problem.