A branch-and-bound algorithm for the linear ordering problem with cumulative costs
A branch-and-bound algorithm for the linear ordering problem with cumulative costs
复制标题
具有累积成本的线性排序问题的分支定界算法
DOI：
10.1016/j.ejor.2007.02.044
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
G. Righini
中科院分区：
文献类型：
--
作者：
G. Righini
具有累积费用的线性排序问题是一个NP-Hard组合优化问题，它来源于UMTS移动通信系统中的一个应用。本文给出了一个多项式可计算的下界，当嵌入到分支定界算法中时，该下界特别有效。可以进一步利用相同的思想来对搜索树的每个节点上的子节点进行排序，以便更早地找到最优解。对所得到的分支定界算法进行适当的截断可以得到快速的构造性启发式算法。
The linear ordering problem with cumulative costs is an NP-hard combinatorial optimization problem arising from an application in UMTS mobile-phone communication systems. This paper presents a polynomially computable lower bound that is particularly effective when embedded in a branch-and-bound algorithm. The same idea can be further exploited to sort the children nodes at each node of the search tree, in order to find the optimal solution earlier. A suitable truncation of the resulting branch-and-bound algorithm results in a fast constructive heuristic.