An efficient outer space branch-and-bound algorithm for globally minimizing linear multiplicative problems

Xiaoli Huang; Yuelin Gao; Xiaoli Huang; Yuelin Gao

doi:10.3934/math.20231327

AIMS Mathematics

2023, Volume 8, Issue 11: 26045-26069. doi: 10.3934/math.20231327

Previous Article Next Article

Research article

An efficient outer space branch-and-bound algorithm for globally minimizing linear multiplicative problems

Xiaoli Huang ^1,3,
Yuelin Gao ^{2,3
,
,}

1.
School of Mathematics and Statistics, Ningxia University, Yinchuan 750021, China
2.
Ningxia province cooperative innovation center of scientific computing and intelligent information processing, North Minzu University, Yinchuan 750021, China
3.
Nixngxia mathematics basic discipline research center, Ningxia University, Yinchuan 750021, China

Received: 29 June 2023 Revised: 25 August 2023 Accepted: 30 August 2023 Published: 08 September 2023
MSC : 90C26, 90C57

We propose an efficient outer space branch-and-bound algorithm for minimizing linear multiplicative problems (LMP). First, by introducing auxiliary variables, LMP is transformed into an equivalent problem (ELMP), where the number of auxiliary variables is equal to the number of linear functions. Subsequently, based on the properties of exponential and logarithmic functions, further equivalent transformation of ELMP is performed. Next, a novel linear relaxation technique is used to obtain the linear relaxation problem, which provides a reliable lower bound for the global optimal value of LMP. Once more, branching operation takes place in the outer space of the linear function while embedding compression technique to remove infeasible regions to the maximum extent possible, which significantly reduces the computational cost. Therefore, an outer space branch-and-bound algorithm is proposed. In addition, we conduct convergence analysis and complexity proof for the algorithm. Finally, the computational performance of the algorithm is demonstrated based on the experimental results obtained by testing a series of problems.
- global optimization,
- linear multiplicative problem,
- linear relaxation,
- branch and bound
Citation: Xiaoli Huang, Yuelin Gao. An efficient outer space branch-and-bound algorithm for globally minimizing linear multiplicative problems[J]. AIMS Mathematics, 2023, 8(11): 26045-26069. doi: 10.3934/math.20231327

Related Papers:

Abstract

We propose an efficient outer space branch-and-bound algorithm for minimizing linear multiplicative problems (LMP). First, by introducing auxiliary variables, LMP is transformed into an equivalent problem (ELMP), where the number of auxiliary variables is equal to the number of linear functions. Subsequently, based on the properties of exponential and logarithmic functions, further equivalent transformation of ELMP is performed. Next, a novel linear relaxation technique is used to obtain the linear relaxation problem, which provides a reliable lower bound for the global optimal value of LMP. Once more, branching operation takes place in the outer space of the linear function while embedding compression technique to remove infeasible regions to the maximum extent possible, which significantly reduces the computational cost. Therefore, an outer space branch-and-bound algorithm is proposed. In addition, we conduct convergence analysis and complexity proof for the algorithm. Finally, the computational performance of the algorithm is demonstrated based on the experimental results obtained by testing a series of problems.

References

