Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming

ISBN-13: 9783764372385 / Angielski / Twarda / 2005 / 213 str.

Ivo Nowak

Opis

Nonlinearoptimizationproblemscontainingbothcontinuousanddiscretevariables are called mixed integer nonlinear programs (MINLP). Such problems arise in many ?elds, such as process industry, engineering design, communications, and ?nance. There is currently a huge gap between MINLP and mixed integer linear programming(MIP) solvertechnology.With a modernstate-of-the-artMIP solver itispossibletosolvemodelswithmillionsofvariablesandconstraints, whereasthe dimensionofsolvableMINLPsisoftenlimitedbyanumberthatissmallerbythree or four orders of magnitude. It is theoretically possible to approximate a general MINLP by a MIP with arbitrary precision. However, good MIP approximations are usually much larger than the original problem. Moreover, the approximation of nonlinear functions by piecewise linear functions can be di?cult and ti- consuming. In this book relaxation and decomposition methods for solving nonconvex structured MINLPs are proposed. In particular, a generic branch-cut-and-price (BCP) framework for MINLP is presented. BCP is the underlying concept in almost all modern MIP solvers. Providing a powerful decomposition framework for both sequential and parallel solvers, it made the success of the current MIP technology possible. So far generic BCP frameworks have been developed only for MIP, for example, COIN/BCP (IBM, 2003) andABACUS (OREAS GmbH, 1999). In order to generalize MIP-BCP to MINLP-BCP, the following points have to be taken into account: A given (sparse) MINLP is reformulated as a block-separable program with linear coupling constraints.The block structure makes it possible to generate Lagrangian cuts and to apply Lagrangian heuristics. In order to facilitate the generation of polyhedral relaxations, nonlinear c- vex relaxations are constructed. The MINLP separation and pricing subproblems for generating cuts and columns are solved with specialized MINLP solvers."

Recenzje

From the reviews:

"In his monograph, the author treats mixed integer nonlinear programs (MINLPs), that is nonlinear optimization problems containing both continuous and discrete variables. ... This self-contained monograph is rich in content, provides the reader with a wealth of information, and motivates his or her further interest in the subject. The book offers fairly comprehensive description of the MINLP theory and algorithms." (Jan Chleboun, Applications of Mathematics, Issue 3, 2012)

Spis treści

Basic Concepts.- Problem Formulations.- Convex and Lagrangian Relaxations.- Decomposition Methods.- Semidefinite Relaxations.- Convex Underestimators.- Cuts, Lower Bounds and Box Reduction.- Local and Global Optimality Criteria.- Adaptive Discretization of Infinite Dimensional MINLPs.- Algorithms.- Overview of Global Optimization Methods.- Deformation Heuristics.- Rounding, Partitioning and Lagrangian Heuristics.- Branch-Cut-and-Price Algorithms.- LaGO — An Object-Oriented Library for Solving MINLPs.

Blurb

This book presents a comprehensive description of theory, algorithms and software for solving nonconvex mixed integer nonlinear programs (MINLP). The main focus is on deterministic global optimization methods, which play a very important role in integer linear programming, and are used only recently in MINLP.

The presented material consists of two parts. The first part describes basic optimization tools, such as block-separable reformulations, convex and Lagrangian relaxations, decomposition methods and global optimality criteria. Some of these results are presented here for the first time.

The second part is devoted to algorithms. Starting with a short overview on existing methods, deformation, rounding, partitioning and Lagrangian heuristics, and a branch-cut-and-price algorithm are presented. The algorithms are implemented as part of an object-oriented library, called LaGO. Numerical results on several mixed integer nonlinear programs are reported to show abilities and limits of the proposed solution methods.

The book contains many illustrations and an up-to-date bibliography. Because of the emphasis on practical methods, as well as the introduction into the basic theory, it is accessible to a wide audience and can be used both as a research as well as a graduate text.