Mixed-integer nonlinear programming

From DDWiki

Jump to: navigation, search

Mixed-integer nonlinear programming refers to optimization problems of the form:

minimize f(\mathbf{x,y})
with respect to \mathbf{x,y}
subject to \mathbf{g(x,y) \leq 0}
\mathbf{h(x,y)=0}
\mathbf{x}\in\Re^n
\mathbf{y}\in\mathcal{Z}^m

where n and m are positive integers, and \mathcal{Z} is the set of integers. If f(\mathbf{x,y}) and \mathbf{g(x,y)} are convex functions of the vectors \mathbf{x} and \mathbf{y}, and if \mathbf{h(x,y)} is an affine function of the vectors \mathbf{x} and \mathbf{y}, then the problem is a convex MINLP.

Contents

Theory

This article has been marked as incomplete and requiring attention. You can help DDWiki by expanding it.


Methods

Because nonconvex MINLPs may in general have multiple local minima, methods that ensure global solutions employ branch and bound methods that rely on convex underestimation of the objective and constraint functions. Global optima can generally only be found when valid convex underestimators can be generated automatically, such as for factorable functions.

Generally, local minima to MINLPs can be found using modified versions of methods for solving convex MINLPs.


Software

  • BARON
    • Author: Nick Sahinidis and Mohit Tawarmalani
    • Method: Branch and reduce optimization navigator is the integration of range reduction techniques using constraint programming and duality within the branch and bound framework for global optimization of general nonconvex MINLPs. Lower bounds are provided using factorable programming for generating convex underestimators followed by polyhedral outer approximation to linearize convex lower bounds enabling use of reliable LP solvers. All functions should be differentiable; supported functions include polynomials, power function, exponential and logarithm, other forms such as trigonometric terms are not allowed; moreover, all nonlinear terms should be bounded appropriately to avoid numerical errors.
    • Links:


Black box solvers

  • LGO
    • Author: Pintér Consulting Services, Inc.
    • Method: The LGO solver integrates algorithms of global and local scope (branch and bound based global search, global adaptive random search, multistart global search, exact penalty function based local search, constrained local optimization). It serves to analyze and solve complex nonlinear models, using only function values.
    • Links:

References

[1] I.E. Grossmann, "Mixed-integer optimization techniques for algorithmic process synthesis," Advances in Chemical Engineering, J.L.Anderson, ed., vol. 23: Process Synthesis, pp.171-246, Academic Press: San Diego, 1996a.

[2] I.E. Grossmann, J. Quesada, R. Raman and V. Voudouris,"Mixed integer optimization techniques for the design and scheduling of batch processes," inBatch Processing Systems Engineering, G.V. Reklaitis, A.K. Sunol, D. W.T. Rippin, and O. Hortacsu, eds., Springer-Verlag:Berlinmpp.451-494,1996.

[3] Brooke, A, Drud, A S, and Meeraus, A, Modeling Systems and Nonlinear Programming in a Research Environment. In Ragavan, R and Rohde, S M, Eds, Computers in Engineering, Vol. III. ACME, 1985.

[4] Michalek, J.J. and P.Y. Papalambros (2006) "MINLP-ATC: Analytical Target Cascading for Mixed-integer Nonlinear Programming," Proceedings of IDETC/CIE, September 10-13, 2006, Philadelphia, Pennsylvania, USA.

[5] I.E. Grossmann and N.V. Sahinidis (eds) (2002). Special Issue on Mixed-integer Programming and it’s Application to Engineering, Part I Optim.Eng., 3 (4), Kluwer Academic Publishers, Netherlands.

[6] I.E. Grossmann and N.V. Sahinidis (eds) (2002). Special Issue on Mixed-integer Programming and it’s Application to Engineering, Part II Optim. Eng., 4 (1), Kluwer Academic Publishers, Netherlands.

[7] G. L. Nemhauser and L. A. Wolsey.Integer and Cominatorial Optimization. J. Wiley, New York, 1998.

[8] Grossmann I.E.., Biegler L.T.,(2004) "Retrospective on Optimization," Computers and Chemical Engineering 28 1169-1192.

[9] I.E. Grossmann and Z. Kravanja, "Mixed-integer nonlinear programming: A survey of algorithms and applications," in The IMA Volumes in Mathematics and its Applications, vol.93: Large-Scale Optimization with Applications, Part II: Optimal Design and Control, Biegler, Coleman, Conn, and Santosa, eds, Springer-Verlag: Berlin, pp.73-100, 1997.

[10] A.M. Geoffrion, "Generalized benders decomposition," Journal of Optimization Theory and Applications vol. 10, no.4, pp. 237-260, 1972.

[11] B.Borchers and J.E. Mitchell, "An improved branch and bound algorithm for mixed integer nonlinear programming," Computers and Operations Research vol. 21,pp.359-367. 1994.

[12] M.A. Duran and I.E. Grossmann, "An outer-approximation algorithm for a class of mixed-integer nonlinear program," Math Programming vol. 36, p.307, 1986.

[13] G.R. Kocis and I.E. Grossmann, "Relaxation strategy for the structural optimization of process flowsheets," Ind. Eng. Chem. Res. vol. 26, p. 1869, 1987.

[14] J. Viswanathan and I.E. Grossmann, "A combined penalty function and outer approximation method for MINLP optimization," Comput. Chem, Engng. vol. 14,p. 769, 1990.

[15] Tawarmalani, M. and N. V. Sahinidis, "Global optimization of mixed-integer nonlinear programs: A theoretical and computational study," Mathematical Programming, 99(3), 563-591, 2004.

[16] I.E. Grossmann and R. Karuppiah, "A Lagrangian based Branch-and-Cut algorithm for global optimization of nonconvex Mixed-Integer Nonlinear Programs with decomposable structures," Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, 15213, July 2006.

[17] R. Porn, T. Westerlund, "A Cutting Plane Method for Minimizing Psuedo-convex Functions in the Mixed Integer Case. Computers and Chemical Engineering, 24, 2655-2665(2000)

Retrieved from "http://ddl.me.cmu.edu/ddwiki/index.php/Mixed-integer_nonlinear_programming"
Personal tools