A revision of the trapezoidal branch-and-bound algorithm for linear sum-of-ratios problems

In this paper, we point out a theoretical flaw in Kuno [(2002)Journal of Global Optimization 22, 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.