Skip to main content
SpringerLink
Log in
Birkhäuser

Relaxation and Decomposition Methods for Mixed Integer Nonlinear Programming

  • Book
  • © 2005

Overview

Authors:
  1. Ivo Nowak

    1. Berlin, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • Presents the first branch-cut-and-price algorithm for mixed integer nonlinear programming (MINLP)
  • Several new MINLP cuts based on semidefinite programming, interval-gradients and Bezier polynomials are proposed
  • A description of the MINLP solver LaGO, including numerical results for a wide range of applications, is provided

Part of the book series: International Series of Numerical Mathematics (ISNM, volume 152)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (14 chapters)

  1. Front Matter

    Pages i-xvi
    Download chapter PDF

  2. Basic Concepts

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Introduction

      • Ivo Nowak
      Pages 3-7

    3. Problem Formulations

      • Ivo Nowak
      Pages 9-19

    4. Convex and Lagrangian Relaxations

      • Ivo Nowak
      Pages 21-31

    5. Decomposition Methods

      • Ivo Nowak
      Pages 33-53

    6. Semidefinite Relaxations

      • Ivo Nowak
      Pages 55-71

    7. Convex Underestimators

      • Ivo Nowak
      Pages 73-81

    8. Cuts, Lower Bounds and Box Reduction

      • Ivo Nowak
      Pages 83-97

    9. Local and Global Optimality Criteria

      • Ivo Nowak
      Pages 99-111

    10. Adaptive Discretization of Infinite Dimensional MINLPs

      • Ivo Nowak
      Pages 113-118

  3. Algorithms

    1. Front Matter

      Pages 119-119
      Download chapter PDF

    2. Overview of Global Optimization Methods

      • Ivo Nowak
      Pages 121-128

    3. Deformation Heuristics

      • Ivo Nowak
      Pages 129-142

    4. Rounding, Partitioning and Lagrangian Heuristics

      • Ivo Nowak
      Pages 143-154

    5. Branch-Cut-and-Price Algorithms

      • Ivo Nowak
      Pages 155-179

    6. LaGO — An Object-Oriented Library for Solving MINLPs

      • Ivo Nowak
      Pages 181-186

  4. Back Matter

    Pages 187-213
    Download chapter PDF
Back to top

Keywords

About this book

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.

Reviews

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)

Authors and Affiliations

  • Berlin, Germany

    Ivo Nowak

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation