An integrated ILS-VND strategy for solving the knapsack problem with forfeits

Matheus M. Vieira (), Bruno Nogueira () and Rian G. S. Pinheiro ()
Additional contact information
Matheus M. Vieira: Universidade Federal de Alagoas
Bruno Nogueira: Universidade Federal de Alagoas
Rian G. S. Pinheiro: Universidade Federal de Alagoas

Journal of Heuristics, 2024, vol. 30, issue 5, No 7, 399-420

Abstract: Abstract This work address a variant of the knapsack problem, known as the knapsack problem with forfeits, which has numerous applications. In this variant, a set of items and a conflict graph are given, and the objective is to identify a collection of items that adhere to the knapsack’s capacity while maximizing the total value of the items minus the penalties for conflicting items. We propose a novel heuristic for this problem based on the concepts of iterated local search, variable neighborhood descent, and tabu search. Our heuristic takes into account four neighborhood structures, and we introduce efficient data structures to explore them. Experimental results demonstrate that our approach outperforms the state-of-the-art algorithms in the literature. In particular, it delivers superior solutions within significantly shorter computation times across all benchmark instances. Additionally, this study includes an analysis of how the proposed data structures have influenced both the quality of the solutions and the execution time of the method.

Keywords: Combinatorial optimization; Knapsack problem; Metaheuristics; Iterated local search; Variable neighborhood descent (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-024-09532-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:30:y:2024:i:5:d:10.1007_s10732-024-09532-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-024-09532-3

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().