论文标题
最大的未解决的QAP实例TAI256C可以转换为具有单个基数约束的256维简单BQOP
The Largest Unsolved QAP Instance Tai256c Can Be Converted into A 256-dimensional Simple BQOP with A Single Cardinality Constraint
论文作者
论文摘要
tai256c是qaplib中最大的未解决二次分配问题（qAP）实例； 1.48 \％的差距保持在未知最佳值的最佳可行目标值和下限之间。本文表明，该实例可以转换为具有单个基数约束的256维二进制二次优化问题（BQOP），该二进制变量要求将二进制变量的总和为92。转换后的BQOP比原始的QAP TAI256C简单得多，并且还继承了某些对称属性。但是，解决仍然非常困难。我们提出了有效改进下限的有效分支和界限方法。还提供了具有1.36 \％间隙的新下限。
Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB; a 1.48\% gap remains between the best known feasible objective value and lower bound of the unknown optimal value. This paper shows that the instance can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. The converted BQOP is much simpler than the original QAP tai256c and it also inherits some of the symmetry properties. However, it is still very difficult to solve. We present an efficient branch and bound method for improving the lower bound effectively. A new lower bound with 1.36\% gap is also provided.
