Branch-Relaxation-Bound Algorithm for Minimizing a Class of Sum of Affine Ratios Programming Problems

被引：0

作者：

Huang, Xiaoli ^{[1
]}

Ma, Xiaohua ^{[2
]}

Gao, Yuelin ^{[1
,2
]}

Liu, Xia ^{[2
]}

机构：

[1] Ningxia Univ, Sch Math & Stat, Yinchuan 750021, Ningxia, Peoples R China

[2] North Minzu Univ, Ningxia Collaborat Innovat Ctr Sci Comp & Intellig, Yinchuan 750021, Ningxia, Peoples R China

来源：

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH | 2025年

基金：

中国国家自然科学基金;

关键词：

Global optimization; branch and bound; sum of affine ratios; output space; affine relaxation; LINEAR FRACTIONAL FUNCTIONS; GLOBAL OPTIMIZATION ALGORITHM; APPROXIMATION;

D O I：

10.1142/S0217595925500113

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

This paper introduces a branch-relaxation-bound algorithm (BRBA) designed to minimize a class of sum of affine ratios programming (SARP) problems. By leveraging the structural characteristics of SARP, we present a novel relaxation technique that facilitates the construction of a sequence of affine relaxation problems. To optimize computational efficiency, the branching operation is conducted in the output space whose dimension is equal to the number of denominators. By integrating the branch-and-bound framework with affine relaxation problems, a branch-relaxation-bound algorithm is developed. Subsequently, we demonstrate the convergence of the algorithm and discuss its computational complexity. Finally, numerical experiments confirm the feasibility and effectiveness of the proposed algorithm.

引用

页数：33

共 49 条

[41]

Stancu-Minasian IoanM., 1997, Fractional programming, volume 409 of Mathematics and its Applications, V409

[42] A Deterministic Method for Solving the Sum of Linear Ratios Problem [J].

Wang, Zhenping ;

Zhang, Yonghong .

MATHEMATICAL PROBLEMS IN ENGINEERING, 2020, 2020

[43] Minimizing the sum of linear fractional functions over the cone of positive semidefinite matrices: Approximation and applications [J].

Xia, Yong ;

Wang, Longfei ;

Wang, Shu .

OPERATIONS RESEARCH LETTERS, 2018, 46 (01) :76-80

[44] An equilibrium efficiency frontier data envelopment analysis approach for evaluating decision-making units with fixed-sum outputs [J].

Yang, Min ;

Li, Yongjun ;

Chen, Ya ;

Liang, Liang .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 239 (02) :479-489

[45] Global Optimization of Large-Scale Mixed-Integer Linear Fractional Programming Problems: A Reformulation-Linearization Method and Process Scheduling Applications [J].

Yue, Dajun ;

Guillen-Gosalbez, Gonzalo ;

You, Fengqi .

AICHE JOURNAL, 2013, 59 (11) :4255-4272

[46] An Output-Space Based Branch-and-Bound Algorithm for Sum-of-Linear-Ratios Problem [J].

Zhang, Bo ;

Gao, Yuelin .

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2023, 40 (02)

[47] A new deterministic global computing algorithm for solving a kind of linear fractional programming [J].

Zhang, Bo ;

Gao, YueLin ;

Liu, Xia ;

Huang, XiaoLi .

OPTIMIZATION, 2023, 72 (06) :1485-1513

[48]

Zhang YH, 2020, ENG LET, V28, P352

[49] A reduced space branch and bound algorithm for a class of sum of ratios problems [J].

Zhao, Yingfeng ;

Zhao, Ting .

OPEN MATHEMATICS, 2018, 16 :539-552

← 1 2 3 4 5 →