Branch and bound method for solving non-convex integer non-linear multi-objective optimization problem?

Question

Following are the characteristics of my problem:

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

Decision variable: two integer variables ($X_1$ and $X_2$)

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

• Constraint 1: $ 0 \le X_1 \le A_1$

• Constraint 2: $ 0 \le X_2 \le A_2$

• Constraint 3: $ X_1 + X_2 \le A_3$

$A_1,A_2$ and $A_3$ are positive constant numbers.

Problem type: non-convex

Solution required: Global optimum

Can we solve this problem using brand-and-bound method?

Answer 1

Yes we can. Branch and bound can both deal the integer variables and with the potenial non convexities of the non-linear functions. Most branch and bound methods can also handle constraints. Depending on the solver you might need provide an relaxation for the bounding part.

However multi objective branch and bound methods are harder to come by, i am still not familiar with any solver that does it directly. I would consider an $\varepsilon$-constraint methodology to turn the multi objective problem into a series of single objective problems which can be solved to global optimality by standard MINLP solvers. In general the notion of solving a Multi-objective problem is ill defined for anything but linear multi-objective programs.

Answer 2

Julia Niebling and Gabriele Eichfelder recently published a paper on solving nonconvex multiobjective optimization problems using branch and bound. You can find the paper through the following link https://doi.org/10.1137/18M1169680