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

Ben Salem, Mariem; Hanafi, Saïd; Taktak, Raouia; Ben Abdallah, Hanêne

doi:10.1051/ro/2016049

Ben Salem, Mariem ¹ ; Hanafi, Saïd ² ; Taktak, Raouia ³ ; Ben Abdallah, Hanêne ⁴

¹ FSEGS/MIRACL, Université de Sfax, Tunisia
² Université de Valenciennes, LAMIH – UMR CNRS 8201, France
³ ISIMS/CRNS, Université de Sfax, Tunisia
⁴ King Abdulaziz University, Jeddah, Saudi Arabia

RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 3, pp. 627-637.

Résumé

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 : 2016-05-25
Accepté le : 2016-06-20

MR Zbl

DOI : 10.1051/ro/2016049

Classification : 90C27, 90C59
Mots-clés : Probabilistic Tabu Search, knapsack problem, weighted independent set, conflict graph

Affiliations des auteurs :

Ben Salem, Mariem ¹ ; Hanafi, Saïd ² ; Taktak, Raouia ³ ; Ben Abdallah, Hanêne ⁴

@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 = {https://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  - https://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 https://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. https://www.numdam.org/articles/10.1051/ro/2016049/

Bibliographie
Cité par

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

Zhou, Qing; Hao, Jin‐Kao; Jiang, Zhong‐Zhong; Wu, Qinghua Adaptive feasible and infeasible evolutionary search for the knapsack problem with forfeits, International Transactions in Operational Research, Volume 32 (2025) no. 3, p. 1442 | DOI:10.1111/itor.13512
Punnen, Abraham P.; Dhahan, Jasdeep The Knapsack Problem with Conflict Pair Constraints on Bipartite Graphs and Extensions, Algorithms, Volume 17 (2024) no. 5, p. 219 | DOI:10.3390/a17050219
Almathkour, Fatmah; Diarrassouba, Ibrahima; Hadhbi, Youssouf Extended formulation and Branch-and-Cut-and-Price algorithm for the two connected subgraph problem with disjunctive constraints, Annals of Operations Research (2024) | DOI:10.1007/s10479-024-06123-0
Zhou, Qing; Hao, Jin-Kao; Jiang, Zhong-Zhong; Wu, Qinghua An effective hybrid search method for the quadratic knapsack problem with conflict graphs, Journal of the Operational Research Society, Volume 75 (2024) no. 5, p. 1000 | DOI:10.1080/01605682.2023.2228339
Almudahka, Intesar; Diarrassouba, Ibrahima; Mahjoub, A. Ridha; Taktak, Raouia Two-edge connectivity with disjunctive constraints: Polyhedral analysis and Branch-and-Cut, Computers Industrial Engineering, Volume 184 (2023), p. 109585 | DOI:10.1016/j.cie.2023.109585
Lalou, Mohammed; Kheddouci, Hamamache Pseudo-polynomial algorithms for solving the Knapsack Problem with dependencies between items, Computers Operations Research, Volume 158 (2023), p. 106281 | DOI:10.1016/j.cor.2023.106281
Wei, Zequn; Hao, Jin-Kao; Ren, Jintong; Glover, Fred Responsive strategic oscillation for solving the disjunctively constrained knapsack problem, European Journal of Operational Research, Volume 309 (2023) no. 3, p. 993 | DOI:10.1016/j.ejor.2023.02.009
Cacchiani, Valentina; Iori, Manuel; Locatelli, Alberto; Martello, Silvano Knapsack problems — An overview of recent advances. Part I: Single knapsack problems, Computers Operations Research, Volume 143 (2022), p. 105692 | DOI:10.1016/j.cor.2021.105692
Wilbaut, Christophe; Hanafi, Saïd; Coelho, Igor Machado; Lucena, Abilio The Knapsack Problem and Its Variants: Formulations and Solution Methods, The Palgrave Handbook of Operations Research (2022), p. 105 | DOI:10.1007/978-3-030-96935-6_4
Wei, Zequn; Hao, Jin-Kao A threshold search based memetic algorithm for the disjunctively constrained knapsack problem, Computers Operations Research, Volume 136 (2021), p. 105447 | DOI:10.1016/j.cor.2021.105447
Laguna, Manuel Tabu and Scatter Search: Principles and Practice, Recent Advances in Optimization and Modeling of Contemporary Problems (2018), p. 130 | DOI:10.1287/educ.2018.0181
de Queiroz, Thiago Alves; Hokama, Pedro Henrique Del Bianco; Schouery, Rafael Crivellari Saliba; Miyazawa, Flávio Keidi Two-dimensional Disjunctively Constrained Knapsack Problem: Heuristic and exact approaches, Computers Industrial Engineering, Volume 105 (2017), p. 313 | DOI:10.1016/j.cie.2017.01.015

Cité par 12 documents. Sources : Crossref