Mixed Integer Nonlinear Programming (MINLP)

Mixed integer programming problems are defined as those where some or all of the decision variables are only allowed to be integers. This is typically required in a range of real world applications in allocation and planning problems where the discrete variables represent quantities, such as the number of individual shares to be held or the number of pipelines need or the number of oil-spill cleaning locations to be deployed, and require integer values for the solution.

Many applications lead to mathematical models which can be written as Mixed Integer Linear Programming (MILP) or as Mixed-Integer Quadratic Programming (MIQP) problems – that is problems with linear constraints and with linear or with quadratic objective functions. However for some this might not be enough to capture the key characteristics of a real problem. In these cases fully nonlinear models are needed - so a solver has to handle the combinatorial difficulty of optimizing over discrete variable sets together with the issues of handling nonlinear functions.

Such models, where a MINLP solver is useful, arise in scientific, engineering, and financial applications. Example can be found in many areas including:

  • portfolio optimization
  • design of distribution networks
  • flight path optimization
  • optimal response to catastrophic oil spills
  • protein folding

At Mark 25 we introduce a new mixed integer nonlinear solver, h02da, to Chapter H of the Library.

The new solver is based on research by Prof. Klaus Schittkowski of University of Bayreuth. The underlying algorithm is a modified Sequential quadratic programming (SQP) stabilised by using trust regions. It can deal with both convex and nonconvex problems and problems with possibly expensive function evaluations. In addition, it is not assumed that the mixed integer problem has to be relaxable; the function evaluations are requested only at integral points. This may be considered as a distinctive feature of the solver since the usual approaches rely on the relaxation of the discrete variables.

(Footnote: If optimization solvers are required for mathematical models that involve only continuous variables then the algorithms in Chapters E04 or E05 of the NAG Library should be preferred.)