×

A branch and bound algorithm for globally solving a class of nonconvex programming problems. (English) Zbl 1155.90459

Summary: A branch and bound algorithm is proposed for globally solving a class of nonconvex programming problems (NP). For minimizing the problem, linear lower bounding functions (LLBFs) of objective function and constraint functions are constructed, then a relaxation linear programming is obtained which is solved by the simplex method and which provides the lower bound of the optimal value. The proposed algorithm is convergent to the global minimum through the successive refinement of linear relaxation of the feasible region and the solutions of a series of linear programming problems. And finally the numerical experiment is reported to show the feasibility and effectiveness of the proposed algorithm.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Henderson, J. M.; Quandt, R. E., Microeconomic Theory (1971), McGraw-Hill: McGraw-Hill New York · Zbl 0224.90014
[2] Maranas, C. D.; Androulakis, I. P.; Floudas, C. A.; Berger, A. J.; Mulvey, J. M., Solving long-term financial planning problems via global optimization, J. Econom. Dynam. Control, 21, 1405-1425 (1997) · Zbl 0901.90016
[3] Markowitz, H. M., Portfolio Selection (1991), Basil Blackwell Inc.: Basil Blackwell Inc. Oxford
[4] Quesada, I.; Grossmann, I. E., Alternative bounding approximations for the global optimization of various engineering design problems, (Grossmann, I. E., Global Optimization in Engineering Design, Nonconvex Optimization and Its Applications, vol. 9 (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 309-331 · Zbl 0879.90189
[5] Mulvey, J. M.; Vanderbei, R. J.; Zenios, S. A., Robust optimization of large-scale systems, Oper. Res., 43, 264-281 (1995) · Zbl 0832.90084
[6] Benson, H. P., Decomposition branch and bound based algorithm for linear programs with additional multiplicative constraints, J. Optim. Theory Appl., 126, 41-46 (2005) · Zbl 1093.90040
[7] Kuno, T., A finite branch and bound algorithm for linear multiplicative programming, Comput. Optim. Appl., 20, 119-135 (2001) · Zbl 0983.90075
[8] Ryoo, H. S.; sahinidis, N. V., Global optimization of multiplicative programs, J. Glob. Optim., 26, 387-418 (2003) · Zbl 1052.90091
[9] 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
[10] Benson, H. P.; Boger, G. M., Outcome-space cutting-plane algorithm for linear multiplicative programming, J. Optim. Theory Appl., 104, 301-322 (2000) · Zbl 0962.90024
[11] Liu, X. J.; Umegaki, T.; Yamamoto, Y., Heuristic methods for linear multiplicative programming, J. Glob. Optim., 4, 433-447 (1999) · Zbl 0966.90051
[12] Ryoo, H. S.; sahinidis, N. V., Global optimization of multiplicative programs, J. Glob. Optim., 26, 387-418 (2003) · Zbl 1052.90091
[13] Schaible, S.; Sodini, C., Finite algorithm for generalized linear multiplicative programming, J. Optim. Theory Appl., 87, 2, 441-455 (1995) · Zbl 0839.90113
[14] Shen, P. P.; Jiao, H. W., Linearization method for a class of multiplicative programming with exponent, Appl. Math. Comput., 183, 1, 328-336 (2006) · Zbl 1110.65051
[15] Hoai-Phuony, Ng. T.; Tuy, H., A unified monotonic approach to generalized linear fractional programming, J. Glob. Optim., 26, 229-259 (2003) · Zbl 1039.90079
[16] Benson, H. P., A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem, Europ. J. Oper. Res., 182, 597-611 (2007) · Zbl 1121.90102
[17] Wang, Y. J.; Shen, P. P.; Liang, Z. A., A branch-and-bound algorithm to globally solve the sum of several linear ratios, Appl. Math. Comput., 168, 89-101 (2005) · Zbl 1079.65071
[18] Jiao, H. W.; Guo, Y. R.; Shen, P. P., Global optimization of generalized linear fractional programming with nonlinear constraints, Appl. Math. Comput., 183, 2, 717-728 (2006) · Zbl 1111.65052
[19] Maranas, C. D.; Floudas, C. A., Global optimization in generalized geometric programming, Comput. Chem. Eng., 21, 4, 351-369 (1997) · Zbl 0891.90165
[20] Floudas, C. A.; Visweswaran, V., Quadratic Optimization, (Horst, R.; Pardalos, P. M., Handbook of Global Optimization, Nonconvex Optimization and its Applications (1995), Kluwer Academic Publishers), 217-270 · Zbl 0833.90091
[21] Shen, P. P.; Jiao, H. W., A new rectangle branch-and-pruning approach for generalized geometric programming, Appl. Math. Comput., 183, 1027-1038 (2006) · Zbl 1112.65058
[22] 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
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.