On the Use of Lagrangian Relaxation in Multiobjective Integer Programming

Lagrangian relaxation is one of the most effective techniques for deriving strong bounds in single-objective discrete optimization. A direct, straightforward extension of this idea to multi-objective optimization can be obtained by applying it to the scalarizations of the original problem. When the multi-objective structure of the problem is preserved, and a Lagrangian relaxation is applied to the original problem, the setting becomes considerably more challenging. In this case, the relaxation naturally yields bound sets instead of scalar bounds. Recent works have introduced a theoretical framework for Lagrangian duality in multi-objective integer programs, showing that suitable choices of Lagrangian multipliers may yield bound sets tighter than those obtained from the convex hull relaxation. Building on these theoretical results, this work develops an algorithmic framework to generate bound sets for multi- objective integer linear programs via Lagrangian relaxation while preserving the multi-objective structure of the dual problem. The proposed approach generates Lagrangian bound sets that can strengthen the ones obtained from the linear relaxation. Computational experiments on benchmark instances of different problem classes show that the resulting bound sets can be significantly tighter. Finally, as a proof of concept, we illustrate how these bound sets can be incorporated into a branch-and-bound procedure and discuss their impact on search tree pruning.