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