Mixed-Integer Nonlinear Programming

Basic Concepts

Mixed integer nonlinear programming (MINLP) refers to optimization problems with continuous and discrete variables and nonlinear functions in the objective function and/or the constraints. MINLPs arise in applications in a wide range of fields, including chemical engineering, finance, and manufacturing. The general form of a MINLP is

\[\begin{array}{lllll}
\mbox{min} & f(x,y) & & & \\
\mbox{s.t.} & c_i(x,y) & = & 0 & \forall i \in E \\
& c_i(x,y) & \leq & 0 & \forall i \in I \\
& x & \in & X & \\
& y & \in & Y & \mbox{integer}
\end{array}
\] where each \(c_i(x,y) \,\) is a mapping from \(R^n \,\) to \(R \,\), and \(E \,\) and \(I \,\) are index sets for equality and inequality constraints, respectively. Typically, the functions \(f\) and \(c_i\) have some smoothness properties, i.e., once or twice continuously differentiable.

Software developed for MINLP has generally followed two approaches:

  • Outer Approximation/Generalized Bender’s Decomposition: These algorithms alternate between solving a mixed-integer LP master problem and nonlinear programming subproblems.
  • Branch-and-Bound: Branch-and-bound methods for mixed-integer LP can be extended to MINLP with a number of tricks added to improve their performance.

For a recent survey of MINLP applications, models, and solution methods, see Belotti et al. (2013).

Test Problems
  • MacMINLP, a collection of MINLP test problems in AMPL
  • MINLPLib, a collection of MINLP test problems
References