A reduced space branch and bound algorithm for a class of sum of ratios problems : Open Mathematics

摘要

Sum of ratios problem occurs frequently in various areas of engineering practice and managementscience, but most solution methods for this kind of problem are often designed for determining local solutions . In this paper, we develop a reduced space branch and bound algorithm for globally solving sum of convex-concave ratios problem. By introducing some auxiliary variables, the initial problem is converted into an equivalent problem where the objective function is linear. Then the convex relaxation problem of the equivalent problem is established by relaxing auxiliary variables only in the outcome space. By integrating some acceleration and reduction techniques into branch and bound scheme, the presented global optimization algorithm is developed for solving these kind of problems. Convergence and optimality of the algorithm are presented and numerical examples taken from some recent literature and MINLPLib are carried out to validate the performance of the proposed algorithm.