Séminaire

Date : 2 juillet 2026 14:00 - Salle :Salle A104 Branch-and-Bound, Convexification and Dominance Inequalities for Multi-Objective Binary Quadratic Problems Lucas Letocart - LIPN – Université Sorbonne Paris Nord

Multi-objective binary quadratic programming refers to optimization problems involving several quadratic, potentially non-convex, objective functions together with binary constraints on the variables.

In this talk, we first focus on extending the well-established Quadratic Convex Reformulation technique, originally developed for single-objective binary quadratic programs, to the multi-objective setting. A branch-and-bound algorithm whose lower bound sets are obtained from suitably defined quadratic convex subproblems is presented.

We then introduce a new polyhedral approach for multi-objective combinatorial optimization problems. The main idea is to eliminate locally dominated solutions while approaching the convex hull of locally non-dominated solutions. The inequalities used to separate locally dominated solutions are called dominance inequalities.

Originally developed for single-objective problems, dominance inequalities simultaneously improve relaxation bounds and reduce redundant regions of the feasible set. We extend these inequalities to a generic multi-objective framework and show theoretically that they can be tight on the nondominated frontiers of the feasible polytope in the criteria space.

As a consequence, multi-objective dominance inequalities can be integrated into both criteria-space search algorithms and decision-space search algorithms. Computational experiments on multi-objective k-item Quadratic Knapsack and multi-objective Max-Cut instances demonstrate the effectiveness of these approaches.