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.

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
Mots-clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ro/2016049/

H. Akeb, M. Hifi and M. Elhafedh O.Ah. Mounir, Local branching-based algorithms for the disjunctively constrained knapsack problem. Comput. Industrial Eng. 60 (2011) 811–820. | DOI

Th. Alves de Queiroz and F.K. Miyazawa, Approaches for the 2d 0-1 knapsack problem with conflict graphs. In Computing Conference (CLEI), 2013 XXXIX Latin American. IEEE (2013) 1–8.

A. Bettinelli, V. Cacchiani and E. Malaguti, Bounds and algorithms for the knapsack problem with conflict graph. Technical Report OR-14-16, DEIS–University of Bologna, Bologna, Italy (2014).

S. Boussier, M. Vasquez, Y. Vimont, S. Hanafi and Ph. Michelon, A multi-level search strategy for the 0–1 multidimensional knapsack problem. Discrete Appl. Math. 158 (2010) 97–109. | DOI | MR | Zbl

T.G. Crainic, M. Gendreau, P. Soriano and M. Toulouse, A tabu search procedure for multicommodity location/allocation with balancing requirements. Ann. Oper. Res. 41 (1993) 359–383. | DOI | Zbl

G.B. Dantzig, Discrete-variable extremum problems. Oper. Res. 5 (1957) 266–288. | DOI | MR | Zbl

Th. Alves de Queiroz and F. Keidi Miyazawa, Problema da mochila 0-1 bidimensional com restriçoes de disjunçao (2012).

L. Epstein and A. Levin, On bin packing with conflicts. SIAM J. Optim. 19 (2008) 1270–1298. | DOI | MR | Zbl

L. Epstein, A. Levin and R. Van Stee, Two-dimensional packing with conflicts. Acta Inf. 45 (2008) 155–175. | DOI | MR | Zbl

A. Fréville, The multidimensional 0–1 knapsack problem: An overview. Europ. J. Oper. Res. 155 (2004) 1–21. | DOI | MR | Zbl

A. Fréville and S. Hanafi, The multidimensional 0-1 knapsack problembounds and computational aspects. Ann. Oper. Res. 139 (2005) 195–227. | DOI | MR | Zbl

M.R. Garey and D.S. Johnson, Computers and intractability: a guide to the theory of np-completeness. San Francisco, LA: Freeman (1979). | MR | Zbl

M. Gendreau, G. Laporte and F. Semet, Heuristics and lower bounds for the bin packing problem with conflicts. Comput. Oper. Res. 31 (2004) 347–358. | DOI | MR | Zbl

F. Glover, Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13 (1986) 533–549. | DOI | MR | Zbl

F. Glover, Tabu search-part i. ORSA J. Comput. 1 (1989) 190–206. | DOI | Zbl

F. Glover, Tabu thresholding: Improved search by nonmonotonic trajectories. ORSA J. Comput. 7 (1995) 426–442. | DOI | Zbl

F. Glover and M. Laguna, Tabu search. Springer (1997). | MR | Zbl

F. Glover and A. Lokketangen, Probabilistic tabu search for zero-one mixed integer programming problems. University of Colorado, Boulder, USA (1994).

S. Hanafi, On the convergence of tabu search. J. Heuristics 7 (2001) 47–58. | DOI | Zbl

S. Hanafi and A. Fréville, An efficient tabu search approach for the 0–1 multidimensional knapsack problem. Europ. J. Oper. Res. 106 (1998) 659–675. | DOI | Zbl

M. Hifi, An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem. Engrg. Optim. 46 (2014) 1109–1122. | DOI | MR

M. Hifi and M. Michrafy, A reactive local search-based algorithm for the disjunctively constrained knapsack problem. J. Oper. Res. Soc. 57 (2006) 718–726. | DOI | Zbl

M. Hifi and M. Michrafy, Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Comput. Oper. Res. 34 (2007) 2657–2673. | DOI | Zbl

M. Hifi, S. Negre and M.Q.A. Mounir, Local branching-based algorithm for the disjunctively constrained knapsack problem. In CIE 2009 – International Conference on Computers & Industrial Engineering. IEEE (2009) 279–284.

M. Hifi, S. Negre, T. Saadi, S. Saleh and L. Wu, A parallel large neighborhood search-based heuristic for the disjunctively constrained knapsack problem. In IPDPSW 2014: International Parallel & Distributed Processing Symposium Workshops. IEEE (2014) 1547–1551.

M. Hifi and N. Otmani, A first level scatter search for disjunctively constrained knapsack problems. In International Conference on Communications, Computing and Control Applications (CCCA). IEEE (2011) 1–6.

M. Hifi, S. Saleh, L. Wu and J. Chen, A hybrid guided neighborhood search for the disjunctively constrained knapsack problem. Cogent Engrg. 2 (2015) 1068969. | DOI

K. Jansen, An approximation scheme for bin packing with conflicts. J. Combin. Optim. 3 (1999) 363–377. | DOI | MR | Zbl

A. Khanafer, F. Clautiaux, S. Hanafi and E.-Gh. Talbi, The min-conflict packing problem. Comput. Oper. Res. 39 (2012) 2122–2132. | DOI | MR | Zbl

A. Khanafer, F. Clautiaux and E.-Ghazali Talbi, New lower bounds for bin packing problems with conflicts. Europ. J. Oper. Res. 206 (2010) 281–288. | DOI | MR | Zbl

M. Maiza and M.S. Radjef, Heuristics for solving the bin-packing problem with conflicts. Appl. Math. Sci. 5 (2011) 1739–1752. | MR | Zbl

S. Martello and P. Toth, Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. (1990). | MR | Zbl

U. Pferschy and J. Schauer, The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13 (2009) 233–249. | DOI | MR | Zbl

D. Pisinger and M. Sigurd, Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS J. Comput. 19 (2007) 36–51. | DOI | MR | Zbl

R. Sadykov and F. Vanderbeck, Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS J. Comput. 25 (2013) 244–255. | DOI | MR

A. Senisuka, B. You and T. Yamada, Reduction and exact algorithms for the disjunctively constrained knapsack problem. In: International symposium on operations research and its applications; ISORA’05. Lecture Notes in Operations Research (2005) 241–254.

P. Soriano and M. Gendreau, Diversification strategies in tabu search algorithms for the maximum clique problem. Ann. Oper. Res. 63 (1996) 189–207. | DOI | Zbl

J. Xu, S.Y. Chiu and F. Glover, Probabilistic tabu search for telecommunications network design. Comb. Optim. Theory Practice 1 (1996) 69–94.

T. Yamada, S. Kataoka and K. Watanabe, Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Inform. Process. Soc. Jpn. J. 43 (2002). | MR

Cité par Sources :