liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A meta-heuristic extension of the Lagrangian heuristic framework
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0003-2094-7376
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-9881-4170
2024 (English)In: Optimization Methods and Software, ISSN 1055-6788, E-ISSN 1029-4937, Vol. 39, no 5, p. 1008-1039Article in journal (Refereed) Published
Abstract [en]

Lagrangian heuristics for discrete optimization work by modifying Lagrangian relaxed solutions into feasible solutions to an original problem. They are designed to identify feasible, and hopefully also near-optimal, solutions and have proven to be highly successful in many applications. Based on a primal-dual global optimality condition for non-convex optimization problems, we develop a meta-heuristic extension of the Lagrangian heuristic framework. The optimality condition characterizes (near-)optimal solutions in terms of near-optimality and near-complementarity measures for Lagrangian relaxed solutions. The meta-heuristic extension amounts to constructing a weighted combination of these measures, thus creating a parametric auxiliary objective function, which is a close relative to a Lagrangian function, and embedding a Lagrangian heuristic in a search procedure in the space of the weight parameters. We illustrate and make a first assessment of this meta-heuristic extension by applying it to the generalized assignment and set covering problems. Our computational experience show that the meta-heuristic extension of a standard Lagrangian heuristic can significantly improve upon solution quality.

Place, publisher, year, edition, pages
TAYLOR & FRANCIS LTD , 2024. Vol. 39, no 5, p. 1008-1039
Keywords [en]
Discrete optimization; global optimality conditions; Lagrangian relaxation; meta-heuristics
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-208662DOI: 10.1080/10556788.2024.2404094ISI: 001330052100001OAI: oai:DiVA.org:liu-208662DiVA, id: diva2:1907075
Available from: 2024-10-21 Created: 2024-10-21 Last updated: 2025-04-24

Open Access in DiVA

fulltext(5107 kB)500 downloads
File information
File name FULLTEXT01.pdfFile size 5107 kBChecksum SHA-512
30f0ec746a4a1fd8360668306ca03c1ef3a9f91ad135d5a92a2b2b24265a565c9ea2271497ded59016a3d4665c64fc620ce6ccd668076d53acfaa95526f54310
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Ngulo, UlediLarsson, TorbjörnQuttineh, Nils-Hassan
By organisation
Applied MathematicsFaculty of Science & Engineering
In the same journal
Optimization Methods and Software
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 502 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 122 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf