A new global optimization algorithm for mixed-integer quadratically constrained quadratic fractional programming problem. (English) Zbl 07924436
Summary: The mixed-integer quadratically constrained quadratic fractional programming (MIQCQFP) problem often appears in various fields such as engineering practice, management science and network communication. However, most of the solutions to such problems are often designed for their unique circumstances. This paper puts forward a new global optimization algorithm for solving the problem MIQCQFP. We first convert the MIQCQFP into an equivalent generalized bilinear fractional programming (EIGBFP) problem with integer variables. Secondly, we linearly underestimate and linearly overestimate the quadratic functions in the numerator and the denominator respectively, and then give a linear fractional relaxation technique for EIGBFP on the basis of non-negative numerator. After that, combining rectangular adjustment-segmentation technique and midpoint-sampling strategy with the branch-and-bound procedure, an efficient algorithm for solving MIQCQFP globally is proposed. Finally, a series of test problems are given to illustrate the effectiveness, feasibility and other performance of this algorithm.
MSC:
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
global optimization; branch and bound; quadratic fractional programming; mixed integer programmingSoftware:
SCIPReferences:
| [1] | A. Beck and M. Teboulle, A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program., 118:1 (2009), 13-35. · Zbl 1176.90451 |
| [2] | A. Beck and M. Teboulle, On minimizing quadratically constrained ratio of two quadratic func-tions, J. Convex Anal., 17:1 (2010), 789-804. · Zbl 1213.90239 |
| [3] | I. Bomze and P. Amaral, Copositivity-based approximations for mixed-integer fractional quadratic optimization, Pac. J. Optim., 11:2 (2014), 225-238. · Zbl 1321.90135 |
| [4] | I. Bomze, M. Locatelli, and F. Tardella, New and old bounds for standard quadratic optimization: Dominance, equivalence and incomparability, Math. Program., 115:1 (2008), 31-64. · Zbl 1171.90007 |
| [5] | I. Bomze and M. Overton, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Math. Program., 151:2 (2015), 459-476. · Zbl 1328.90095 |
| [6] | A. Charnes and W. Cooper, Programming with linear fractional functionals, Nav. Res. Logist., 10:1 (1963), 273-274. |
| [7] | A. Del Pia, On approximation algorithms for concave mixed-integer quadratic programming, Math. Program., 172:1-2 (2018), 3-16. · Zbl 1406.90080 |
| [8] | W. Dinkelbach, On non-linear fractional programming, Manage. Sci., 13:7 (1967), 492-498. · Zbl 0152.18402 |
| [9] | S. Fallahi and M. Salahi, On the indefinite quadratic fractional optimization with two quadratic constraints, J. Optim. Theory Appl., 162:1 (2014), 249-256. · Zbl 1298.90114 |
| [10] | L. Galli and A.N. Letchford, A binarisation heuristic for non-convex quadratic programming with box constraints, Oper. Res. Lett., 46:5 (2018), 529-533. · Zbl 1476.90255 |
| [11] | Y. Gao and F. Wei, A new bound-and-reduce approach of nonconvex quadratic programming problems, Appl. Math. Comput., 250 (2015), 298-308. · Zbl 1328.90096 |
| [12] | A. Gleixner et al., The SCIP Optimization Suite 5.0, https://www.scipopt.org/. |
| [13] | F. Glover, Improved linear integer programming formulations of nonlinear integer problems, Man-age. Sci., 22:4 (1975), 455-460. · Zbl 0318.90044 |
| [14] | N. Gould and P. Toint, Numerical methods for large-scale non-convex quadratic programming, in: Trends in Industrial and Applied Mathematics, Springer, (2002), 149-179. |
| [15] | T. Ibaraki, H. Ishii, J. Iwase, T. Hasegawa, and H. Mine, Algorithms for quadratic fractional programming problems, J. Oper. Res. Soc. Japan, 19:2 (1976), 174-191. · Zbl 0349.90073 |
| [16] | E. Jain, K. Dahiya, and V. Verma, Integer quadratic fractional programming problems with bounded variables, Eur. J. Oper. Res., 269:1-2 (2018), 269-295. · Zbl 1411.90333 |
| [17] | V. Jeyakumar and G. Li, Trust-region problems with linear inequality constraints: Exact SDP relaxation, global optimality and robust optimization, Math. Program., 147:1-2 (2014), 171-206. · Zbl 1297.90105 |
| [18] | H. Jiao and S. Liu, A new linearization technique for minimax linear fractional programming, Int. J. Comput. Math., 91:7-8 (2014), 1730-1743. · Zbl 1302.90210 |
| [19] | H. Jiao and S. Liu, A practicable branch and bound algorithm for sum of linear ratios problem, Eur. J. Oper. Res., 243:3 (2015), 723-730. · Zbl 1346.90773 |
| [20] | A. Khurana and S. Arora, An algorithm for solving quadratic fractional program with linear homogeneous constraints, Croat. Oper. Res. Rev., 39:4 (2011), 391-404. · Zbl 1236.90088 |
| [21] | S. Kim and M. Kojima, Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations, Comput. Optim. Appl., 26:2 (2003), 143-154. · Zbl 1043.90060 |
| [22] | S. Liu and L. Ge, An outcome space algorithm for minimizing a class of linear ratio optimization problems, Comput. Appl. Math., 40 (2021), 225. · Zbl 1476.90321 |
| [23] | X. Liu, Y.L. Gao, B. Zhang, and F.P. Tian, A new global optimization algorithm for a class of linear fractional programming, Mathematics, 7:9 (2019), 867. |
| [24] | A. Lo and A. Mackinlay, Maximizing predictability in the stock and bond markets, Macroecon. Dyn., 1:1 (1995), 102-134. · Zbl 0915.90025 |
| [25] | V.-B. Nguyen, R.-L. Sheu, and Y. Xia, An SDP approach for quadratic fractional problems with a two-sided quadratic constraint, Optim. Methods Softw., 31:4 (2016), 701-719. · Zbl 1385.90027 |
| [26] | J. Ohlson, The asymptotic validity of quadratic utility as the trading interval approaches zero, in: Stochastic Optimization Models in Finance, 1:1 (1975), 221-234. |
| [27] | B. Ozkok, An iterative algorithm to solve a linear fractional programming problem, Comput. Ind. Eng., 140 (2020), 106234. |
| [28] | P. Pandian and M. Jayalakshmi, On solving linear fractional programming problems, Math. Models Methods Appl. Sci., 7:6 (2013), 90-100. |
| [29] | P. Pardalos and G. Schnitger, Checking local optimality in constrained quadratic programming is NP-hard, Oper. Res. Lett., 7:1 (1988), 33-35. · Zbl 0644.90067 |
| [30] | N. Phuong and H. Tuy, A unified monotonic approach to generalized linear fractional program-ming, J. Glob. Optim., 26:3 (2003), 229-259. · Zbl 1039.90079 |
| [31] | N. Sahinidis, Baron user manual v.21.1.13, http://minlp.com. |
| [32] | M. Salahi and S. Fallahi, Parametric approach for solving quadratic fractional optimization with a linear and a quadratic constraint, Comput. Appl. Math., 35:2 (2016), 439-446. · Zbl 1370.90270 |
| [33] | V. Seerengasamy and K. Jeyaraman, A new approach for easy computation by using θ-matrix for solving integer linear fractional programming problems, Int. J. Comput. Appl., 69:7 (2013), 26-30. |
| [34] | P. Shen and B. Huang, Global algorithm for solving linear multiplicative programming problems, Optim. Lett., 14:3 (2020), 693-710. · Zbl 1442.90153 |
| [35] | P. Shen, B. Huang, and L. Wang, Range division and linearization algorithm for a class of linear ratios optimization problems, J. Comput. Appl. Math., 350 (2019), 324-342. · Zbl 1405.90109 |
| [36] | P. Shen, K. Wang, and T. Lu, Outer space branch and bound algorithm for solving linear multi-plicative programming problems, J. Glob. Optim., 78:3 (2020), 453-482. · Zbl 1465.90102 |
| [37] | M. Sivri, I. Albayrak, and G. Temelcan, A novel approach for solving quadratic fractional pro-gramming problems, Croat. Oper. Res. Rev., 9:2 (2018), 199-209. · Zbl 1457.90160 |
| [38] | N. Suleimann and M. Nawkhass, Solving quadratic fractional programming problem, Int. J. Appl. Math. Res., 2:2 (2013), 303-309. |
| [39] | K. Swarup, Some aspects of linear fractional programming, Aust. N. Z. J. Stat., 7:3 (2008), 90-104. · Zbl 0158.19002 |
| [40] | S. Tantawy, Using feasible direction linear programming problems, Aust. J. Basic Appl. Sci., 1:2 (2007), 109-114. |
| [41] | C. Tofallis, Fractional programming: Theory, methods and applications, J. Oper. Res. Soc., 49:8 (1998), 895. |
| [42] | W. Xia, J. Vera, and L. Zuluaga, Globally solving nonconvex quadratic programs via linear integer programming techniques, INFORMS J. Comput., 32:1 (2020), 40-56. · Zbl 07284452 |
| [43] | R. Yamamoto and H. Konno, An efficient algorithm for solving convexconvex quadratic fractional programs, J. Optim. Theory Appl., 133:2 (2007), 241-255. · Zbl 1151.90560 |
| [44] | D. Yue, G.G. Gosalbez, and F. You, Global optimization of large-scale mixedinteger linear frac-tional programming problems: A reformulation-linearization method and process scheduling ap-plications, AIChE J., 59:11 (2013), 4255-4272. |
| [45] | A. Zhang and S. Hayashi, Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints, Numer. Algebra, Control. Optim., 1:1 (2011), 83-98. · Zbl 1219.90169 |
| [46] | Y. Zhao and S. Liu, Global optimization algorithm for mixed integer quadratically constrained quadratic program, J. Comput. Appl. Math., 319 (2017), 159-169. · Zbl 1366.90143 |
| [47] | Y. Zhao, S. Liu, and H. Jiao, A new branch and bound algorithm for minimax ratios problems, Open Math., 15:1 (2017), 840-851. · Zbl 1368.90134 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
