Mixed Integer Nonlinear Optimization

Many real-world problems lead to mixed-integer non-linear optimization problems (MINLP) that need to be solved to global optimality. While research efforts over the past fifty years have led to a development of linear integer programming as a mature discipline of mathematical optimization, such a level of maturity has not been reached when one considers nonlinear systems subject to integrality requirements for the variables. To develop new mathematical methods for the global optimization of MINLPs, theoretical results that allow to construct strong mixed-integer convex relaxations for MINLPs are needed. In particular, we focus on identifying combinatorial substructures induced by integral variables that can be exploited to improve global optimization algorithms, and on bound tightening techniques.

People

• Robert Weismantel
• Dennis Michaels
• Martin Ballerstein

Ongoing projects

Mixed-Integer Nonlinear Optimization with Applications in Chemical Engineering (M. Ballerstein, D. Michaels, R. Weismantel)

A general approach in global optimization is to combine local search methods with algorithms computing strong globally valid bounds on the optimal function value of the underlying MINLP. This is achieved by constructing and solving a hierarchy of (mixed-integer) convex relaxations. For this, the non-linearities involved in the model description are typically replaced by convex under- and concave overestimators. A key step to obtain reasonable bounds is to build strong convex relaxations. The tightest convex under- and the tightest concave overestimator are called the convex and the convex envelope of a function, and are only known explicitly for a few special classes of functions. It is the goal of this research project to develop new mathematical methods for the global optimization of MINLPs. The usefulness of the developed algorithms are demonstrated by considering MINLPs arising in the context of the Collaborative Research Centre SFB/TR 63 "InPROMPT - Integrated Chemical Processes in Liquid Multiphase Systems" funded by the German Research Foundation (DFG).