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

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?

• What do you understand under "global optimum" of a multi-objective problem, this notion is ill-defined. Oct 10 '21 at 12:26
• Are your integer variables bounded?
– Sune
Oct 11 '21 at 7:06
• Yes. It is bounded. Oct 11 '21 at 15:27

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]

• If the decision variables can be relaxed as real, then the problem can be non-convex NLP. So, can we use successive quadratic programming or QP or Reduced gradient method to get global optimization results? Oct 12 '21 at 13:39
• SQP/reduced gradient are local methods they can not provide any global guarantees with regard to a local minima that they found Oct 12 '21 at 23:24