Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications. (English) Zbl 1031.90022

Nonconvex Optimization and Its Applications. 65. Dordrecht: Kluwer Academic Publishers. xxv, 475 p. (2002).
The book presents a theory, algorithms, and application results concerning an important topic of global optimization based on convex envelopes of nonlinear functions. The authors claim that “the aim of the book is to marry the advancements in solving nonlinear and integer programming models, and to develop new results in the general framework of mixed-integer nonlinear programs”. The approach developed by the authors concentrates on separable concave, univariate polynomial, multiplicative, mixed-integer semidefinate, general factorable integer programs. The problem specific methods are developed in a general branch-and-bound framework.
Chapter 1 is an introduction defining a mixed-integer nonlinear program, branch-and-bound approach and the related concepts. Chapter 2 presents basic methods of convexification, i.e. deriving convex envelopes of nonlinear functionals. In the chapters 3 and 4 a theory of convexification is presented and branch-and-bound type algorithms are developed for the rational, 0-1 hyperbolic, and factorable problems. It should be noted that the convexification approach developed by the authors enables the construction of closed form expressions for convex envelopes of nonlinear functions.
In Chapter 5 the domain reduction techniques are considered including bound tightening, domain contraction, and range reduction. An efficient branch-and-bound algorithm is developed in Chapter 6 based on rectangular partitioning and the notion of an ideal violation which is useful to improve the partitioning. Chapter 7 discusses the implementation of the proposed algorithms, including the questions on programming language, data storage, supported optimization software, evaluation of derivatives, etc. The chapters 8,9,10 presnt the results of application of the developed software to the problems of chemical engineering as well as to miscellaneous testing problems. The largest (90 pages) eleventh chapter is a tutorial describibg the use of the solver GAMS/BARON, i.e. the software developed by the authors and implemented as a package BARON interfaced with GAMS, a popular high level programming/modeling language. The Appendix contains GAMS models for pooling problems whose solution results are discussed in the book.


90C26 Nonconvex programming, global optimization
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C11 Mixed integer programming
90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut