SHORT COURSE

I. Title:

A Practical Guide to Mixed Integer Nonlinear Programming

II. Short-Course Organizers:

Sven Leyffer, Argonne National Laboratory,
[email protected]
Jeff Linderoth, Lehigh University
[email protected]

III. Associated SIAM Conference:

Eighth SIAM Conference on Optimization

IV. Rationale:

Many optimization problems involve both nonlinear constraints to model
physical phenomena and integer variables to model design decisions,
giving rise to mixed integer nonlinear programming (MINLP)
problems. The efficient solution of large MINLP problems remains an
open question whose solution requires expertise in both integer and
nonlinear optimization. This course brings together experts in
nonlinear programming and mixed integer programming to chart the state
of the art in MINLP from the view of these two fields.

V. Instructors:

Sven Leyffer is a scientist at Argonne National Laboratory. He has worked on integer nonlinear optimization, nonlinear optimization, and optimization problems with equilibrium constraints.

Jeff Linderoth is an assistant professor at Lehigh University. His interests include mixed integer linear optimization, and stochastic programming.

VI. Course Description:

The course will start by considering examples of MINLPs, showing how they arise in a variety of application areas.  Through the applications, the students will be introduced to a variety of modeling techniques for MINLP.

The second part reviews classical methods for MINLP, such as nonlinear branch-and-bound (BB), and decomposition schemes, such as outer approximation and Benders decomposition. We show how these methods can be improved by using inexact solves and hybrid approaches.

The third part of the course provides an introduction to more recent developments in MINLP, including the extension of cutting planes from MILP to MINLP, direct disjunctive formulations, and underestimation methods for nonconvex problems.

The final part of the course discusses software for MINLP and implementation details of the various available packages, including comparative computational results. We also present a parallel BB approach that solves large MINLP on a computational grid.

VII. Level of the Material:

The target audience is both graduate students and researchers working in nonlinear programming and mixed integer optimization. The course does not require any knowledge beyond an undergraduate course in nonlinear optimization and some familiarity with AMPL.

Course Outline

Introduction, Applications, and Formulations:       (1 hour)

• Mixed integer nonlinear programming: Problem classifications
• Applications:  Finance, networks, engineering design
• Modeling with integer variables
• Special modeling considerations: convexification, linearization, special ordered sets

Methods for Convex MINLP:        (2 hours)

• Branch-and-bound (BB): variable & node selection
• Outer approximation and Benders decomposition
• Hybrid methods: LP/NLP-based BB
• Sequential quadratic programming and BB
• Outer approximation heuristics for nonconvex MINLP

Advanced Methods for MINLP:       (2 hours)

• Cutting planes for MILP
• Branch-and-cut for MINLP
• Disjunctive MINLP
• Underestimators for nonconvex MINLP
• BARON approach
• MINOPT and alpha-BB

Implementation and Software:        (1.5 hours)

• Warm starts for active set methods
• Detecting infeasibility; degeneracy
• MINLP & SBB on the NEOS server
• BARON & DICOPT++ under GAMS
• Model problem libraries: MINLPworld & MacMINLP
• Parallel BB and grid computing