A linear relaxation algorithm for solving the sum-of-linear-ratios problem with lower dimension

被引：18

作者：

Carlsson, John Gunnar ^{[1
]}

Shi, Jianming ^{[2
]}

机构：

[1] Univ Minnesota, Minneapolis, MN 55455 USA

[2] Tokyo Univ Sci, Tokyo 162, Japan

来源：

OPERATIONS RESEARCH LETTERS | 2013年 / 41卷 / 04期

关键词：

Sum of ratios; Branch and bound; Global optimization; Linear relaxation; EFFICIENT ALGORITHMS; FRACTIONAL FUNCTIONS; BOUND ALGORITHM; AREA;

D O I：

10.1016/j.orl.2013.04.005

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we present an algorithm for solving the sum-of-linear-ratios problem based on a linear relaxation of the objective function. Though there already exist linear relaxation algorithms for solving this problem, they all work on a space whose dimension increases with the number of ratios. When the number of ratios becomes large, these algorithms are unable to solve the problem efficiently. Our numerical experiments indicate that the proposed algorithm in this paper is superior to these existing algorithms when the number of ratios is large. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：381 / 389

页数：9

共 50 条

[21] A branch-and-bound algorithm to globally solve the sum of several linear ratios [J].

Wang, YJ ;

Shen, PP ;

Liang, Z .

APPLIED MATHEMATICS AND COMPUTATION, 2005, 168 (01) :89-101

[22] Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints [J].

Jiao, Hong-Wei ;

Liu, San-Yang ;

Zhao, Ying-Feng .

APPLIED MATHEMATICAL MODELLING, 2015, 39 (23-24) :7568-7582

[23] A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming [J].

Jiao, Hongwei ;

Liu, Sanyang ;

Lu, Nan .

APPLIED MATHEMATICS AND COMPUTATION, 2015, 250 :973-985

[24] Global optimization algorithm for sum of generalized polynomial ratios problem [J].

Jiao, Hongwei ;

Wang, Zhankui ;

Chen, Yongqiang .

APPLIED MATHEMATICAL MODELLING, 2013, 37 (1-2) :187-197

[25] A Global Optimization Algorithm for Solving Generalized Linear Fractional Programming [J].

Zhang, Yonghong ;

Li, Zhaolong ;

Liu, Lixia .

ENGINEERING LETTERS, 2020, 28 (02) :352-358

[26] BRANCH-REDUCTION-BOUND ALGORITHM FOR LINEAR SUM-OF-RATIOS FRACTIONAL PROGRAMS [J].

Shen, Pei-Ping ;

Li, Wei-Min ;

Liang, Yan-Chao .

PACIFIC JOURNAL OF OPTIMIZATION, 2015, 11 (01) :79-99

[27] Effective outcome space branch-and-bound algorithm for solving the sum of affine ratios problem [J].

Shi, Yan ;

Zheng, Qunzhen ;

Yin, Jingben .

AIMS MATHEMATICS, 2024, 9 (09) :23837-23858

[28] A branch-and-bound algorithm for maximizing the sum of several linear ratios [J].

Kuno, T .

JOURNAL OF GLOBAL OPTIMIZATION, 2002, 22 (1-4) :155-174

[29] A global optimization algorithm using linear relaxation [J].

Qu Shaojian ;

Yin Hongyou ;

Zhang Kecun .

APPLIED MATHEMATICS AND COMPUTATION, 2006, 178 (02) :510-518

[30] A global optimization algorithm for solving linear programming problem [J].

Cavalcante, JRR ;

de Souza, FMC .

MANAGEMENT AND CONTROL OF PRODUCTION AND LOGISTICS, VOL 1 AND 2, 1998, :513-515

← 1 2 3 4 5 →