An Output-Space Based Branch-and-Bound Algorithm for Sum-of-Linear-Ratios Problem

Bo Zhang () and Yuelin Gao
Additional contact information
Bo Zhang: School of Mathematics and Statistics, Ningxia University, Yinchuan 750021, P. R. China
Yuelin Gao: Ningxia Province Cooperative Innovation, Center of Scientific Computing and Intelligent Information Processing, North Minzu University, Yinchuan 750021, P. R. China3Ningxia Province Key Laboratory of Intelligent Information and Data Processing, North Minzu University, Yinchuan 750021, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 02, 1-23

Abstract: Founded on the idea of subdividing the (p − 1)-dimensional output space, a branch-and-bound algorithm for solving the sum-of-linear-ratios(SLR) problem is proposed. First, a two-stage equivalent transformation method is adopted to obtain an equivalent problem(EP) for the problem SLR. Second, by dealing with all nonlinear constraints and bilinear terms in EP and its sub-problems, a corresponding convex relaxation subproblem is obtained. Third, all redundant constraints in each convex relaxation subproblem are eliminated, which leads to a linear programming problem with smaller scale and fewer constraints. Finally, the theoretical convergence and computational complexity of the algorithm are demonstrated, and a series of numerical experiments illustrate the effectiveness and feasibility of the proposed algorithm.

Keywords: Global optimization; sum-of-linear-ratios problem; branch and bound; output-space (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595922500105
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:40:y:2023:i:02:n:s0217595922500105

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595922500105

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().