×

Global solution of optimization problems with signomial parts. (English) Zbl 1134.90041

Summary: A new approach for the global solution of nonconvex MINLP (Mixed Integer NonLinear Programming) problems that contain signomial (generalized geometric) expressions is proposed and illustrated. By applying different variable transformation techniques and a discretization scheme a lower bounding convex MINLP problem can be derived. The convexified MINLP problem can be solved with standard methods. The key element in this approach is that all transformations are applied termwise. In this way all convex parts of the problem are left unaffected by the transformations. The method is illustrated by four example problems.

MSC:

90C30 Nonlinear programming
90C11 Mixed integer programming

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Pörn, R.; Harjunkoski, I.; Westerlund, T., Convexification of different classes of nonconvex MINLP problems, Computers and Chemical Engineering, 23, 439-448 (1999)
[2] Harjunkoski, I.; Westerlund, T.; Pörn, R.; Skrifvars, H., Different transformations for solving nonconvex Trim-Loss problems by MINLP, European Journal of Operational Research, 105, 594-603 (1998) · Zbl 0955.90095
[3] I. Harjunkoski, Application of MINLP methods to a scheduling problem in the paper-converting industry, Ph.D. Thesis in Process Synthesis, Åbo Akademi University, 1997. ISBN 952-12-0091-X; I. Harjunkoski, Application of MINLP methods to a scheduling problem in the paper-converting industry, Ph.D. Thesis in Process Synthesis, Åbo Akademi University, 1997. ISBN 952-12-0091-X
[4] Passy, U.; Wilde, D. J., Generalized polynomial optimization, SIAM Journal of Applied Mathematics, 15, 1344 (1967) · Zbl 0171.18002
[5] Blau, G. E.; Wilde, D. J., A Lagrangian algorithm for equality constrained generalized polynomial optimization, AIChE, 17, 235 (1971)
[6] Duffin, R. J.; Peterson, E. L., Reversed geometric programming treated by harmonic means, Indiana University Mathematics Journal, 22, 531 (1972) · Zbl 0246.90044
[7] Rijckaert, M. J.; Martens, X. M., A bibliographical note on geometric programming, JOTA, 2, 325 (1978) · Zbl 0369.90111
[8] Dembo, R. S., Current state of the art of algorithms and computer software for geometric programming, JOTA, 26, 149 (1978) · Zbl 0369.90121
[9] J.E. Falk, Global solutions of signomial programs, Report, The George Washington University, Program in Logistics, 1973; J.E. Falk, Global solutions of signomial programs, Report, The George Washington University, Program in Logistics, 1973
[10] Maranas, C. D.; Floudas, C. A., Global optimization in generalized geometric programming, Computers and Chemical Engineering, 21, 351-369 (1997)
[11] Minkowski, H., Geometrie der zahlen (1896), Teubner: Teubner Leipzig · JFM 27.0127.09
[12] Avriel, M.; Diewert, W. E.; Shaible, S.; Zang, I., Generalized Concavity (1988), Plenum Press
[13] Maranas, C. D.; Floudas, C. A., Finding all solutions of nonlinearly constrained systems of equations, Journal of Global Optimization, 7, 143-182 (1995) · Zbl 0841.90115
[14] Winston, W., Operations Research—Applications and Algorithms (1994), Duxbury Press · Zbl 0867.90079
[15] Floudas, C. A., Nonlinear and Mixed-Integer Optimization—Fundamentals and Applications (1995), Oxford University Press · Zbl 0886.90106
[16] Williams, H. P., Experiments in the formulation of integer programming problems, Mathematical Programming Study, 2, 180-197 (1974)
[17] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), John Wiley and Sons · Zbl 0652.90067
[18] Padberg, M., Approximating separable nonlinear functions via mixed zero-one programs, Operations Research Letters, 1-5 (2000) · Zbl 0960.90065
[19] Cplex. http://www.ilog.com/products/cplex/, 2006; Cplex. http://www.ilog.com/products/cplex/, 2006
[20] XPRESS. http://www.dashoptimization.com/home/products/products_optimizer.html, 2006; XPRESS. http://www.dashoptimization.com/home/products/products_optimizer.html, 2006
[21] Lp-solve. http://www.cs.sunysb.edu/ algorith/implement/ lpsolve/implement.shtml, 2006; Lp-solve. http://www.cs.sunysb.edu/ algorith/implement/ lpsolve/implement.shtml, 2006
[22] Beale, E. M.L, Branch-and-bound methods for mathematical programming systems, Annals of Discrete Mathematics, 5, 201-219 (1979) · Zbl 0405.90049
[23] Williams, H. P., Model Solving in Mathematical Programming (1993), John Wiley & Sons Ltd.: John Wiley & Sons Ltd. Chichester · Zbl 0788.90053
[24] Al-Khayyal, F. A.; Falk, J. E., Jointly constrained biconvex programming, Mathematics of Operations Research, 8, 273-286 (1983) · Zbl 0521.90087
[25] T. Westerlund, Global optimization, in: L. Liberti, N. Maculan (Eds.), Theory to Implementation, Kluwer Academic Press, pp. 45-74 (Chapter 3 ); T. Westerlund, Global optimization, in: L. Liberti, N. Maculan (Eds.), Theory to Implementation, Kluwer Academic Press, pp. 45-74 (Chapter 3 ) · Zbl 1100.90037
[26] Westerlund, T.; Petterson, F., An extended cutting plane method for solving convex MINLP problems, Computers and Chemical Engineering, 19, Suppl., 131-136 (1995)
[27] Quesada, I.; Grossamnn, I., A global optimization algorithm for linear fractional and bilinear programs, Journal of Global Optimization, 6, 39-76 (1995) · Zbl 0835.90074
[28] Ryoo, H. S.; Sahinidis, N. V., Global optimization of nonconvex NLPs and MINLPs with applications in process design, Computers and Chemical Engineering, 19, 551-566 (1995)
[29] Adjiman, C. S.; Androulakis, I. P.; Floudas, C. A., A global optimization method, aBB, for general twice-differentiable constrained NLPs-II. Implementation and computational results, Computers and Chemical Engineering, 22, 1159-1179 (1998)
[30] Smith, E. M.B.; Pantelides, C. C., A symbolic reformulation/spatial branch and bound algorithm for the global solution of nonconvex MINLPs, Computers and Chemical Engineering, 23, 457-478 (1999)
[31] Quesada, I.; Grossmann, I., Global optimization algorithm for heat exchanger networks, Industrial Engineering and Chemical Resort, 32, 487-499 (1993)
[32] R. Pörn, Mixed integer nonlinear programming: Convexification techniques and algorithm development, Ph.D. Thesis in Applied Mathematics, Åbo Akademi University, ISBN 952-12-0681-X, 2000; R. Pörn, Mixed integer nonlinear programming: Convexification techniques and algorithm development, Ph.D. Thesis in Applied Mathematics, Åbo Akademi University, ISBN 952-12-0681-X, 2000
[33] Kocis, G. R.; Grossmann, I., Global optimization of nonconvex mixed-integer nonlinear programming (MINLP) problems in process synthesis, Industrial Engineering Chemical Resort, 27, 1407 (1988)
[34] Haverly, C. A., Studies of the behavior of recursion for the pooling problem, ACM SIGMAP Bulletin, 25, 19-28 (1978)
[35] Roberts, A. W.; Varberg, D. E., Convex Functions (1973), Academic Press · Zbl 0271.26009
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.