An algorithm for generating Lagrangian bound sets in Multiobjective Integer Programming

Lagrangian relaxation is a well-established technique for deriving strong bounds in single-objective discrete optimization. Its generalization to the multiobjective setting is not straightforward, as preserving the multiobjective structure leads to bound sets rather than scalar bounds. Recent studies show the existence of Lagrange multipliers that can yield tighter bound sets than those obtained from convex hull relaxations. However, from an algorithmic perspective, the potential benefits and challenges of applying Lagrangian relaxation to multiobjective integer programming remain largely unexplored. In this article, we develop the first algorithmic framework to generate bound sets for multiobjective integer linear programs via Lagrangian relaxation. Our approach preserves the multiobjective structure of the problem in the Lagrangian dual. Computational experiments on biobjective benchmark instances show that Lagrangian bound sets obtained by the algorithm are significantly tighter than those obtained from linear relaxations. In a proof of concept implementation, we embed our algorithm within a branch-and-bound scheme for a biobjective knapsack problem and assess the impact of Lagrangian bound sets on pruning efficiency and computational time in comparison with the linear programming bound sets. Our results illustrate the potential of Lagrangian bound sets for multiobjective integer programming.