An outcome space algorithm for minimizing a class of linear ratio optimization problems

被引:8
|
作者
Liu, Sanyang [1 ]
Ge, Li [1 ]
机构
[1] Xidian Univ, Sch Math & Stat, Xian 710071, Peoples R China
来源
COMPUTATIONAL & APPLIED MATHEMATICS | 2021年 / 40卷 / 06期
基金
中国国家自然科学基金;
关键词
Global optimization; Linear ratio optimization problem; Branch-and-bound; Affine relaxation programming problem; GLOBAL OPTIMIZATION; FRACTIONAL FUNCTIONS; BOUND ALGORITHM; SUM;
D O I
10.1007/s40314-021-01614-3
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
This paper presents an outcome space branch-and-bound algorithm for minimizing a class of linear ratio optimization problems (LROPs), requiring just nonnull denominators in the given domain. The solution methodology uses an affine relaxation of a bilinear approximation model, which is equivalent to the original problem. By combining the relaxation model with the branch-and-bound framework, an outcome space branch-and-bound algorithm is devised for solving LROPs. The algorithm can reduce the computational complexity, as branching is performed in the outcome space with a size equal to the number of fractions, rather than the variable dimension space. Finally, the numerical results indicate the computational feasibility and good performance of the algorithm.
引用
收藏
页数:17
相关论文
共 50 条
  • [21] A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems
    Shetiya, Suraj
    Asudeh, Abolfazl
    Ahmed, Sadia
    Das, Gautam
    PROCEEDINGS OF THE VLDB ENDOWMENT, 2019, 13 (03): : 239 - 251
  • [22] An asynchronous multithreaded algorithm for a class of linear programming problems
    Thulasiraman, P
    Khokhar, AA
    PARALLEL AND DISTRIBUTED COMPUTING SYSTEMS, 2002, : 392 - 397
  • [24] AN ALGORITHM FOR A RESTRICTED CLASS OF LINEAR-PROGRAMMING PROBLEMS
    MITTEN, LG
    OPERATIONS RESEARCH, 1957, 5 (04) : 593 - 593
  • [25] An Outcome-Space-Based Branch-and-Bound Algorithm for a Class of Sum-of-Fractions Problems
    Zhang, Bo
    Gao, YueLin
    Liu, Xia
    Huang, XiaoLi
    JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2022, 192 (03) : 830 - 855
  • [26] An Outcome-Space-Based Branch-and-Bound Algorithm for a Class of Sum-of-Fractions Problems
    Bo Zhang
    YueLin Gao
    Xia Liu
    XiaoLi Huang
    Journal of Optimization Theory and Applications, 2022, 192 : 830 - 855
  • [27] A linear programming based algorithm to solve a class of optimization problems with a multi-linear objective function and affine constraints
    Charkhgard, Hadi
    Savelsbergh, Martin
    Talebian, Masoud
    COMPUTERS & OPERATIONS RESEARCH, 2018, 89 : 17 - 30
  • [28] Global Optimization Algorithm for Solving a Class of Multiplicative Problems
    Yin, Jingben
    Jiao, Hongwei
    Gang, Peiyong
    PROCEEDINGS OF FIRST INTERNATIONAL CONFERENCE OF MODELLING AND SIMULATION, VOL II: MATHEMATICAL MODELLING, 2008, : 414 - 418
  • [29] An Algorithm for the Global Optimization of a Class of Continuous Minimax Problems
    P. Parpas
    B. Rustem
    Journal of Optimization Theory and Applications, 2009, 141 : 461 - 473
  • [30] An Algorithm for a Class of Functional Inequality Constrained Optimization Problems
    Wu Xiang
    Zhang Kanjian
    Sun Changyin
    Lei Bangjun
    2013 32ND CHINESE CONTROL CONFERENCE (CCC), 2013, : 2411 - 2414