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. Examples can be found in many areas including:

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

The mixed integer nonlinear solver h02da, in Chapter H of the Library, 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.)