A refined branch and bound algorithm for solving the sum of linear ratios programming

Hongwei Yue, Hou Li, Peiping Shen and Yaping Deng

Mathematics and Computers in Simulation (MATCOM), 2026, vol. 247, issue C, 210-224

Abstract: A refined branch and bound algorithm is introduced to efficiently solve the sum of linear ratios (SLR) programming. Initially, an equivalent problem of (SLR) is established through a two-stage transformation process, and then this equivalent problem is relaxed into a linear programming problem. Subsequently, under the criterion of minimal integral area, we characterize the relaxation gaps of the two components in the relaxation problem, and determine the corresponding optimal branching points. Based on these obtained points, we develop a refined branch rule. This rule guarantees that the lower bound for the optimal value of the original problem is effectively updated. To further enhance the efficiency of algorithm, a region tightening technique is incorporated to eliminate redundant calculations. Ultimately, the convergence and complexity of the algorithm are analyzed. Numerical experiments indicate that the algorithm has advantages in term of efficiency for the test instances.

Keywords: Global optimization; Sum of linear ratios; Relaxation; Branch and bound; Region tightening (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378475426000935
Full text for ScienceDirect subscribers only

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:eee:matcom:v:247:y:2026:i:c:p:210-224

DOI: 10.1016/j.matcom.2026.03.012

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().