MINLP Mixed integer nonlinear programming

Last updated on May 2, 2023

Mixed integer nonlinear programming (MINLP) is a type of optimization problem that involves both continuous and integer variables, as well as nonlinear objective functions and constraints. MINLP problems are often encountered in many fields, such as engineering, economics, and finance, where decisions must be made under uncertainty and subject to various constraints.

In this article, we will explain what MINLP is, how it differs from other types of optimization problems, and what methods can be used to solve it.

What is MINLP?

MINLP can be formulated as follows:

minimize f(x,y) subject to g(x,y) <= 0 h(x,y) = 0 x in R^n, y in Z^m

where f(x,y) is a nonlinear objective function, g(x,y) are nonlinear inequality constraints, h(x,y) are nonlinear equality constraints, x is a vector of continuous variables, y is a vector of integer variables, R^n is the n-dimensional Euclidean space, and Z^m is the m-dimensional integer lattice.

The variables in the problem are split into two types: continuous variables x and integer variables y. The objective function and constraints are nonlinear functions of both types of variables.

The objective function is a function of the variables that we want to minimize. The constraints are conditions that must be satisfied in order for the problem to be feasible. The inequality constraints impose limits on the values of the variables, while the equality constraints impose conditions that must be met exactly.

The variables in the problem can be either continuous or integer. Continuous variables can take on any value within a specified range, while integer variables can only take on integer values.

How is MINLP different from other types of optimization problems?

MINLP is a challenging optimization problem due to its nonlinear objective function and constraints, as well as the presence of integer variables. This makes it different from other types of optimization problems, such as linear programming (LP), quadratic programming (QP), and mixed-integer linear programming (MILP).

In LP, the objective function and constraints are linear functions of the variables, and all variables are continuous. In QP, the objective function is a quadratic function of the variables, and the constraints are linear functions of the variables. In MILP, the variables are split into two types: continuous variables and integer variables, but both the objective function and constraints are linear functions of the variables.

MINLP, on the other hand, involves nonlinear functions of both continuous and integer variables. The presence of integer variables makes the problem much more difficult to solve than LP, QP, or MILP.

Methods to solve MINLP

There are several methods that can be used to solve MINLP, including branch and bound, outer approximation, and mixed-integer convex optimization. Each method has its strengths and weaknesses, and the choice of method depends on the specific problem being solved.

Branch and bound

Branch and bound is a widely used algorithm for solving MINLP problems. The basic idea behind branch and bound is to split the problem into a set of smaller subproblems, solve each subproblem, and then combine the solutions to obtain a global solution.

The algorithm works as follows:

Divide the problem into a set of subproblems by adding integer constraints to the problem.
Solve each subproblem using a nonlinear solver to obtain a lower bound on the objective function.
If the lower bound is greater than the current best upper bound, prune the subproblem and move on to the next subproblem.
If the lower bound is less than the current best upper bound, update the best upper bound and move on to the next subproblem.
Repeat steps 2-4 until all subproblems have been solved.

Branch and bound can be a very effective method for solving MINLP problems , especially when the problem is not too large or complex. However, as the problem size increases, the number of subproblems grows exponentially, and the algorithm can become computationally expensive and impractical.

Outer approximation

Outer approximation is another method for solving MINLP problems. The basic idea behind outer approximation is to linearize the nonlinear functions in the problem and then solve a series of linear programming (LP) problems to obtain a sequence of lower bounds on the objective function.

The algorithm works as follows:

Linearize the nonlinear functions in the problem to obtain a set of linear constraints.
Solve an LP relaxation of the problem, which is obtained by dropping the integer constraints, to obtain a lower bound on the objective function.
Add a cut to the problem, which is a linear constraint that eliminates a solution that violates a nonlinear constraint.
Repeat steps 2-3 until the lower bound converges to the optimal solution.

Outer approximation can be a very effective method for solving MINLP problems, especially when the nonlinear functions in the problem are not too complex. However, as the complexity of the nonlinear functions increases, the number of cuts that need to be added to the problem can become very large, and the algorithm can become computationally expensive.

Mixed-integer convex optimization

Mixed-integer convex optimization is a relatively new method for solving MINLP problems. The basic idea behind mixed-integer convex optimization is to relax the integer variables to continuous variables and then solve a series of convex optimization problems to obtain a sequence of lower bounds on the objective function.

The algorithm works as follows:

Relax the integer variables to continuous variables to obtain a convex optimization problem.
Solve the convex optimization problem to obtain a lower bound on the objective function.
Use a cutting plane algorithm to add linear constraints to the problem that eliminate solutions that violate nonlinear constraints.
If a feasible solution is found, add a branch-and-bound algorithm to the problem to refine the solution and obtain a global optimum.

Mixed-integer convex optimization can be a very effective method for solving MINLP problems, especially when the nonlinear functions in the problem are convex. However, as the complexity of the nonlinear functions increases, the algorithm can become computationally expensive.

Conclusion

Mixed integer nonlinear programming (MINLP) is a challenging optimization problem that involves both continuous and integer variables, as well as nonlinear objective functions and constraints. MINLP problems are encountered in many fields, such as engineering, economics, and finance, where decisions must be made under uncertainty and subject to various constraints.