Solving Multiobjective Mixed Integer Convex Optimization Problems

Abstract

Multiobjective mixed integer convex optimization refers to mathematical programming problems where more than one convex objective function needs to be optimized simultaneously and some of the variables are constrained to take integer values. We present a branch-and-bound method based on the use of properly defined lower bounds. We do not simply rely on convex relaxations, but we build linear outer approximations of the image set in an adaptive way. We are able to guarantee correctness in terms of detecting both the efficient and the nondominated set of multiobjective mixed integer convex problems according to a prescribed precision. As far as we know, the procedure we present is the first non-scalarization-based deterministic algorithm devised to handle this class of problems. Our numerical experiments show results on biobjective and triobjective mixed integer convex instances.