OPTI Toolbox

Problem Definition

An MINLP has the following form:

Where f is a scalar function containing the nonlinear objective function, which is subject to the following constraints:

Linear Inequalities*

A is a m x n sparse matrix, b is a m x 1 vector.

Linear Equalities*

A_eq is a k x n sparse matrix, b_eq is a k x 1 vector.

Decision Variable Bounds

l_b and u_b are n x 1 vectors, where -inf or inf indicate an unbounded lower or upper bound, respectively.

Nonlinear Inequalities*

c is a u x 1 vector of functions containing nonlinear inequality constraints, d is a u x 1 vector

Nonlinear Equalities*

c_eq is a v x 1 vector of functions containing nonlinear equality constraints, d_eq is a v x 1 vector

Integer Constraints

x_i are decision variables which must be an integer number (..-2, -1, 0, 1, 2..).

Binary Constraints

x_j are decision variables which must be a binary number (0,1), where i ≠ j.

The goal is to minimize the objective function by selecting a value of x that also satisfies all constraints.

*Your problem description will either use Linear / Nonlinear Inequalties and Linear / Nonlinear Equalities OR Linear / Nonlinear Row Constraints. See the constraint information page.

Note an MINLP is created in the same way as an NLP, except some variables are defined to take discrete (integer) values only. It is recommened you complete reading the NLP section before reading the remainder of the section.

Example 1: Convex MINLP

Before you read any further, have another think about the term "Convex MINLP". By introducing integer constraints, the problem is now non-convex. So how can an MINLP be convex? Well, technically it's not. However the relaxed problem (integer constraints removed) is convex, thus this is typically what is meant by "Convex MINLP". Just remember it really is technically incorrect!

Anyway, consider the following MINLP:

This problem contains a linear objective, one quadratic constraint and two linear constraints. While it could be formulated as a MIQCQP, we will keep it as a MINLP for this example.

The problem is entered into MATLAB as follows:

Note we have opted to split the constraints into linear and nonlinear types. While the MINLP solver will call them all in a single nonlinear callback, OPTI will recognise two as being linear, and pass this linear information to the solver to use while solving.

To solve the problem:

Using BONMIN (the default MINLP solver), this problem should be solved at the root node, requiring less than 1/4 of a second to solve. However remember this is a tiny problem, real MINLPs can take hours or days to solve.

Example 2: Non-Convex MINLP

Like IPOPT, BONMIN will only find local solutions to non-convex problems, thus for non-convex MINLPs we have to use a different solver. Rastrigin's function is an example of a test non-convex NLP:

To make it more interesting, we are going to constrain x₁ to be an integer variable, within a curved region of the function:

This can be entered into MATLAB as follows:

For this problem we are going to use NOMAD to solve it. NOMAD is an excellent derivative free, global MINLP solver which continues to surprise us with it's ability to find solutions to difficult, real world problems.

NOMAD is used to solve the problem as follows:

NOMAD should return in less than 1/4 of a second with a integer optimal solution. Note we have also enabled iteration display, allowing us to view solver progress while it is solving. On large problems this is especially useful, to ensure progress is being made!