Variable Neighborhood Search with Dynamic Exploration for the Set Union Knapsack Problem

Igor Machado Coelho (), Saïd Hanafi (), Raca Todosijevic (), Mustapha Ratli () and Bernard Gendron
Additional contact information
Igor Machado Coelho: Universidade do Estado do Rio de Janeiro
Saïd Hanafi: Université Polytechnique de Hauts de France, CNRS UMR 8201
Raca Todosijevic: Université Polytechnique de Hauts de France, CNRS UMR 8201
Mustapha Ratli: Université Polytechnique de Hauts de France, CNRS UMR 8201
Bernard Gendron: CIRRELT, Université de Montréal

A chapter in Combinatorial Optimization and Applications, 2024, pp 17-35 from Springer

Abstract: Abstract In the set-union knapsack problem (SUKP), we are given a set of elements, each with a positive weight, and a set of items, each with a positive profit and a corresponding set of associated elements. An item is included in the knapsack only if all its associated elements are included. The SUKP is to select the items to be included in the knapsack such that the total profit of the selected items is maximized and the capacity of the knapsack is not exceeded. We propose a variable neighborhood search to solve the SUKP and show, on a set of benchmark instances from the literature, that this method is competitive with the state-of-the-art heuristics for the problem. In addition, we focus on simplicity of the proposed algorithm while providing competitive results, thus showing that less may yield more.

Keywords: Heuristics; Variable neighborhood search; Set union knapsack problem; Dynamic exploration; Less-is-more (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:isochp:978-3-031-57603-4_2

Ordering information: This item can be ordered from
http://www.springer.com/9783031576034

DOI: 10.1007/978-3-031-57603-4_2

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().