EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2573. A Lagrangian Bounding and Heuristic Principle for Bi-Objective Discrete Optimization

Invited abstract in session WB-37: Discrete Multiobjective Optimization, stream Multiobjective Optimization.

Wednesday, 10:30-12:00
Room: 33 (building: 306)

Authors (first author is the speaker)

1. Nils-Hassan Quttineh
Department of Mathematics
2. Torbjörn Larsson
Mathematics, Linköping University
3. Ida Åkerholm
Department of Mathematics, Linköping University

Abstract

Lagrangian relaxation is a common and often successful way to approach computationally challenging single-objective discrete optimization problems with complicating side constraints. Its aim is often two-fold; first, it provides bounds for the optimal value, and, second, it can be used to heuristically find near-optimal feasible solutions, the quality of which can be assessed by the bounds. We consider bi-objective discrete optimization problems with complicating side constraints and extend this Lagrangian bounding and heuristic principle to such problems. The Lagrangian heuristic here produces non-dominated candidates for points on the Pareto frontier, while the bounding forms a polyhedral outer approximation of the Pareto frontier, which can be used to assess the quality of the candidate points. As an illustration example we consider a facility location problem in which both CO2 emission and cost should be minimized. The computational results are very encouraging, both with respect to bounding and the heuristically found non-dominated solutions. In particular, the Lagrangian bounding is much stronger than the outer approximation given by the Pareto frontier of the problem’s linear programming relaxation.

Keywords

Status: accepted

Back to the list of papers