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 benchmark instances from the literature up to 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 best known solutions and discover new best known solutions out of benchmark instances.
Accepté le :
DOI : 10.1051/ro/2016049
Mots-clés : Probabilistic Tabu Search, knapsack problem, weighted independent set, conflict graph
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2016049/
Local branching-based algorithms for the disjunctively constrained knapsack problem. Comput. Industrial Eng. 60 (2011) 811–820. | DOI
, and ,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).
A multi-level search strategy for the 0–1 multidimensional knapsack problem. Discrete Appl. Math. 158 (2010) 97–109. | DOI | MR | Zbl
, , , and ,A tabu search procedure for multicommodity location/allocation with balancing requirements. Ann. Oper. Res. 41 (1993) 359–383. | DOI | Zbl
, , and ,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).
On bin packing with conflicts. SIAM J. Optim. 19 (2008) 1270–1298. | DOI | MR | Zbl
and ,Two-dimensional packing with conflicts. Acta Inf. 45 (2008) 155–175. | DOI | MR | Zbl
, and ,The multidimensional 0–1 knapsack problem: An overview. Europ. J. Oper. Res. 155 (2004) 1–21. | DOI | MR | Zbl
,The multidimensional 0-1 knapsack problembounds and computational aspects. Ann. Oper. Res. 139 (2005) 195–227. | DOI | MR | Zbl
and ,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
Heuristics and lower bounds for the bin packing problem with conflicts. Comput. Oper. Res. 31 (2004) 347–358. | DOI | MR | Zbl
, and ,Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13 (1986) 533–549. | DOI | MR | Zbl
,Tabu search-part i. ORSA J. Comput. 1 (1989) 190–206. | DOI | Zbl
,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).
On the convergence of tabu search. J. Heuristics 7 (2001) 47–58. | DOI | Zbl
,An efficient tabu search approach for the 0–1 multidimensional knapsack problem. Europ. J. Oper. Res. 106 (1998) 659–675. | DOI | Zbl
and ,An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem. Engrg. Optim. 46 (2014) 1109–1122. | DOI | MR
,A reactive local search-based algorithm for the disjunctively constrained knapsack problem. J. Oper. Res. Soc. 57 (2006) 718–726. | DOI | Zbl
and ,Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem. Comput. Oper. Res. 34 (2007) 2657–2673. | DOI | Zbl
and ,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.
A hybrid guided neighborhood search for the disjunctively constrained knapsack problem. Cogent Engrg. 2 (2015) 1068969. | DOI
, , and ,An approximation scheme for bin packing with conflicts. J. Combin. Optim. 3 (1999) 363–377. | DOI | MR | Zbl
,The min-conflict packing problem. Comput. Oper. Res. 39 (2012) 2122–2132. | DOI | MR | Zbl
, , and ,New lower bounds for bin packing problems with conflicts. Europ. J. Oper. Res. 206 (2010) 281–288. | DOI | MR | Zbl
, and ,Heuristics for solving the bin-packing problem with conflicts. Appl. Math. Sci. 5 (2011) 1739–1752. | MR | Zbl
and ,S. Martello and P. Toth, Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. (1990). | MR | Zbl
The knapsack problem with conflict graphs. J. Graph Algorithms Appl. 13 (2009) 233–249. | DOI | MR | Zbl
and ,Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS J. Comput. 19 (2007) 36–51. | DOI | MR | Zbl
and ,Bin packing with conflicts: a generic branch-and-price algorithm. INFORMS J. Comput. 25 (2013) 244–255. | DOI | MR
and ,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.
Diversification strategies in tabu search algorithms for the maximum clique problem. Ann. Oper. Res. 63 (1996) 189–207. | DOI | Zbl
and ,Probabilistic tabu search for telecommunications network design. Comb. Optim. Theory Practice 1 (1996) 69–94.
, and ,Heuristic and exact algorithms for the disjunctively constrained knapsack problem. Inform. Process. Soc. Jpn. J. 43 (2002). | MR
, and ,Cité par Sources :