A hybrid relaxation method for solving generalized linear fractional programs

Xia Jing; Yuelin Gao; Xiaoli Huang; Xia Jing; Yuelin Gao; Xiaoli Huang

doi:10.3934/jimo.2026022

Journal of Industrial and Management Optimization

2026, Volume 22, Issue 1: 581-611. doi: 10.3934/jimo.2026022

Previous Article Next Article

Research article Special Issues

A hybrid relaxation method for solving generalized linear fractional programs

1.
School of Mathematics and Information Science, North Minzu University, Yinchuan 750021, China
2.
College of Mathematics and Computer Science, Yan'an University, Yan'an 716000, China
3.
School of Mathematics and Statistics, Shaanxi Xueqian Normal University, Xian 710061, China

Received: 05 August 2025 Revised: 13 October 2025 Accepted: 05 November 2025 Published: 16 December 2025
90C26, 90C32

Performing the efficient global optimization algorithm for generalized linear fractional programs (GLFPs) is a very desirable goal in the field of optimization. As the problem's size increases, this goal is becoming increasingly difficult to achieve, although there have been some advances in recent years. In this paper, we present an efficient outcome space branch-and-bound algorithm for globally solving large-scale GLFPs. First, we convert the GLFP into its equivalent problem (EP) by introducing new variables. Second, a hybrid relaxation strategy (a convex envelope and a second-order cone) is used to derive a series of new linear relaxation problems (LRPs) that approximate the EP's optimal value. Meanwhile, a new region reduction method is presented, where the branching operation is performed in an outcome space. A novel branch-and-bound algorithm is then provided to solve GLFPs by computing a lower bound from the LRPs. Subsequently, the algorithm's convergence and worst-case iteration count are also reported. We conclude with numerical experiments illustrating the proposed algorithm's efficacy, especially when solving large-scale GLFPs.
- generalized linear fractional programs,
- hybrid relaxation,
- branch-and-bound,
- computational complexity
Citation: Xia Jing, Yuelin Gao, Xiaoli Huang. A hybrid relaxation method for solving generalized linear fractional programs[J]. Journal of Industrial and Management Optimization, 2026, 22(1): 581-611. doi: 10.3934/jimo.2026022

Related Papers:

Abstract

Performing the efficient global optimization algorithm for generalized linear fractional programs (GLFPs) is a very desirable goal in the field of optimization. As the problem's size increases, this goal is becoming increasingly difficult to achieve, although there have been some advances in recent years. In this paper, we present an efficient outcome space branch-and-bound algorithm for globally solving large-scale GLFPs. First, we convert the GLFP into its equivalent problem (EP) by introducing new variables. Second, a hybrid relaxation strategy (a convex envelope and a second-order cone) is used to derive a series of new linear relaxation problems (LRPs) that approximate the EP's optimal value. Meanwhile, a new region reduction method is presented, where the branching operation is performed in an outcome space. A novel branch-and-bound algorithm is then provided to solve GLFPs by computing a lower bound from the LRPs. Subsequently, the algorithm's convergence and worst-case iteration count are also reported. We conclude with numerical experiments illustrating the proposed algorithm's efficacy, especially when solving large-scale GLFPs.

References

