ROADEF 2026>
Quadratic Convex Reformulations for MultiObjective Binary Quadratic Programming
Marianna De Santis  1@  , Lucas Létocart  2@  , Yue Zhang  2@  
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.


Chargement... Chargement...