Lagrangian Relaxations for Multi-Objective Discrete Optimization Problems

The majority of the algorithms for Multi-Objective Discrete Optimization (MODO) problems relies on scalarizations of the problem and investigations in the objective space. Although branch and bound techniques are highly effective in single-objective optimization, Multi-Objective Branch and Bound (MOBB) methods have only emerged recently. Bounding is one of the most challenging aspects in MOBB where the classic single-objective concept of a bound is substituted by the concept of a bound set [2]. Lagrangian relaxation is a technique that is known to outperform linear programming-based bounds in single objective branch-and-bound methods. Recent studies have shown that Lagrangian relaxation has the potential to provide tighter bound sets than linear programming relaxations also for MODO problems. This is due to their ability to reach the interior of the feasible region. An appropriate choice of the lower bound set is important for the performance of MOBB methods: improved lower bound sets reduce the area where possibly new non-dominated points could be found [1]. This talk investigates the potential and effectiveness of Lagrangian relaxation within a MOBB setting. The results of preliminary computational experiments are discussed. [1]Bauß, J., et al., Adaptive improvements of multi-objective branch and bound, arXiv:2312.12192 preprint, 2023 [2]Dunbar, A., et al., Relaxations and duality for multiobjective integer programming, Mathematical Programming, 207(1):577-616, 2024