[1]	M. Palmgren, M. Rönnqvist, P. Värbrand, A solution approach for log truck scheduling based on composite pricing and branch and bound, Int. T. Oper. Res., 10 (2003), 433–447. https://doi.org/10.1111/1475-3995.00420 doi: 10.1111/1475-3995.00420
[2]	X. Li, Z. W. He, N. M. Wang, A branch-and-bound algorithm for the proactive resource-constrained project scheduling problem with a robustness maximization objective, Comput. Oper. Res., 166 (2024), 106623. https://doi.org/10.1016/j.cor.2024.106623 doi: 10.1016/j.cor.2024.106623
[3]	M. Barkhagen, S. García, J. Gondzio, J. Kalcsics, J. Kroeske, S. Sabanis, et al., Optimising portfolio diversification and dimensionality, J. Glob. Optim., 85 (2023), 185–234. https://doi.org/10.1007/s10898-022-01202-7 doi: 10.1007/s10898-022-01202-7
[4]	H. Konno, M. Inori, Bond portfolio optimization by bilinear fractional programming, J. Oper. Res. Soc. Jpn., 32 (1989), 143–158. https://doi.org/10.15807/jorsj.32.143 doi: 10.15807/jorsj.32.143
[5]	H. Konno, T. Suzukia, D. Kobayashi, A branch and bound algorithm for solving mean-risk-skewness portfolio models, Optim. Method. Soft., 10 (1998), 297–317. https://doi.org/10.1080/10556789808805716 doi: 10.1080/10556789808805716
[6]	C. D. Maranas, I. P. Androulakis, C. A. Floudas, A. J. Berger, J. M. Mulvey, Solving long-term financial planning problems via global optimization, J. Econ. Dyn. Control, 21 (1997), 1405–1425. https://doi.org/10.1016/S0165-1889(97)00032-8 doi: 10.1016/S0165-1889(97)00032-8
[7]	B. Grimstad, B. Foss, R. Heddle, M. Woodman, Global optimization of multiphase flow networks using spline surrogate models, Comput. Chem. Eng., 84 (2016), 237–254. https://doi.org/10.1016/j.compchemeng.2015.08.022 doi: 10.1016/j.compchemeng.2015.08.022
[8]	F. Pecci, E. Abraham, I. Stoianov, Global optimality bounds for the placement of control valves in water supply networks, Optim. Eng., 20 (2019), 457–495. https://doi.org/10.1007/s11081-018-9412-7 doi: 10.1007/s11081-018-9412-7
[9]	K. Bot, I. Laouali, A. Ruano, M. D. G. Ruano, Home energy management systems with branch-and-bound model-based predictive control techniques, Energies, 14 (2021), 5852. https://doi.org/10.3390/en14185852 doi: 10.3390/en14185852
[10]	S. A. Cetegen, M. D. Stuber, Optimal design of controlled environment agricultural systems under market uncertainty, Comput. Chem. Eng., 149 (2021), 107285. https://doi.org/10.1016/j.compchemeng.2021.107285 doi: 10.1016/j.compchemeng.2021.107285
[11]	N. T. H. Phuong, H. Tuy, A unified monotonic approach to generalized linear fractional programming, J. Glob. Optim., 26 (2003), 229–259. https://doi.org/10.1023/A:1023274721632 doi: 10.1023/A:1023274721632
[12]	H. Konno, Parametric simplex algorithms for solving a special class of nonconvex minimization problems, J. Glob. Optim., 1 (1991), 65–82. https://doi.org/10.1007/BF00120666 doi: 10.1007/BF00120666
[13]	P. P. Shen, B. D. Huang, L. F. Wang, Range division and linearization algorithm for a class of linear ratios optimization problems, J. Comput. Appl. Math., 350 (2019), 324–342. https://doi.org/10.1016/j.cam.2018.10.038 doi: 10.1016/j.cam.2018.10.038
[14]	R. M. Oliveira, P. A. V. Ferreira, An outcome space approach for generalized convex multiplicative programs, J. Glob. Optim., 47 (2010), 107–118. https://doi.org/10.1007/s10898-009-9460-9 doi: 10.1007/s10898-009-9460-9
[15]	H. P. Benson, G. M. Boger, Outcome-space cutting-plane algorithm for linear multiplicative programming, J. Optim. Theory Appl., 104 (2000), 301–322. https://doi.org/10.1023/A:1004657629105 doi: 10.1023/A:1004657629105
[16]	P. Bonami, A. Lodi, J. Schweiger, A. Tramontaniet, Solving quadratic programming by cutting planes, SIAM J. Optim., 29 (2019), 1076–1105. https://doi.org/10.1137/16M107428X doi: 10.1137/16M107428X
[17]	P. P. Shen, D. X. Wu, Y. F. Wang, An efficient spatial branch-and-bound algorithm using an adaptive branching rule for linear multiplicative programming, J. Comput. Appl. Math., 426 (2023), 115100. https://doi.org/10.1016/j.cam.2023.115100 doi: 10.1016/j.cam.2023.115100
[18]	C. F. Wang, Y. P. Deng, P. P. Shen, A novel convex relaxation-strategy-based algorithm for solving linear multiplicative problems, J. Comput. Appl. Math., 407 (2023), 114080. https://doi.org/10.1016/j.cam.2021.114080 doi: 10.1016/j.cam.2021.114080
[19]	E. A. Y. Envelope, Level set algorithm for solving convex multiplicative programming problems, Appl. Math. Comput., 167 (2005), 1412–1417. https://doi.org/10.1016/j.amc.2004.08.028 doi: 10.1016/j.amc.2004.08.028
[20]	S. Y. Liu, Y. F. Zhao, An effcient algorithm for globally solving generalized linear multiplicative programming, J. Comput. Appl. Math., 296 (2016), 840–847. https://doi.org/10.1016/j.cam.2015.11.009 doi: 10.1016/j.cam.2015.11.009
[21]	X. L. Huang, Y. L. Gao, An effcient outer space branch-and-bound algorithm for globally minimizing linear multiplicative problems, AIMS Math., 8 (2023), 26045–26069. https://doi.org/10.3934/math.20231327 doi: 10.3934/math.20231327
[22]	H. W. Jiao, W. J. Wang, J. B. Yin, Y. L. Shang, Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems, RAIRO-Oper. Res., 56 (2022), 1533–1552. https://doi.org/10.1051/ro/2022061 doi: 10.1051/ro/2022061
[23]	H. W. Jiao, W. J. Wang, Y. L. Shang Outer Space branch-reduction-bund algorithm for solving generalizaed affine multiplicative problems, J. Comput. Appl. Math., 419 (2023), 114784. https://doi.org/10.1016/j.cam.2022.114784 doi: 10.1016/j.cam.2022.114784
[24]	Y. L. Gao, C. X. Xu, Y. J. Yang, An outcome-space finite algorithm for solving linear multiplicative programming, Appl. Math. Comput., 179 (2006), 494–505. https://doi.org/10.1016/j.amc.2005.11.111 doi: 10.1016/j.amc.2005.11.111
[25]	B. Zhang, H. Y. Wang, Y. L. Gao, Output-space outer approximation branch-and-bound algorithm for a class of linear multiplicative programs, J. Optim. Theory Appl., 202 (2024), 997–1026. https://doi.org/10.1007/s10957-024-02461-y doi: 10.1007/s10957-024-02461-y
[26]	Y. L. Gao, B. Zhang, Output-space branch-and-bound reduction algorithm for generalized linear fractional-multiplicative programming problem, Chaos Soliton. Fract., 175 (2023), 113924. https://doi.org/10.1016/j.chaos.2023.113924 doi: 10.1016/j.chaos.2023.113924
[27]	R. W. Freund, F. Jarre, Solving the sum-of-ratios problem by an interior-point method, J. Glob. Optim., 19 (2001), 83–102. https://doi.org/10.1023/A:1008316327038 doi: 10.1023/A:1008316327038
[28]	R. Precup, A. Orzan, Dinkelbach type approximation algorithms for nonlinear fractional optimization problems, Numer. Funct. Anal. Optim., 44 (2023), 954–969. https://doi.org/10.1080/01630563.2023.2217893 doi: 10.1080/01630563.2023.2217893
[29]	M. Jaberipour, E. Khorram, Solving the sum-of-ratios problems by a harmony search algorithm, J. Comput. Appl. Math., 234 (2010), 733–742. https://doi.org/10.1016/j.cam.2010.01.013 doi: 10.1016/j.cam.2010.01.013
[30]	B. D. Huang, P. P. Shen, An efficient branch and bound reduction algorithm for globally solving linear fractional programming problems, Chaos Soliton. Fract., 182 (2024), 114757. https://doi.org/10.1016/j.chaos.2024.114757 doi: 10.1016/j.chaos.2024.114757
[31]	Y. J. Wang, Z. A. Liang, A deterministic global optimization algorithm for generalized geometric programming, Math. Comput., 168 (2005), 722–737. https://doi.org/10.1016/j.amc.2005.01.142 doi: 10.1016/j.amc.2005.01.142
[32]	H. W. Jiao, B. B. Li, W. Yang. A criterion-space branch-reduction-bound algorithm for solving generalized multiplicative problems, J. Glob. Optim., 89 (2024), 597–632. https://doi.org/10.1007/s10898-023-01358-w doi: 10.1007/s10898-023-01358-w
[33]	P. P. Shen, X. D. Bai, W. M. Li, A new accelerating method for globally solving a class of nonconvex programming problems, Nonlinear Anal., 71 (2009), 2866–2876. https://doi.org/10.1016/j.na.2009.01.142 doi: 10.1016/j.na.2009.01.142
[34]	H. W. Jiao, Y. L. Shang, Two-level linear relaxation method for generalized linear fractional programming, J. Oper. Res. Soc. China, 11 (2023), 569–594. https://doi.org/10.1007/s40305-021-00375-4 doi: 10.1007/s40305-021-00375-4
[35]	P. P. Shen, C. F. Wang, Global optimization for sum of generalized fractional functions, J. Comput. Appl. Math., 214 (2008), 1–12. https://doi.org/10.1016/j.cam.2007.01.022 doi: 10.1016/j.cam.2007.01.022
[36]	H. W. Jiao, Y. R. Guo, P. P. Shen, Global optimization of generalized linear fractional programming with nonlinear constraints, Appl. Math. Comput., 183 (2006), 717–728. https://doi.org/10.1016/j.amc.2006.05.102 doi: 10.1016/j.amc.2006.05.102
[37]	H. W. Jiao, B. B. Li, Y. L. Shang, An outer space approach to tackle generalized affine fractional program problems, J. Optim. Theory Appl., 201 (2024), 1–35. https://doi.org/10.1007/s10957-023-02368-0 doi: 10.1007/s10957-023-02368-0
[38]	Z. S. Hou, S. Y. Liu, An efficient image space branch-reduction-bound algorithm to globally solve generalized fractional programming problems for large-scale real applications, J. Comput. Appl. Math., 451 (2024), 116070. https://doi.org/10.1016/j.cam.2024.116070 doi: 10.1016/j.cam.2024.116070
[39]	H. W. Jiao, J. Q. Ma, Optimizing generalized linear fractional program using the image space branch-reduction-bound scheme, Optimization, 74 (2024), 1–32. https://doi.org/10.1080/02331934.2023.2253816 doi: 10.1080/02331934.2023.2253816
[40]	Z. S. Hou, S. Y. Liu, A spatial branch-reduction-bound algorithm for solving generalized linear fractional problems globally, Chaos Soliton. Fract., 176 (2023), 114144. https://doi.org/10.1016/j.chaos.2023.114144 doi: 10.1016/j.chaos.2023.114144
[41]	A. Charnes, W. W. Cooper, Programming with linear fractional functionals, Nav. Res. Logist. Q., 9 (1962), 181–186.
[42]	A. Gleixner, L. Eifler, T. Gally, G. Gamrath, P. Gemander, R. L. Gottwald, et al., The SCIP Optimization Suite, version 5.0.1, Zuse Institute Berlin (ZIB), Berlin, Germany, 2017. Available from: https://www.scipopt.org/index.php/download [Accessed 2 July 2025].

jimo-22-01-022-s001.pdf

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)