[1]	J. Mulvey, R. Vanderbei, S. Zenios, Robust optimization of large-scale systems, Oper. Res., 43 (1995), 264–281. https://doi.org/10.1287/opre.43.2.264 doi: 10.1287/opre.43.2.264
[2]	H. Konno, H. Shirakawa, H. Yamazaki, A mean-absolute deviation-skewness portfolio optimization model, Ann. Oper. Res., 45 (1993), 205–220. https://doi.org/10.1007/BF02282050 doi: 10.1007/BF02282050
[3]	M. Domeich, N. Sahinidis, Global optimization algorithms for chip design and compaction, Eng. Optimiz., 25 (1995), 131–154. https://doi.org/10.1080/03052159508941259 doi: 10.1080/03052159508941259
[4]	K. Bennett, Global tree optimization: a non-greedy decision tree algorithm, Computing Science and Statistics, 26 (1994), 156–161.
[5]	R. Cambini, C. Sodini, On the minimization of a class of generalized linear functions on a flow polytope, Optimization, 63 (2014), 1449–1464. https://doi.org/10.1080/02331934.2013.852548 doi: 10.1080/02331934.2013.852548
[6]	S. Qu, L. Shu, J. Yao, Optimal pricing and service level in supply chain considering misreport behavior and fairness concern, Comput. Ind. Eng., 174 (2022), 108759. https://doi.org/10.1016/j.cie.2022.108759 doi: 10.1016/j.cie.2022.108759
[7]	C. Maranas, I. Androulakis, C. Floudas, A. Berger, J. Mulvey, Solving long-term financial planning problems via global optimization, Comput. Ind. Eng., 21 (1997), 1405–1425. https://doi.org/10.1016/S0165-1889(97)00032-8 doi: 10.1016/S0165-1889(97)00032-8
[8]	T. Matsui, NP-hardness of linear multiplicative programming and related problems, J. Glob. Optim., 9 (1996), 113–119. https://doi.org/10.1007/bf00121658 doi: 10.1007/bf00121658
[9]	H. Ryoo, N. Sahinidis, Global optimization of multiplicative programs, J. Glob. Optim., 26 (2003), 387–418. https://doi.org/10.1023/A:1024700901538 doi: 10.1023/A:1024700901538
[10]	C. Wang, S. Liu, A new linearization method for generalized linear multiplicative programming, Comput. Oper. Res., 38 (2011), 1008–1013. https://doi.org/10.1016/j.cor.2010.10.016 doi: 10.1016/j.cor.2010.10.016
[11]	Y. Zhao, S. Liu, An efficient method for generalized linear multiplicative programming problem with multiplicative constraints, SpringerPlus, 5 (2016), 1302. https://doi.org/10.1186/s40064-016-2984-9 doi: 10.1186/s40064-016-2984-9
[12]	P. Shen, H. Jiao, Linearization method for a class of multiplicative programming with exponent, Appl. Math. Comput., 183 (2006), 328–336. https://doi.org/10.1016/j.amc.2006.05.074 doi: 10.1016/j.amc.2006.05.074
[13]	C. Wang, Y. Bai, P. Shen, A practicable branch-and-bound algorithm for globally solving linear multiplicative programming, Optimization, 66 (2017), 397–405. https://doi.org/10.1080/02331934.2016.1269765 doi: 10.1080/02331934.2016.1269765
[14]	P. Shen, B. Huang, Global algorithm for solving linear multiplicative programming problems, Optim. Lett., 14 (2020), 693–710. https://doi.org/10.1007/s11590-018-1378-z doi: 10.1007/s11590-018-1378-z
[15]	S. Schaible, C. Sodini, Finite algorithm for generalized linear multiplicative programming, J. Optim. Theory Appl., 87 (1995), 441–455. https://doi.org/10.1007/bf02192573 doi: 10.1007/bf02192573
[16]	X. Liu, T. Umegaki, Y. Yamamoto, Heuristic methods for linear multiplicative programming, J. Glob. Optim., 15 (1999), 433–447. https://doi.org/10.1023/A:1008308913266 doi: 10.1023/A:1008308913266
[17]	Y. Zhao, J. Yang, Inner approximation algorithm for generalized linear multiplicative programming problems, J. Inequal. Appl., 2018 (2018), 354. https://doi.org/10.1186/s13660-018-1947-9 doi: 10.1186/s13660-018-1947-9
[18]	B. Zhang, Y. Gao, X. Liu, X. Huang, An efficient polynomial time algorithm for a class of generalized linear multiplicative programs with positive exponents, Math. Probl. Eng., 2021 (2021), 8877037. https://doi.org/10.1155/2021/8877037 doi: 10.1155/2021/8877037
[19]	H. Konno, Y. Yajima, T. Matsui, Parametric simplex algorithms for solving a special class of nonconvex minimization problems, J. Glob. Optim., 1 (1991), 65–81. https://doi.org/10.1007/BF00120666 doi: 10.1007/BF00120666
[20]	P. Bonami, A. Lodi, J. Schweiger, A. Tramontani, Solving quadratic programming by cutting planes, SIAM J. Optimiz., 29 (2019), 1076–1105. https://doi.org/10.1137/16M107428X doi: 10.1137/16M107428X
[21]	E. Youness, 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
[22]	Y. Gao, C. Xu, Y. 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
[23]	B. Zhang, Y. Gao, X. Liu, X. Huang, Output-space branch-and-bound reduction algorithm for a class of linear multiplicative programs, Mathematics, 8 (2020), 315. https://doi.org/10.3390/math8030315 doi: 10.3390/math8030315
[24]	Y. Zhao, T. Zhao, Global optimization for generalized linear multiplicative programming using convex relaxation, Math. Probl. Eng., 2018 (2018), 9146309. https://doi.org/10.1155/2018/9146309 doi: 10.1155/2018/9146309
[25]	Z. Hou, S. Liu, Global algorithm for a class of multiplicative programs using piecewise linear approximation technique, Numer. Algor., 92 (2023), 1063–1082. https://doi.org/10.1007/s11075-022-01330-x doi: 10.1007/s11075-022-01330-x
[26]	H. Jiao, W. Wang, J. Yin, Y. 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
[27]	C. Wang, Y. Deng, P. Shen, A novel convex relaxation-strategy-based algorithm for solving linear multiplicative problems, J. Comput. Appl. Math., 407 (2022), 114080. https://doi.org/10.1016/j.cam.2021.114080 doi: 10.1016/j.cam.2021.114080
[28]	H. Jiao, W. Wang, Y. Shang, Outer space branch-reduction-bound algorithm for solving generalized 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
[29]	H. Zhou, G. Li, X. Gao, Z. Hou, Image space accelerating algorithm for solving a class of multiplicative programming problems, Math. Probl. Eng., 2022 (2022), 1565764. https://doi.org/10.1155/2022/1565764 doi: 10.1155/2022/1565764
[30]	H. Jiao, S. Liu, Y. Zhao, Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints, Appl. Math. Model., 39 (2015), 7568–7582. https://doi.org/10.1016/j.apm.2015.03.025 doi: 10.1016/j.apm.2015.03.025

Reader Comments

Your name:*

Email:*
© 2023 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)