Mixed Integer Nonlinear Programming

Contents

Back to Integer Linear Programming or 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).

Software Resources

The NEOS Server offers a number of MINLP solvers. See the list here.

Test Problems

References

Optimization Online Integer Programming area (area covers both linear and nonlinear submissions)

  • Belotti, P., C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan. 2013. Mixed-Integer Nonlinear Optimization. Acta Numerica 22:1-131. DOI: http://dx.doi.org/10.1017/S0962492913000032
  • Leyffer, S. and Mahajan, A. 2011. Software For Nonlinearly Constrained Optimization. Wiley Encyclopedia of Operations Research and Management Science, John Wiley & Sons, New York.