18.02.18 - 23.02.18, Seminar 18081

Designing and Implementing Algorithms for Mixed-Integer Nonlinear Optimization

The following text appeared on our web pages prior to the seminar, and was included as part of the invitation.


Mathematical models for optimal decisions often require both nonlinear and discrete components. These mixed-integer nonlinear programs (MINLP) may be used to optimize the energy use of large industrial plants, integrate renewable sources into energy networks, design biological and biomedical systems, and address numerous other applications of societal importance. The first MINLP algorithms and software were designed by application engineers. While these efforts initially proved useful, scientists, engineers, and practitioners have realized that a transformational shift in technology will be required for MINLP to achieve its full potential. MINLP has transitioned to a forefront position in computer science, with researchers actively developing MINLP theory, algorithms, and implementations. Even with their concerted effort, algorithms and available software are often unable to solve practically-sized instances of these important models. Current obstacles include characterizing the computability boundary, effectively exploiting known optimization technologies for specialized classes of MINLP, and effectively using logical formulas holistically throughout algorithms.

This seminar aims to address this mismatch between natural optimization models for important scientific problems and practical optimization solvers for their solution. A significant seminar outcome will be the accelerated development of powerful new solver technology for mixed-integer nonlinear programs.

By bringing together experts in both theory and implementation, this seminar will energize efforts making MINLP as ubiquitous a paradigm for both modeling and solving important decision problems as mixed-integer linear programming (MIP) and nonlinear programming (NLP) have become in recent years. In particular, we plan to highlight:

  • MINLP Solver Software. Early in the seminar, the main developers of MINLP software packages will outline the current state of their software. This will serve as a needs analysis for the community to identify crucial areas for future development. We will also dedicate one or two sessions to discuss best practices for conducting scientifically-meaningful computational experiments in MINLP.
  • Intersecting Mixed-Integer & Nonlinear Programming. MINLP is a superset of both MIP and NLP, so we aim to leverage the best methods from both.
  • Complexity & Convergence Analysis. Studying complexity unpacks the border of tractability in MINLP. Convergence analysis helps motivate which algorithmic components to develop.
  • Submodular Optimization. Some important MINLP problems reduce to maximizing submodular functions.
  • Driving Applications. Applications experts, e.g. in petrochemicals, manufacturing, and gas networks, will offer their perspectives on what practitioners need from MINLP solvers.

Creative Commons BY 3.0 Unported license
Pierre Bonami, Ambros M. Gleixner, Jeff Linderoth, and Ruth Misener