×

Solving generalized polynomial problem by using new affine relaxed technique. (English) Zbl 1499.90277

Summary: This article presents and validates a new branch-and-bound algorithm for effectively solving the generalized polynomial problem (GPP). In this algorithm, a new affine relaxed technique is derived for establishing the relaxed linear programs problem of the GPP. In addition, some box reducing manipulations are employed to improve the speed of branch-and-bound search of the algorithm. Combining the relaxed linear programs problem with the box reducing manipulations, a new branch-and-bound algorithm is constructed. Some numerical examples are solved to verify the potential practical and computing advantages of the algorithm. At last, several engineering design problems are solved to validate the usefulness of the algorithm.

MSC:

90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C26 Nonconvex programming, global optimization
90C32 Fractional programming
65K05 Numerical mathematical programming methods

Software:

BARON
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bao, X.; Khajavirad, A.; Sahinidis, N. V.; Tawarmalani, M., Global optimization of nonconvex problems with multilinear intermediates, Math. Program. Comput., 7, 1, 1-37 (2015) · Zbl 1317.90243
[2] Bao, X.; Sahinidis, N. V.; Tawarmalani, M., Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs, Optim. Methods Softw., 24, 4-5, 485-504 (2009) · Zbl 1179.90252
[3] Costa, J., A branch & cut technique to solve a weighted-sum of linear ratios, Pac. J. Optim., 6, 1, 21-38 (2010) · Zbl 1190.90232
[4] Das, K.; Roy, T. K.; Maiti, M., Multi-item inventory model with under imprecise objective and restrictions: A geometric programming approach, Prod. Plan. Control, 11, 8, 781-788 (2000)
[5] Floudas, C.A. and Visweswaran, V., Quadratic Optimization, in Handbook of Global Optimization, Nonconvex Optimization and its Applications, R. Horst, and P.M. Pardalos, eds., Dordrecht, Kluwer Academic Publishers, 1995, pp. 217-270. · Zbl 0833.90091
[6] Gao, Y.; Wei, F., A new bound-and-reduce approach of nonconvex quadratic programming problems, Appl. Math. Comput., 250, 298-308 (2015) · Zbl 1328.90096
[7] Gao, Y. L.; Xu, C. X.; Yan, Y. L., An outcome-space finite algorithm for solving linear multiplicative programming, Appl. Math. Comput., 179, 2, 494-505 (2006) · Zbl 1103.65065
[8] Jiao, H., A branch and bound algorithm for globally solving a class of nonconvex programming problems, Nonlinear Anal.-Theor., 70, 1113-1123 (2009) · Zbl 1155.90459
[9] Jiao, H.; Liu, S., A practicable branch and bound algorithm for sum of linear ratios problem, Eur. J. Oper. Res., 243, 3, 723-730 (2015) · Zbl 1346.90773
[10] Jiao, H.; Liu, S., An efficient algorithm for quadratic sum-of-ratios fractional programs problem, Numer. Funct. Anal. Opt., 38, 11, 1426-1445 (2017) · Zbl 1387.90243
[11] Jiao, H.; Liu, S.; Lu, N., A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming, Appl. Math. Comput., 250, 973-985 (2015) · Zbl 1328.65137
[12] Jiao, H.; Liu, S.; Zhao, Y., Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints, Appl. Math. Model., 39, 23-24, 7568-7582 (2015) · Zbl 1443.90037
[13] Khajavirad, A.; Michalek, J. J.; Sahinidis, N. V., Relaxations of factorable functions with convex-transformable intermediates, Math. Program., 144, 107-140 (2014) · Zbl 1301.65047
[14] Khajavirad, A.; Sahinidis, N. V., A hybrid LP/NLP paradigm for global optimization relaxations, Math. Program. Comput., 10, 3, 383-421 (2018) · Zbl 1400.90227
[15] Konno, H.; Fukaishi, K., A branch-and-bound algorithm for solving low-rank linear multiplicative and fractional programming problems, J. Glob. Optim., 18, 283-299 (2000) · Zbl 0971.90065
[16] Lin, M.-H.; Tsai, J.-F., Range reduction techniques for improving computational efficiency in global optimization of signomial geometric programming problems, Eur. J. Oper. Res., 216, 17-25 (2012) · Zbl 1242.90177
[17] Maranas, C. D.; Floudas, C. A., Global optimization in generalized geometric programming, Comput. Chem. Engin., 21, 4, 351-369 (1997)
[18] Nguyen, T. H.P.; Tuy, H., A unified monotonic approach to generalized linear fractional programming, J. Glob. Optim., 26, 229-259 (2003) · Zbl 1039.90079
[19] Nohra, C. J.; Sahinidis, N. V., Global optimization of nonconvex problems with convex-transformable intermediates, J. Glob. Optim., 72, 255-276 (2018) · Zbl 1417.90121
[20] Phan-huy-Hao, E., Quadratically constrained quadratic programming: Some applications and a method for solution, Zeitschrift Für Oper. Res., 26, 105-119 (1982) · Zbl 0479.90065
[21] Qin, J.; Xu, X.; Wu, Q.; Cheng, T. C.E., Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem, Comput. Oper. Res., 66, 199-214 (2016) · Zbl 1349.90720
[22] Ryoo, H.-S.; Sahinidis, N. V., A branch-and-reduce approach to global optimization, J. Glob. Optim., 8, 107-138 (1996) · Zbl 0856.90103
[23] Ryoo, H.-S.; Sahinidis, N. V., Analysis of bounds for multilinear functions, J. Glob. Optim., 19, 403-424 (2001) · Zbl 0982.90054
[24] Ryoo, H.-S.; Sahinidis, N. V., Global optimization of multiplicative programs, J. Glob. Optim., 26, 387-418 (2003) · Zbl 1052.90091
[25] Sahinidis, N. V., BARON: A general purpose global optimization software package, J. Global Optim., 8, 201-205 (1996) · Zbl 0856.90104
[26] Schaible, S.; Shi, J., Fractional programming: The sum-of-ratios case, Optim. Meth. Softw., 18, 219-229 (2003) · Zbl 1070.90115
[27] Shen, P., Linearization method of global optimization for generalized geometric programming, Appl. Math. Comput., 162, 353-370 (2005) · Zbl 1071.65089
[28] Shen, P.; Huang, B., Global algorithm for solving linear multiplicative programming problems, Optim. Lett. (2019) · Zbl 1442.90153 · doi:10.1007/s11590-018-1378-z
[29] Shen, P.; Huang, B.; Wang, L., Range division and linearization algorithm for a class of linear ratios optimization problems, J. Comput. Appl. Math., 350, 324-342 (2019) · Zbl 1405.90109
[30] Shen, P.; Jiao, H., Linearization method for a class of multiplicative programming with exponent, Appl. Math. Comput., 183, 1, 328-336 (2006) · Zbl 1110.65051
[31] Shen, P.; Li, X., Branch-reduction-bound algorithm for generalized geometric programming, J. Glob. Optim., 56, 3, 1123-1142 (2013) · Zbl 1300.90032
[32] Shen, P.-P.; Li, X.-A.; Jiao, H.-W., Accelerating method of global optimization for signomial geometric programming, J. Comput. Appl. Math., 214, 66-77 (2008) · Zbl 1140.65048
[33] Shen, P.; Wang, C., Linear decomposition approach for a class of nonconvex programming problems, J. Inequal. Appl., 2017, 472 (2017) · Zbl 1360.90239
[34] Shen, P.; Zhang, K., Global optimization of signomial geometric programming using linear relaxation, Appl. Math. Comput., 150, 99-114 (2004) · Zbl 1053.90112
[35] Shen, P.; Zhu, Z.; Chen, X., A practicable contraction approach for the sum of the generalized polynomial ratios problem, Eur. J. Oper. Res., 278, 1, 36-48 (2019) · Zbl 1430.90528
[36] Sherali, H. D.; Alameddine, A., A new reformulation-linearization technique for bilinear programming problems, J. Glob. Optim., 2, 379-410 (1992) · Zbl 0791.90056
[37] Stancu-Minasian, I. M., Fractional Programming: Theory, Methods and Applications (1997), Kluwer: Kluwer, Dordrecht · Zbl 0899.90155
[38] Stancu-Minasian, I. M., A eighth bibliography of fractional programming, Optim., 66, 3, 439-470 (2017) · Zbl 1365.90249
[39] Sui, Y. K., The expansion of functions under transformation and its application to optimization, Comput. Method Appl. M., 113, 253-262 (1994) · Zbl 0847.73076
[40] Tawarmalani, M.; Sahinidis, N. V., Semidefinite relaxations of fractional programs via novel convexification techniques, J. Glob. Optim., 20, 2, 133-154 (2001) · Zbl 1001.90064
[41] Tawarmalani, M.; Sahinidis, N. V., Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications (2002), Kluwer: Kluwer, Dordrecht · Zbl 1031.90022
[42] Tawarmalani, M.; Sahinidis, N. V., Convex extensions and convex envelopes of l.s.c functions, Math. Program., 93, 247-263 (2002) · Zbl 1065.90062
[43] Tawarmalani, M.; Sahinidis, N. V., A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047
[44] Tsai, J.-F., Global optimization of nonlinear fractional programming problems in engineering design, Eng. Optim., 37, 4, 399-409 (2005)
[45] Wang, C.-F.; Bai, Y.-Q.; Shen, P.-P., A practicable branch-and-bound algorithm for globally solving linear multiplicative programming, Optimization,, 66, 397-405 (2017) · Zbl 1364.90276
[46] Wang, Y. J.; Liang, Z. A., A deterministic global optimization algorithm for generalized geometric programming, Appl. Math. Comput., 168, 722-737 (2005) · Zbl 1105.65335
[47] Wang, C. F.; Liu, S. Y., A new linearization method for generalized linear multiplicative programming, Comput. Oper. Res., 38, 1008-1013 (2011) · Zbl 1208.90162
[48] Wang, C.-F.; Liu, S.-Y.; Shen, P.-P., Global minimization of a generalized linear multiplicative programming, Appl. Math. Model., 36, 6, 2446-2451 (2012) · Zbl 1246.90162
[49] Wang, Y.; Punnen, A. P., The boolean quadratic programming problem with generalized upper bound constraints, Comput. Oper. Res., 77, 1-10 (2017) · Zbl 1391.90418
[50] Weintraub, A.; Vera, J., A cutting plane approach for chance-constrained linear programs, Oper. Res., 39, 776-785 (1991) · Zbl 0744.90065
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.