Search: WFRF:(Quttineh Nils Hassan) >
A Lagrangian boundi...
A Lagrangian bounding and heuristic principle for bi-objective discrete optimization
-
- Larsson, Torbjörn (author)
- Linköpings universitet,Tillämpad matematik,Tekniska fakulteten
-
- Quttineh, Nils-Hassan (author)
- Linköpings universitet,Tillämpad matematik,Tekniska fakulteten
-
- Åkerholm, Ida (author)
- Linköpings universitet,Matematiska institutionen,Tekniska fakulteten
-
(creator_code:org_t)
- SPRINGER HEIDELBERG, 2024
- 2024
- English.
-
In: Operational Research. - : SPRINGER HEIDELBERG. - 1109-2858 .- 1866-1505. ; 24:2
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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 twofold; 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.
Subject headings
- NATURVETENSKAP -- Matematik -- Beräkningsmatematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Computational Mathematics (hsv//eng)
Keyword
- Multi-objective; Discrete optimization; Integer programming; Lagrangian duality; Heuristics; Facility location
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database