EUVIMEDEUVIMED entdecken
Crossref

LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup

Malek Masmoudi, Yassine Adouani, Bassem Jarboui

International Transactions in Operational Research · 2024-05 · 31 (3) · 1890-1916

DOI: 10.1111/itor.13213 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Transactions in Operational Research, 2022-10. Verfasst von Malek Masmoudi und 2 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 46 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the multiple knapsack problem (KP) with setup (MKPS), which is an extension of the KP with setup (KPS). We propose a new solving approach denoted by LP&DP‐VNS that combines linear programming (LP) relaxation and dynamic programming (DP) to enhance variable neighborhood search (VNS). The LP&DP‐VNS is tailored to the characteristics of the MKPS and reduced to LP&DP to solve the KPS. The approach is tested on 200 KPS and 360 MKPS benchmark instances. Computational experiments show the effectiveness of the LP&DP‐VNS, compared to integer programming (using CPLEX) and the best state‐of‐the‐art algorithms. It reaches 299/342 optimal solutions and 316/318 best‐known solutions and provides 127 new best solutions. An additional computational study shows that the LP&DP‐VNS scales up extremely well, solving optimally and near‐optimally very large instances with up 200 families and 300,000 items in a reasonable amount of time.

Zitieren

APA

Masmoudi, M., Adouani, Y., & Jarboui, B. (2024). LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup. International Transactions in Operational Research, 31(3), 1890-1916. https://doi.org/10.1111/itor.13213

Vancouver

Masmoudi M, Adouani Y, Jarboui B. LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup. International Transactions in Operational Research. 2024;31(3):1890-1916. doi:10.1111/itor.13213

BibTeX
@article{Masmoudi2024,
  author = {Masmoudi, Malek and Adouani, Yassine and Jarboui, Bassem},
  title = {LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup},
  journal = {International Transactions in Operational Research},
  year = {2024},
  volume = {31},
  number = {3},
  pages = {1890--1916},
  doi = {10.1111/itor.13213}
}
Kostenlos starten →