Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming

✍ Scribed by Ivo Nowak (auth.)

• Publisher: Birkhäuser Basel
• Year: 2005
• Tongue: English
• Leaves: 214
• Series: International Series of Numerical Mathematics 152
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Front Matter....Pages 1-1
Introduction....Pages 3-7
Problem Formulations....Pages 9-19
Convex and Lagrangian Relaxations....Pages 21-31
Decomposition Methods....Pages 33-53
Semidefinite Relaxations....Pages 55-71
Convex Underestimators....Pages 73-81
Cuts, Lower Bounds and Box Reduction....Pages 83-97
Local and Global Optimality Criteria....Pages 99-111
Adaptive Discretization of Infinite Dimensional MINLPs....Pages 113-118
Front Matter....Pages 119-119
Overview of Global Optimization Methods....Pages 121-128
Deformation Heuristics....Pages 129-142
Rounding, Partitioning and Lagrangian Heuristics....Pages 143-154
Branch-Cut-and-Price Algorithms....Pages 155-179
LaGO — An Object-Oriented Library for Solving MINLPs....Pages 181-186

✦ Subjects

Math Applications in Computer Science; Applications of Mathematics; Algorithms; Computational Science and Engineering; Programming Techniques