Geodesic
Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem
Ben Salem, Mariem1 ; Hanafi, Saïd2  ; Taktak, Raouia3 ; Ben Abdallah, Hanêne4
1 FSEGS/MIRACL, Université de Sfax, Tunisia
2 Université de Valenciennes, LAMIH – UMR CNRS 8201, France
3 ISIMS/CRNS, Université de Sfax, Tunisia
4 King Abdulaziz University, Jeddah, Saudi Arabia
RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 627-637

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2016049
Classification : 90C27, 90C59
Keywords: Probabilistic Tabu Search, knapsack problem, weighted independent set, conflict graph

Ben Salem, Mariem 1 ; Hanafi, Saïd 2 ; Taktak, Raouia 3 ; Ben Abdallah, Hanêne 4

1 FSEGS/MIRACL, Université de Sfax, Tunisia
2 Université de Valenciennes, LAMIH – UMR CNRS 8201, France
3 ISIMS/CRNS, Université de Sfax, Tunisia
4 King Abdulaziz University, Jeddah, Saudi Arabia 
@article{RO_2017__51_3_627_0,
     author = {Ben Salem, Mariem and Hanafi, Sa{\"\i}d and Taktak, Raouia and Ben Abdallah, Han\^ene},
     title = {Probabilistic {Tabu} search with multiple neighborhoods for the {Disjunctively} {Constrained} {Knapsack} {Problem}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {627--637},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {3},
     year = {2017},
     doi = {10.1051/ro/2016049},
     mrnumber = {3880516},
     zbl = {1387.90227},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2016049/}
}
TY  - JOUR
AU  - Ben Salem, Mariem
AU  - Hanafi, Saïd
AU  - Taktak, Raouia
AU  - Ben Abdallah, Hanêne
TI  - Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2017
SP  - 627
EP  - 637
VL  - 51
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2016049/
DO  - 10.1051/ro/2016049
LA  - en
ID  - RO_2017__51_3_627_0
ER  - 
%0 Journal Article
%A Ben Salem, Mariem
%A Hanafi, Saïd
%A Taktak, Raouia
%A Ben Abdallah, Hanêne
%T Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2017
%P 627-637
%V 51
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2016049/
%R 10.1051/ro/2016049
%G en
%F RO_2017__51_3_627_0
Ben Salem, Mariem; Hanafi, Saïd; Taktak, Raouia; Ben Abdallah, Hanêne. Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 627-637. doi: 10.1051/ro/2016049

Cité par Sources :