Una Revisión del Estado del Arte en Optimización

José A. Caballero, Ignacio E. Grossmann

Resumen

En este artículo se hace una revisión de las técnicas de optimización más importantes: programación lineal y no lineal con y sin variables discretas, así como de los algoritmos disponibles hasta la fecha para resolver dichos problemas. Además de los problemas clásicos se hace una extensión para incluir problemas planteados mediante disyunciones y relaciones lógicas, optimización global determinista y estocástica, optimización en problemas sin estructura definida y una visión global de los sistemas de modelado algebraico.

Palabras clave

Optimización; LP; NLP; MINLP; MILP; Programación disyuntiva; Optimización global

Texto completo:

PDF

Referencias

Adjiman, C.S. y Floudas, C.A. (1996) Rigorous convex underestimators for general twice differentiable problems. Journal of Global Optimization, 9(1), 23-40.

Al-Khayyal F.A. (1992) Generalized bilinear Programming. Mathematics of Operations Research, 60, 306-314.

Al-Khayyal F.A. y Falk, J.E. (1983) Jointly constrained biconvex programming. Mathematics of Operations Research, 8, 273-286.

Ashford, R.W. y Daniel, R.C.; (1995). XPRESS-MP Reference Manual. Dash Associates, Blisworth House, Northants, NN73BX.

Balas, E. (1985) Disjunctive Programming and a hierarchy of relaxations for discrete optimization problems, SIAM J. Alg. Disc. Meth., 6, 466-486.

Balas, E.; Ceria, S. y Cornuejols G. (1993) A lift and project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming 58, 295- 324.

Barnhart J.R.; Johnson, E.L.; Nemhauser, G.L.; Savelsbergh, M. W. P. y Vance, P.H. (1998) Branch and Price: Column generation for solving huge integer programs. Operations Research, 46. 316-329.

Barton, P. y Pantelides, C. (1994) Modeling of combined discrete/continuous processes. AIChE Journal. 40, 966-979.

Beaumont, N. (1991) An Algorithm for Disjunctive Programs. European Journal of Operations Research, 48, 362-371.

Ben-Tal, A.; Eiger, G.; Gershovitz, V. (1994). Global optimization by reducing the duality gap. Mathematical Programming, 63,193-212.

Biegler, L.T. y Grossmann, I.E. (2004) Retrospective on Optimization. Comp. Chem. Engng, 28, 1169- 1192.

Binder, T.; Blank, L.; Bock, H.; Bulitsch, R.; Dahmen, W.; Diehl, M.; Kronseder, T.; Marquardt, W. Schloeder, J.; Stryk, O. (2001) Introduction to model based optimization of chemical processes on moving horizons. En Groetschel, M, Krumke, S.O. (Eds.) Online Optimization of large scale systems. Berlin: Springer.

Bisschop, J. y Roelofs, M. (1999). AIMMS: The Lenguaje Reference. Paragon Decision Technology. B.V., Haarlem, The Netherlands.

