Introduction to Mathematical Optimisation for MINLPs

Overview of Mathematical Optimisation

Mathematical optimisation (also known as mathematical programming) describes the mathematical representation of real-world scenarios in the form of optimisation problems. These techniques can be applied in a range of fields from engineering and supply chain management to finance and economics.

Mathematical programming aims to find the best possible solution to the problem. This type of problem consists of a collection of variables, an objective function which is to be maximised or minimised, and a set of constraints which the variables are subject to. These constraints are represented by equations (that can be equalities or inequalities) which can restrict the possible values of the variables.

Mathematical Programming

There are different types of optimisation problems. The hardest of these is Mixed-integer Nonlinear Programming (MINLP) as it consists of a nonlinear objective function and/or constraints where the variables can be both discrete and continuous. In order to explain this type of optimisation problem, let’s begin with the basics of mathematical programming.

In mathematical programming, we aim to either maximise or minimise an objective function to find the optimal solution possibly subject to some constraints. The difficulty of this task depends on the functional forms of these functions. For example, consider the following objective functions:

\(C: f(x) = (x - 1)^{2} +1\)
\(NC: f(x) = x^{4}-10x^{3}+34x^{2}-47x+30\)

Let’s assume that we want to minimise \(C\) and \(NC\). Figure 1a and Figure 1b show a graph of \(C\) and \(NC\) respectively.

convex graph

Figure 1a
non-convex graph

Figure 1b

The problem represented by \(C\) is convex and therefore any local minimum is a global minimum \((x^*, y^*)\) in Figure 1a. Whereas the problem represented by \(NC\) (Figure 1b) is non-convex and has two local minimums \((x_{lm}, y_{lm})\) and \((x^*, y^*)\) of which only one is the global minimum \((x^*, y^*)\).

Very often, an objective function is maximised or minimised subject to certain constraints. These constraints produce a feasible region which contains all feasible solutions (including the optimal solution).

convex graph

Figure 2a
non-convex graph

Figure 2b

Figure 2a shows an example of a feasible region which is convex and has been formed by linear constraints. Whereas Figure 2b provides an example of a non-convex feasible region formed by nonlinear constraints.

The nature of both the objective function and the constraints determine the type of mathematical programming problem as well as the level of difficulty in finding an optimal solution. Let’s now go through the different types of optimisation problems. We will focus on the feasible regions given by the constraints but the basic idea can also be applied to the objective function.

Linear Programming (LP)

LPs are problems that consist of a linear objective function and constraints. In mathematical programming, this is the easiest type of optimisation problem to solve. Due to its linear nature, LPs are always convex.
Let’s look at a simple example: \begin{equation} \begin{aligned} \min \quad & x - y \\ \text {s.t } \quad & x \leq 3 \\ & x + y \geq 3 \\ & y \leq 3 \\ & x \geq 0 \\ & y \geq 0 \\ & x \in R \\ & y \in R \end{aligned} \end{equation}
Linear Programming
Figure 3

The feasible region is shown by the blue area in Figure 3. This is the region which contains the feasible solution set i.e all possible solutions which satisfy the constraints. In this example, we can assume that the variables, \(x\) and \(y\), are continuous as no integer values are stated. Also notice that in this case, \(x \geq 0\) and \(y \geq 0\) are redundant constraints since they can be removed without changing the current feasible region.

Nonlinear Programming (NLP)

NLPs are optimisation problems where the objective function and/or some of the constraints are now nonlinear. These types of problems reflect the fact that some features of real-world scenarios cannot be represented by linear functions.
\begin{equation} \begin{aligned} \min \quad & x^3 - y \\ \textrm{s.t. } \quad & y \ge 6 (x -1.5)^{2} +1 \\ & y \le 3 \\ & x \le 3 \\ & x + y \ge 3.5 \\ & x \geq 0 \\ & y \geq 0 \\ & x \in R \\ & y \in R \\ \end{aligned} \end{equation}
Nonlinear Programming
Figure 4

Introducing nonlinearity has made the problem more complex. Both the objective function and one of the constraints now contain a nonlinear component. Figure 4 shows that the shape of the feasible region has changed, from what it was in Figure 3. This is due to the addition of the nonlinear constraint. The size of the feasible solution set has, effectively, been reduced.

Mixed-integer Linear Programming (MILP)

MILPs is an area of optimisation where some variables are integers while others are continuous. If we come back to the original LP and now assume that \(x\) is a binary variable e.g. \(x \in \{1, 2\}\), the optimisation problem will now look as follows:
\begin{equation} \begin{aligned} \min \quad & x - y \\ \textrm{s.t.} \quad & x \leq 3 \\ & x + y \ge 3.5 \\ & y \leq 3 \\ & x \geq 0 \\ & y \geq 0 \\ & x \in \{1, 2\} \\ & y \in R \\ \end{aligned} \end{equation}
Mixed-integer Linear Programming
Figure 5

Figure 5 shows that the feasible solution set can only have values of \(x\) which are 1 and 2 that satisfy all other constraints.This is indicated by the thicker blue lines in Figure 5.

Mixed-integer Nonlinear Programming (MINLP)

As we mentioned above, MINLPs are the most difficult type of optimisation problem to solve. This is Octeract Engine’s area of expertise. MINLPs combine nonlinearity with mixed-integers which introduces significant complexity to a problem. Often, these types of optimisation problems most accurately represent real-world scenarios. For example, adding the binary constraint \(x \in \{1,2\}\) to the previous NLP, we obtain
\begin{equation} \begin{aligned} \min \quad & x^3 - y \\ \textrm {s.t } \quad & y \ge 6 (x -1.5)^{2} +1 \\ & x + y \ge 3 \\ & y \leq 3 \\ & x \leq 3 \\ & x \geq 0 \\ & y \geq 0 \\ & x \in \{1, 2\} \\ & y \in R \\ \end{aligned} \end{equation}
Mixed-integer Nonlinear Programming
Figure 6

The addition of a nonlinear constraint has reduced the feasible region from what it was in Figure 5. This constraint now cuts \(y\) values for \(x = 2\) in the feasible region.

Octeract Engine specialises in handling MINLPs which, as shown above, is the most complex type of optimisation problem. The Engine is also well-equipped to deal with any of the aforementioned problems. One of the most used tools in the Octeract Engine toolbox is the branch and bound algorithm. This is the next topic we will cover.

Was this helpful?
Please make sure you fill the comments section before sending.

Thank you for your comments.
Please contact us if you need any further support.