Quadratic Convex Reformulations for MultiObjective Binary Quadratic Programming
1 : Dipartimento di Ingegneria dell'Informazione [Firenze]
2 : Laboratoire d'Informatique de Paris-Nord
Centre National de la Recherche Scientifique, Université Sorbonne Paris nord, Centre National de la Recherche Scientifique : UMR7030
Multiobjective binary quadratic programming refers to optimization problems involving multiple quadratic - potentially non-convex - objective functions and a feasible set that includes binary constraints on the variables. In this paper, we extend the well-established Quadratic Convex Reformulation technique, originally developed for single-objective binary quadratic programs, to the multiobjective setting. We propose a branch-and-bound algorithm where lower bound sets are derived from properly defined quadratic convex subproblems. Computational experiments on multiobjective k-item Quadratic Knapsack and multiobjective Max-Cut instances demonstrate the effectiveness of our approach.

