A BRANCH-AND-BOUND REDUCED ALGORITHM FOR SOLVING A CLASS OF LINEAR MULTIPLICATIVE PROGRAMMING PROBLEMS
Gao Yuelin1,2, Jing Xia3
1. Institute of Information and System Science, Beifang University for Nationalities, Yinchuan 750021, China;
2. School of Mathematics and Computer Science, Ningxia University, Yinchuan 750021, China;
3. School of Mathematics and Computer Science, Ningxia University, Yinchuan 750021, China
Abstract：
A branch-and-bound reduced method is proposed for globally solving a class of linear multiplicative programming problems and the convergence of the algorithm is proved. In this algorithm, the lower bound functions on the multiplications in the constraints and the objective functions are given by using the convex envelopes technique of the two-vector multiplications so as to determine a relaxed convex programming of the original problem. We solve the relaxed convex programming to find the global optimization value's lower bound the feasible solutions of the original problem.In order to improve convergence rate, a rectangular reduction strategy is used. Numerical experiments show that the proposed algorithm is feasible.
. A BRANCH-AND-BOUND REDUCED ALGORITHM FOR SOLVING A CLASS OF LINEAR MULTIPLICATIVE PROGRAMMING PROBLEMS[J]. Mathematica Numerica Sinica, 2013, 35(1): 89-98.
[1]
Marinas C D, Andreoulakis I P, Floudas C.A. Solving long term financial planning problems viaglobal optimization[J]. Journal of Economic Dynamics and Control, 1997, 21: 1405-1425.
[2]
Mulvey J M, Vanderbei R J, Zenios S A. Robust optimization of large-scale system[J]. OperationsResearch, 1995, 43: 264-281.
[3]
Donnish M C, Salinities N V. Global optimization algorithms for chip design andcompaction[J].Engineering Optimization, 1995, 25(2): 131-154.
[4]
Kuno T. Globally determining a minimun-aera rectangle enclosing the projection of a higherdimensional Set[J]. Operations Research Letters, 1993, 13: 295-303.
[5]
Bennett K P and Mangasarian. Bilinear separation of two sets in n-space[J]. ComputationalOptimization and Application, 1994, 2: 207-227.
[6]
Kuno T, Yajima Y, and Konno H. An outer approximation method for minimizing the product ofseveral convex functions on a convex set[J]. Journal of Global optimization, 1993, 3(3): 325-335.
[7]
Benson H P. Decomposition branch and bound based algorithm for linear programs with additionalmultiplicative constraints[J]. Journal of Optimization Theory and Applications, 2005,126(1): 41-46.
[8]
Flippo O E Rinnoy K. A note on Benders decomposion in mixed-integer quadratic programming[J]. Operations Research Letters, 1990, 9: 81-83.
[9]
Stabile S, Sodini C. Finite algorithm for generalized linear multiplicative programming[J]. Journalof Optimization Theory and Applications, 1995, 87(2): 441-455.
[10]
Benson H P, Boger G M. Outcome-space cutting-plane algorithm for linear multiplicative programming[J]. Journal of Optimization Theory and Applications, 2001, 104(2): 301-322.
Shen Peiping, Jiao Hongwei. Linearization method for a class of multiplicative programmingwith exponent[J]. Applied Mathematics and Computation, 2006, 183: 328-336.
[13]
Gao Yuelin, Wu Guorong, Ma Weiming. A new global optimization approach for convex multiplicativeprogramming[J]. Applied Mathematics and Computation, 2010, 216: 1206-1218.
[14]
黄红选译．全局优化引论[M]. 北京: 清华大学出版社, 2003, 9.
[15]
Kuno T. A finite branch and bound algorithm for generalized linear multiplicative programming[J]. Computational Optimization and Application, 2001, 20: 119-135.
