575b Parallel Global Optimization for Nlp and Minlp Programming Problems

Pradeep K. Polisetty1, David M. Gay2, William Hart2, and Edward P. Gatzke1. (1) Chemical Engineering, University of South Carolina, Dept. of Chemical Engineering, Swearingen Engineering Center, 301 Main St., Columbia, SC 29208, (2) Sandia National Laboratory, NM

 

     The objective of this work is to develop efficient large scale parallel methods for global optimization of nonconvex nonseparable nonlinear programming (NLP) and mixed-integer nonlinear programming (MINLP) problems. Finding global optima of nonconvex nonlinear optimization problems has been an important topic for many researchers. Branch-and-bound [2, 6, 3] and Outer-Approximation algorithms [1, 4] can be used for solving MINLP problems to global solutions. Existing optimization routines when implemented sequentially may require large amount of time in determining global solutions. Significant speed-up can be attained by implementing these techniques on parallel machines.

     Several commercial software tools are already available for solving NLP and MINLP problems. However, existing tools can be expensive and difcult to extend or adapt and may not support parallel searches. An overview of GNLP, an object-oriented open source software package for global nonlinear programming on parallel machines is presented. GNLP can be applied to a wide range of industrial and scientific applications. GNLP is a branch-and-bound based code for rigorous optimization of algebraically specified nonlinear functions subject to nonlinear constraints, involving bounded continuous or discrete variables. GNLP builds on PICO's facilities for parallel computing, rewrites expression graphs to obtain convex or linear bounding functions, and uses some facilities from COCONUT [10]. COCONUT is another open-source global optimization project developed within academic framework and can support the use of various bounding strategies and AMPL for automatic differentiation.

     GNLP is integrated with various public domain LP solvers and IPOPT [9], an open source NLP optimization solver for determining locally optimal solutions that can be used as upper bounds during branch-and-bound implementation. Linear Programming (LP) based relaxations for nonconvex nonlinear expressions can be generated using reformulation technique of McCormick and Smith [5, 7] combined with linearization strategy of Tawarmalani and Sahinidis [8]. Additionally, LP based relaxations can also be generated using COCONUT's interval slopes and exclusion box techniques [10]. The advantage of using multiple lower bounding techniques is that tighter relaxations can be generated which can signicantly decrease the partitioning during branch-and-bound algorithm. PICO's parallel MILP branch-and-bound framework can be used in obtaining global solutions to nonconvex NLP problems. Current work under progress includes extension of PICO's branch-andbound capabilities to obtain global solutions to MINLP problems and implementing Outer-Approximation algorithms in parallel framework. Further, various heuristics for parallel variable bound contraction, parallel incumbent generation techniques are under consideration. Computational results from work in progress will be presented.

References

[1] M. A. Duran and I. E. Grossmann. An Outer-Approximation Algorithm for a Class of Mixed-Integer Nonlinear Programs. Mathematical Programming, 36:307-339, 1986.

[2] J. E. Falk and R. M. Soland. An Algorithm for Separable Nonconvex Programming Problems. Management Science, 15(9):550-569, 1969.

[3] R. Horst and H. Tuy. Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin, second edition, 1993.

[4] P. Kesavan, R. J. Allgor, E. P. Gatzke, and P. I. Barton. Outer Approximation Algorithms for Separable Nonconvex Mixed-Integer Nonlinear Programs. Mathematical Programming, 100:517- 535, 2004.

[5] G. P. McCormick. Computability of Global Solutions to Factorable Nonconvex Programs: Part I - Convex Underestimating Problems. Mathematical Programming, 10:147-175, 1976.

[6] I. Quesada and I. E. Grossmann. Global optimization algorithm for heat exchanger networks. Industrial and Engineering Chemistry Research, 32:487-499, 1993.

[7] E. M. B. Smith. On the Optimal Design of Continuous Processes. PhD thesis, Imperial College, London, 1996.

[8] Mohit Tawarmalani and Nikoloas V. Sahinidis. Global Optimization of Mixed-Integer Nonlinear Programs: A Theoretical and Computational Study. Mathematical Programming, October 2002.

[9] Andreas Wachter. An Interior Point Algorithm for Large-Scale Nonlinear Optimization with Applications in Process Engineering. PhD thesis, Carnegie Mellon University, January 2002.

[10] C. Bliek, P. Spellucci, L. N. Vicente, A. Neumaier, L. Granvilliers, E. Monfroy, F. Benhamou,E. Huens, P. V. Hentenryck, D. Sam-Haroud, and B. Faltings. COCONUT deliverable D1: Algorithms for solving nonlinear constrained and optimization problems: The state of art. Technical report, The COCONUT project. 2001.