Issue |
RAIRO-Oper. Res.
Volume 51, Number 3, July-September 2017
|
|
---|---|---|
Page(s) | 627 - 637 | |
DOI | https://doi.org/10.1051/ro/2016049 | |
Published online | 24 July 2017 |
Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem
1 FSEGS/MIRACL, Université de Sfax, Tunisia
bensalem.mariem@gmail.com
2 Université de Valenciennes, LAMIH – UMR CNRS 8201, France
3 ISIMS/CRNS, Université de Sfax, Tunisia
4 King Abdulaziz University, Jeddah, Saudi Arabia
Received: 25 May 2016
Accepted: 20 June 2016
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.
Mathematics Subject Classification: 90C27 / 90C59
Key words: Probabilistic Tabu Search / knapsack problem / weighted independent set / conflict graph
© EDP Sciences, ROADEF, SMAI 2017
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.