Box-inequalities for quadratic assignment polytopes
Box-inequalities for quadratic assignment polytopes
复制标题
二次赋值多胞形的盒不等式
作者：
M. Jünger;V. Kaibel
摘要：近年来，基于线性规划的下界已多次被考虑用于一般问题和对称二次分配问题。实践证明，它们的质量非常好。对相应整数线性规划公式（非对称和对称二次赋值多胞形）基础的多胞形的研究在过去十年中已经开始[34,31,21,22]。它们带来了关于这些多胞体的基本知识，涉及诸如它们的尺寸、仿射外壳和琐碎面等问题。然而，尚未发现可用于切割平面程序的大类（定义面的）不等式。我们在本文中提出了第一个此类不等式，即盒不等式，它在一些众所周知的割多胞形超度量不等式中有着有趣的起源。基于这些不等式的割平面算法的计算实验表明，它们对于解决二次分配问题以达到最优或计算严格下界的目标非常有用。事实证明，新的不等式中最有效的不等式确实是非对称和对称二次分配多胞体的面定义。
Abstract.Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment problem several times in the recent years. Their quality has turned out to be quite good in practice. Investigations of the polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic assignment polytope) have been started during the last decade [34, 31, 21, 22]. They have lead to basic knowledge on these polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining) inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as for the symmetric quadratic assignment polytope.