A Revision of the Trapezoidal Branch-and-Bound Algorithm for Linear Sum-of-Ratios Problems
A Revision of the Trapezoidal Branch-and-Bound Algorithm for Linear Sum-of-Ratios Problems
复制标题
DOI：
10.1007/s10898-004-1952-z
复制
发表时间：
2005-10
影响因子：
1.8
通讯作者：
Takahito Kuno
中科院分区：
文献类型：
--
作者：
Takahito Kuno
本文指出了Kuno [（2002）Journal of Global Optimization 22，155-174]在处理线性比率和问题时的一个理论缺陷，并证明了所提出的分支定界算法尽管存在该缺陷，但仍能正确工作。我们还注意到一个单一的比率和高估的边界操作中使用的关系，并制定了一个程序，收紧上界的最佳值。该过程是不昂贵的，但修改后的算法，将其纳入显着提高效率。这是证实了原始和修订后的算法之间的数值比较。
In this paper, we point out a theoretical flaw in Kuno [(2002)Journal of Global Optimization22, 155–174] which deals with the linear sum-of-ratios problem, and show that the proposed branch-and-bound algorithm works correctly despite the flaw. We also note a relationship between a single ratio and the overestimator used in the bounding operation, and develop a procedure for tightening the upper bound on the optimal value. The procedure is not expensive, but the revised algorithms incorporating it improve significantly in efficiency. This is confirmed by numerical comparisons between the original and revised algorithms.