An adaptive branch-and-bound reduction algorithm for minimizing sum of linear ratios programs
摘要
This paper presents an adaptive branch-and-bound reduction algorithm to globally minimize the sum of linear ratios programs (P), originating from practical issues such as multi-stage shipping problem, computer vision, and others. To find the global optimum of problem (P), a linear relaxation (LR) is derived to yield a lower bound on the optimal value of equivalent problem (P2) of problem (P). In order to further tighten the linear relaxation (LR), we then construct an enhanced linear relaxation (ELR) by adding cuts derived from the solution information of (LR). Moreover, we present an adaptive branching scheme (ABS) that overcomes the drawback of the usual bisection scheme that the optimal solution of the relaxation problem on the selected partitioned rectangle may not be cut off. As a result, ABS leads to a continuous improvement in the lower bound of the optimum of problem (P2). Additionally, the region reduction method is introduced to eliminate regions that do not contain the optimal solution of (P2). By iteratively refining the initial rectangle with the proposed ABS and solving the relaxation problems, the constructed algorithm converges to the global optimum of problem (P). Also, we estimate the maximum number of iterations required for the presented algorithm to achieve an