EUROPT 2025
Abstract Submission

206. Multi-Objective branch-and-bound algorithms for binary (non-convex) quadratic problems

Invited abstract in session WB-10: Global Multi-Objective Optimization, stream Multiobjective and Vector Optimization.

Wednesday, 10:30-12:30
Room: B100/8011

Authors (first author is the speaker)

1. Yue Zhang
LIPN UMR CNRS 7030, Université Sorbonne Paris Nord
2. Marianna De Santis
University of Florence
3. Pierre Fouilhoux
LIPN UMR CNRS 7030, Université Sorbonne Paris Nord
4. Lucas Létocart
LIPN UMR CNRS 7030, Université Sorbonne Paris Nord

Abstract

We propose the first exact generic branch-and-bound framework for Multi-Objective Binary Quadratic programs (MObBQ). The MObBQ framework explores the decision space dividing the original problem into subproblems by variable fixing. The efficiency of the MObBQ approach is to repeatedly solve the easier relaxed problems and enumerate the complete non-dominated set by branching. Such a fully implicit enumeration stops until all nodes/subproblems are evaluated, where constructing valid lower and upper bound sets remains an essential ingredient. In this work, we propose different strategies for computing lower bound sets using the Quadratic Convex Reformulation techniques. The use of a preprocessing phase allows a significant time saving. We prove both theoretically and numerically the validity of our algorithm. Tests on bi- and tri-objectives instances from different multi-objective combinatorial quadratic problems show the effectiveness of the approach, able to outperform the epsilon-constraint method on bi-objective quadratic maxcut instances strongly.

Keywords

Status: accepted

Back to the list of papers