On the Lagrangian Relaxation in a Bi-Objective Branch and Bound Algorithm

Summarise with VIRAT
Authors: Mariagrazia Cairo, Lavinia Amorosi, Paolo Dell’Olmo, Serpil Sayın
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

Branch-and-bound algorithms are among the most effective methods for single-objective discrete optimization, while their extension to multi-objective settings has been investigated only recently. In Multi-Objective Branch and Bound (MOBB) methods, the definition of effective bounding strategies remains a key challenge, as the notion of a scalar bound is replaced by that of a bound set[2]. Lagrangian relaxation, known for providing tight bounds in single-objective optimization, has recently shown the potential to generate tight bound sets also for multi-objective problems, due to its ability to approximate the interior of the feasible region [1]. This talk investigates the integration of Lagrangian relaxation within a MOBB framework, highlighting the difficulties of exploring these theoretical insights. [1] Matthew Brun, Tyler Perini, Saumya Sinha, and {Andrew J.} Schaefer. On the strength of lagrangian duality in multi objective integer programming. Mathematical Programming,212(1):683–715,2025. [2] Alex Dunbar, Saumya Sinha, and Andrew J Schaefer. Relaxations and duality for multi objective integer programming. Mathematical Programming, 207(1):577–616, 2024.

Fields of Study & Subjects

Advanced Optimization Algorithms Research Complexity and Algorithms in Graphs Optimization and Mathematical Programming

Publication details

Journal / source
IRIS Research product catalog (Sapienza University of Rome)
Publication date
1 January 2026
Language
EN