EURO 2025 Leeds
Abstract Submission

2688. Lagrangian Relaxations for Multi-Objective Discrete Optimization Problems

Invited abstract in session TB-51: Multiobjective discrete optimization, stream Multiobjective and vector optimization.

Tuesday, 10:30-12:00
Room: Parkinson B22

Authors (first author is the speaker)

1. Mariagrazia Cairo
Statistical Sciences, Sapienza University of Rome
2. Lavinia Amorosi
Statistical Sciences, Sapienza
3. Dell'Olmo Paolo
Dipartimento di Statistica, Probabilità, Statistiche applicate, University of Rome La Sapienza
4. Serpil Sayin
College of Administrative Sciences and Economics, Koc University

Abstract

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

Keywords

Status: accepted

Back to the list of papers