What methods are used to solve multi-objective optimization problem with non-linear objective functions and integer decision variables?

Question

Case 1: NLP

When either the objective function or at least one of the constraints or both are non-linear it is a NLP. We use generalized reduced gradient or Quadratic Programming to solve NLP. However, NLP also requires the decision variables to be continuous

Case 2: MINLP

When either the objective function and/or at least one constraint is non-linear it is a MINLP. We use outer approximation or branch and bound to solve MINLP. However, MINLP also requires the decision variables to be both continuous and discrete(binary/integer).

Case 3: My Case

Objective function: two non-linear functions and one linear function

Decision variable: two integer variables (Bounded)

Constraint: three linear constraint (two bounding constraint and one relationship constraint)

Problem type: non-convex

Solution required: Global optimum

Will this problem require conversion to NLP or MINLP to implement the above solution methods? What exact multi-objective optimization methods can be used for my case?

Also, if the problem is converted from INLP to NLP by relaxing the decision variables to real values what exact multi-objective optimization methods can be used?

Answer 1

Disclaimer: One might want to look for a reformulation or a special structure to apply mathematical tools to find optimal in the feasible set. I am assuming you're already past the possibility that your problem case could be reformulated as a MILP/LP/QP etc.

So, with the problem on hand, we're dealing a case where we cannot have a reformulation. Whatever I understood from your problem description is that the problem is non-convex, non-linear, and constrained. But turns out you have just two bounded variables say $x_1$ and $x_2$, We'll take advantage of this fact.

My following approach is a brute force but this shall be a quick solution. Given discrete domains for $x_1$ and $x_2$ as follows, $$x_1 \in \{x_1^1, x_1^2, \cdots, x_1^n\}$$ $$x_2 \in \{x_2^1, x_2^2, \cdots, x_2^m\}$$

Some Non-Linear Objective Function: $f(x_1,x_2)$

Constraints: $(x_1^i,x_2^j) \in S : ~ i \in \{1,\cdots, n\}, j \in \{1,\cdots, m\} $

Determine Global Optimal Solution: $\underset{x_1,x_2}{\mathrm{argmin}}{\{f(x_1^i,x_2^j) : ~ i,j \in S\}}$

Observe that, the complexity of brute force is still O(m*n) ie. polynomial in terms of your input domains.

EDIT: You also mentioned your problem is multiobjective, so you'll have an added advantage with this approach. You could even score each solution by computing the objectives separately rather than having one single objective function.

PS: @community I agree, This is a bad solution if the no. variables increase or feasible region is too big. Given the size and the information available, this could be one of the feasible approach. [Read Disclaimer]