Abstract

Multiobjective mixed integer nonlinear programming (MOMINLP) represents a powerful tool to model real-world decision problems, as applied problems often reveal multiple, conflicting goals to be optimized and 0-1 or integer variables are needed to model logical relationships or discrete quantities. Solving MOMINLPs means to detect the set of efficient solutions of the problem, i.e. those points such that none of the objective functions can be improved in value without degrading some of the other objective values.

An efficient integer assignment for MOMINLPs is a fixing of the integer variables so that there exists an efficient point of the problem with exactly that fixing. Depending on the instance, solution algorithms for MOMINLPs may need to detect a large number of efficient integer assignments, possibly all integer feasible assignments, so that a full enumeration cannot be avoided. This shows a big difference with respect to the single objective case and a big challenge in terms of algorithms development.

In this talk, we present a branch-and-bound method for multiobjective mixed-integer convex quadratic programs that computes a superset of efficient integer assignments using outer approximations of the upper image set of continuous relaxations. These outer approximations are obtained addressing the dual formulations of specific subproblems where the values of certain integer variables are fixed. The devised pruning conditions and a tailored preprocessing phase allow a fast enumeration of the nodes. Despite the fact that we do not require any boundedness of the feasible set, we are able to prove that the method stops after having explored a finite number of nodes. Numerical experiments on instances with two, three, and four objectives are presented.