Decorous Lower Bounds for Minimum Linear Arrangement
Decorous Lower Bounds for Minimum Linear Arrangement
复制标题
DOI：
10.1287/ijoc.1100.0390
复制
发表时间：
2011-12-01
影响因子：
2.1
通讯作者：
Salazar-Gonzalez, Juan-Jose
中科院分区：
文献类型：
--
作者：
Caprara, Alberto;Letchford, Adam N.;Salazar-Gonzalez, Juan-Jose
最小线性排列是20世纪60年代的经典基本组合优化问题，在实践中极具挑战性。特别是，对于大多数基准实例，甚至最优解值的数量级是未知的，正如对包含表格的问题的调查所证明的那样，其中最知名的解值通常比最知名的下限值多一位。在本文中，我们提出了一种基于线性规划的方法来计算最优的下限。这使我们能够第一次证明，对于大多数基准测试实例来说，最知名的解决方案确实离最优不远。
Minimum linear arrangement is a classical basic combinatorial optimization problem from the 1960s that turns out to be extremely challenging in practice. In particular, for most of its benchmark instances, even the order of magnitude of the optimal solution value is unknown, as testified by the surveys on the problem that contain tables in which the best-known solution value often has one more digit than the best-known lower bound value. In this paper, we propose a linear programming-based approach to compute lower bounds on the optimum. This allows us, for the first time, to show that the best-known solutions are indeed not far from optimal for most of the benchmark instances.