Bixby, R.E.; Fenelon, M.; Gu, Z.; Rothberg, E y Wunderling, R. (2002) MIP: Theory and Practice – closing the gap (http://www.ilog.com/products/ optimization/tech/research/mip.pdf)

Bonami, P.; Biegler, L.T.; Conn, A.R.; Cornuéjols, G; Grossmann, I.E.; Laird, C.D.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A.; (2005) An algorithmic framework for convex mixed integer nonlinear programs. IBM Research Report RC23771 (W0511-023)

Booker, A.J.; Dennis Jr. J.E.; Frank, P.D.; Serafini, D.B.; Torczon, V.; Trosset, M.W. (1998). A rigorous framework optimization of expensive functions by surrogates. CRPC Technical Report 98739, Rice University.

Borchers, B.; Mitchell, J.E. (1994) An Improved Branch and Bound algorithm for mixed integer non linear programming. Computers and Operations Research. 21, 359-367

Brooke, A.; Kendrick, D.; Meeraus, A.; (1992); GAMS: A User`s Guide. Boyd y Fraser Publising Company, Danvers, Massachusets.

Byrd, R.H.; Hribar, M.E. y Nocedal, J. (1997) An interior point algorithm for large scale nonlinear programming. Optimization technology Center, Northwestern University.

Ceria S. and J. Soares. (1999) Convex Programming for Disjunctive Optimization. Mathematical Programming, 86(3), 595-614.

Conn, A.R.; Gould, N y Toint, P (2000). Trust Region Methods. Philadelphia, USA. MPS/SIAM. Series on Optimization

Conn, A.R.; Scheinberg, K.; Toint, P. (1997) Recent progress in unconstrained nonlinear optimization without derivatives. Mathematical Programming, Series B 79(3), 397.

Dakin, R.J. (1965) A tree search algorithm for mixed integer programming problems. Computer Journal, 8, 250-255.

Dantzing, G.B., (1963). Linear Programming and Extensions, Princeton University Press.

Dennis, J.E. y Torczon, V. (1991) Direct search methods on parallel machines. SIAM journal of Optics, 1, 448.

Duran, M.A. y Grossmann, I.E. (1986) An Outer Approximation Algorithm for a Class of Mixed Integer Non Linear Programs. Mathematical Programming, 36, 307.

Edgar, T.F.; Himmelblau, D.M.; Lasdon L.S. (2002) Optimization of Chemical Processes. New York: McGrawHill.

Eldred, M. (2002). DAKOTA: A multilevel parallel object oriented framework for design optimization, parameter estimation, uncertainty quantification, and sensitivity analysis.(http://endo.sandia.gov/ DAKOTA/software.html).

Elmqvist, H.; Mattsson, S.; Otter, M. (1998). Modelica: the new object-oriented modeling language. http://citeseer.nj.nec.com/elmqvist98 modelica.html

Fletcher, R. y Leyffer, S. (1994) Solving Mixed Integer Non Linear Programs by Outer Approximation. Mathematical Programming 66, 327.

Fletcher, R. (1987) Practical methods of optimization. Chichester. Wiley.

Fletcher, R.; Gould, N. I. M.; Leyffer, S.; Toint, Ph. L. y Waechter, A (2002). Global convergence of a trust-region (SQP) filter algorithms for general nonlinear programming. SIAM Journal on Optimization, 13 (3) 635 - 659

Flippo, O.E.; Rinnoy Kan, A.H.G. (1993) Decomposition in General Mathematical Programming. Mathematical Programming, 60, 361-382.

Floudas, C. A. y Visweswaran, V. (1990). A global optimization algorithm (GOP) for certain classes of non convex NLPs I Theory. Computers and Chemical Engineering, 14, 1397-1417.

Floudas, C.A. (2000). Deterministic Global Optimization: Theory, methods and applications. Dordretcht, The Netherlands: Kluwer Academic Publishers.

Fourer, R.; Gay, D.M.; Kernighan, B.W. (1993). AMPL: A Modeling Language for Mathematical Programming. Duxbury Press, Brooks/Cole Publishing Company, Monterrey, CA.

Geofrion, A.M. (1972) Generalized Benders Decomposition. Journal of Optimization Theory and Applications, 10(4), 237-260.

Griewank, A. y G Corliss, editors (1991). Automatic Differentiation of Algorithms: Theory, Implemetation and Application, Philadelphia, SIAM.

Grossmann, I. E. (1996). Global optimization in engineering design. Dordretcht, The Netherlands: Kluwer Academic Publishers.

Grossmann, I.E. y S. Lee. (2002) Generalized Disjunctive Programming: Nonlinear Convex Hull Relaxation and algorithms. Computational Optimization and Applications.

Gupta, O.K.; Ravindran, V. (1985) branch and Bound experiments in nonlinear integer programming. Management Sciences. 31(12), 1533-1546.

Han, S.P. (1976) Superlinearly Convergent Variable Metric Algorithms for General Nonlinear Programming Problems. Math Progr., 11, 263- 82.

Hansen, E.R. (1980). Global optimization using interval analysis: The multidimensional case. Numerische Mathematick. 34, 247-270.

Hansen, P.; Jaumard, B.; Lu, S. (1992a) Global optimization of univariate Lipschitz functions. Surrey and properties. Mathematical Programming. 55, 251-272.

Hansen, P.; Jaumard, B.; Lu, S. (1992b) Global optimization of univariate Lipschitz functions: New algorithms and computational comparison. Mathematical Programming. 55, 273-292.

Holland J.H. (1975) Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press.

Hooker, J.N. y Osorio, M.A. (1999) Mixed logical. linear programming. Discrete Applied Mathematics, 96-97, pp.395-442.

Hooker, J.N. (2000) Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction. Wiley.

Horst, R. y Tuy, H. (1987) On the convergence of global methods in multiextremal optimization. Journal of Optimization Theory and Applications, 54 253.

Horst, R.; Thoai, N.V.; De Vries J. (1992). A new simplicial cover technique in constrained global optimization. Journal of Global Optimization, 2, 1- 19.

ILOG (2000) http://www.ilog.com/products/ optimization/info/qpperformance.cfm

Johnson, E.L.; Nemhauser E. L. y Savelsbergh, M. W. P. (2000) Progress in Linear Programming based branch and bound algorithms: Exposition. INFORMS Journal of Computing, 12.

Kallrath, J. (2004). Modeling languages in Mathematical Optimization. Kluwer Academic Publishers.

Karmarkar, N. (1984) A New Polynominal-time algorithm for linear programming. Combinatorica, 4(4):373—395.

Kelley Jr, J.E. (1960) The Cutting Plane Method for Solving Convex Programs. Journal of SIAM 8, 703-712.

Kennedy, J. y Everhart, R.C. (1995a) A discrete binary version of the particle swarm algorithm. In Proceedings of the conference of systems, Man and Cybernetics. 4104-4109.

Kennedy, J. y Everhart, R.C. (1995b) A new optimizer using particle swarm theory. In proceedings of the sixth international symposium on micro machine and human science. Nagoya Japón. IEEE service center Piscataway, NJ.

Kocis, G.R. y Grossmann. I.E. (1987) Relaxation Strategy for the Structural Optimization of Process Flowsheets. Ind. Eng. Chem. Res. 26, 1869.

Kravanja, Z y Grossmann, I.E. (1994). New developments and capabilities in PROSYN an automated topology and parameter process synthesizer. Computers Chem. Eng. 18, 1097-1114.

Laahorven, P.J.M y Van Aarts E.H.L. (1987). Simmulated annealing: theory and applications. Dordrecht: Reidel.

Lee, S. y I.E. Grossmann. (2000) New Algorithms for Nonlinear Generalized Disjunctive Programming. Computers and Chemical Engineering 24, 2125- 2141.

Leyffer, S. (2001) Integrating SQP and Branch and Bound for Mixed Integer non Linear Programming. Computational Optimization and Applications, 18, 295-309.

Luus, R. y Jaakola, T.H.I. (1973) Direct search for complex systems. AIChE Journal, 19, 645-646.

Ming S. Hung, Walter O. Rom, and Allan D. Waren (1993) Optimization with IBM OSL and Handbook for IBM OSL, The Scientific Press (now Duxbury Press),

Murtagh, B. A. y Saunders, M. A. (1987). Minos 5.1 user’s guide. Technical Report SOL 83-20R. Stanford University.

Nedler, J.A. y Mead, R. (1965). A simplex method for function minimization. Computer Journal, 7, 308.

Nemhauser, G.L. y Wolsey, L.A. (1988) Integer and Combinatorial Optimization. New York Wiley Interscinece.

Nocedal, J. y Wright, S.J. (1999). Numerical Optimization. NewYork: Springer.

Piela, P., Epperly, Y.; Westerber, K; Westerberg, A. (1991) ASCEND: An object-oriented computer environment for modeling and analysis: The Modeling Language. Computers and Chemical Engineering. 15(1), 53-72.

Pörn, R. y Westerlund, T. (2000) A Cutting Plane Method for Minimizing Pseudo-Convex Functions in the Mixed Integer Case. Computers and Chemical Engineering, 24, 2655-2665.

Powell, M.J.D. (1964) An efficient method for finding the minimum of a function of several variables without calling derivatives. Computing Journal. 7, 155.

Powell, M.J.D., (1978) A Fast Algorithm for Nonlinearly Constrained Optimization Calculations. In Numerical Analysis, Dundee, G.A. Watson (ed.), Lecture Notes in Mathematics 630, Springer-Verlag, Berlin.

Quesada, I. y Grossmann, I.E. (1995). A global optimization algorithm for linear fractional and bilinear programs. Journal of Global Optimization, 6(1), 39-76.

Quesada, I.E. y Grossmann, I.E. (1992) An LP/NLP Based Branch and Bound Algorithm for Convex MINLP Optimization Problems. Computers and Chemical Engineering 16, 937-947.

Raman, R. y I.E. Grossmann. (1991) Relation Between MILP Modeling and Logical Inference for Chemical Process Synthesis. Computers and Chemical Engineering 15, 73.

Raman, R. y I.E. Grossmann. (1993). Symbolic Integration of Logic in Mixed Integer Linear Programming Techniques for Process Synthesis. Computers and Chemical Engineering, 17, 909.

Raman, R. y I.E. Grossmann. (1994) Modeling and Computational Techniques for Logic Based Integer Programming. Computers and Chemical Engineering, 18, 563.

Rivera, J. (1998) Modeling with EXTEND. In Winter Simulation Conference. 257-262.

Ryoo, H.S. y Sahinidis, N.Y. (1995) Global optimization of nonconvex NLPs and MINLPs with applications in process design. Computers and Chemical Engineering. 19(5), 551-566.

Sahinidis, N. V. (1996) BARON: A general purpose global optimization software package. Journal of Global Optimization, 8(2), 201-205.

Sawaya, N y I.E. Grossmann (2006). Computational Implementation of nonlinear convex hull reformulation. Por aparecer en Computers and Chemical Engineering.

Scharage, L. (1999) Optimization Modeling with LINGO. LINDO Systems, Inc, Chicago, Il.

Schichl, H.; Neumaier, A.; Dallwig, S (2001). The NOP-2 Modeling Language. Annals of Operations Research, 104, 281-312.

Schweiger, C.A.; Rojnuckarin, A.; Floudas, C.A. (1996). MINOPT: A Software Package for MixedInteger Nonlinear Optimization. Dept Of Chemical Engineering, Princeton University, NJ.

Sherali, H.D. y Alameddine, A. (1992). A new reformulation – linearization technique for bilinear programming problems. Journal of Global Optimization, 2, 379-410.

Sherali, H.D. y Tuncbilek, C.H. (1992). A global optimization algorithm for polynomial programming problems using a reformulationlinearization technique. Journal of Global Optimization, 2, 101-112.

Shor, N.Z. (1990). Dual quadratic estimates in polynomial and Boolean programming. Annals of Operations Research, 25, 163-168.

Smith, E.M.B. y Pantelides, C.C. (1999). A symbolic reformulation spatial Branch and bound algorithm for the global optimization of nonconvex MINLPs. Computers and Chemical Engineering, 23, 457- 478.

Stubbs R. y S. Mehrotra. (1999) A Branch-and-Cut Method for 0-1 Mixed Convex Programming. Mathematical Programming, 86(3), 515-532.

Tawarmalani, M y Sahinidis, N.V. (2004). Global optimization of mixed integer non linear programs: theoretical and computational study. Mathematical programming Ser. A 99, 563–591

Tawarmalani, M. y N. V. Sahinidis, (2002) Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Kluwer Academic Publishers, Dordrecht, Vol. 65 in Nonconvex Optimization And Its Applications series.

Türkay, M. and I.E. Grossmann, (1996). A Logic Based Outer-Approximation Algorithm for MINLP Optimization of Process Flowsheets. Computers and Chemical Enginering, 20, 959-978.

Tuy, R. (1987). Global minimum of difference of two convex functions. Mathematical Programming Study, 30, 150-182.

Tuy, R.; Thieu, T.V.; Thai, N.Q. (1985) A conical algorithm for globally minimizing a concave function over a closed convex set. Mathematics of Operations Research, 10, 498-514.

Van Hentenryck, P.; Michel, J.; Deville, Y.; (1997). Numerica – A Modeling language for Global Optimization. MIT Press, Cambridge MA.

Vecchietti, A. y I.E. Grossmann. (1999) LOGMIP: A Discrete Continuous Nonlinear Optimizer. Computers and Chemical Engineering 23, 555- 565.

Vecchietti, A. y I.E. Grossmann. (2000) Modeling Issues and Implementation of Language for Disjunctive Programming. Computers and Chemical Engineering 24, 2143-2155.

Viswanathan, J. y Grossmann, I.E. (1990) A Combined Penalty Function and Outer Approximation Method for MINLP Optimization. Computers and Chemical Engineering, 14, 769.

Wächter, A. (2002) An interior point algorithm for large scale non linear optimization with applications in process engineering. Ph. D. Tesis Carnegie Mellon University.

Wätcher A. y Biegler. L.T. (2002) Global and local convergence of line search filter methods for nonlinear programming. CAPD Technical report B-01-09.

Westerlund, T. y Pettersson, A. (1995) A Cutting Plane Method for Solving Convenx MINLP Problems. Computers and Chemical Engineering, 19, S131-S136.

Williams, H.P. (1985) Mathematical Building in Mathematical Programming. John Wiley, Chichester.

Yuan, X.; Zhang, S.; Piboleau, L.; Domenech, S. (1988) Une Methode d’optimisation Nonlineare en Variables Mixtes pour la Conception de Procedes RAIRO 22, 331.

Zamora, J.M. y Grossmann, I.E. (1998) Continuous global optimization of structured process system models. Computers and Chemical Engineering, 22(12), 1749-1770.

Zamora, J.M. y Grossmann, I.E. (1999) A branch and bound algorithm for problems with concave univariate. Journal of Global Optimization, 14(3), 217-249.

Abstract Views

912
Metrics Loading ...

Metrics powered by PLOS ALM




Creative Commons License

Esta revista se publica bajo una Licencia Creative Commons Attribution-NonCommercial-CompartirIgual 4.0 International (CC BY-NC-SA 4.0)

Universitat Politècnica de València     https://doi.org/10.4995/riai

e-ISSN: 1697-7920     ISSN: 1697-7912