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

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.