Skip to Main content Skip to Navigation
Journal articles

Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem

Abstract : Given a set of items, each with a profit and a weight and a conflict graph describing incompatibilities between items, the Disjunctively Constrained Knapsack Problem is to select the maximum profit set of compatible items while satisfying the knapsack capacity constraint. We develop a probabilistic tabu search heuristic with multiple neighborhood structures. The proposed algorithm is evaluated on a total of 50 benchmark instances from the literature up to 1000 items. Computational results disclose that the proposed tabu search method outperforms recent state-of-the-art approaches. In particular, our approach is able to reach 46 best known solutions and discover 8 new best known solutions out of 50 benchmark instances.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03401130
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 11:52:14 AM
Last modification on : Wednesday, November 3, 2021 - 5:22:07 AM

Links full text

Identifiers

Collections

Citation

Mariem Ben Salem, Said Hanafi, Raouia Taktak, Hanene Ben-Abdallah. Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem. RAIRO - Operations Research, EDP Sciences, 2017, 51 (3), pp.627-637. ⟨10.1051/ro/2016049⟩. ⟨hal-03401130⟩

Share

Metrics

Record views

5