An Efficient Algorithm for Solving Linear Fractional Programming Problems with Flexible Branching Technique
摘要
In this paper, we present an efficient algorithm equipped with a flexible branching rule to address the linear fractional programming (LFP) problem. To pinpoint the global optimal solution of the problem LFP, we initiate by transforming the problem LFP into an equivalent problem through the introduction of parameters. Subsequently, we construct linear relaxation subproblems by relaxing each fraction, thereby establishing the lower bounds for the global minimum of the equivalent problem. Leveraging the branch-and-bound framework, we propose an innovative flexible branching rule and incorporate a compression technique to enhance the performance of the algorithm. Compared with the common branch methods, under certain conditions, the flexible branch can continuously update the lower bound of the optimal value of the equivalent problem after each iteration. Furthermore, we delve into the convergence and complexity of the algorithm, providing a definitive maximum on the number of iterations required. Finally, numerical results on various test problems demonstrate the effectiveness and feasibility of our proposed algorithm.