Une approche hybride pour le sac à dos multidimensionnel en variables 0-1
RAIRO - Operations Research - Recherche Opérationnelle, Volume 35 (2001) no. 4, pp. 415-438.

We present, in this article, a hybrid approach for solving the 0-1 multidimensional knapsack problem (MKP). This approach combines linear programming and Tabu search. The resulting algorithm improves on the best result on many well-known hard benchmarks.

Nous présentons, dans cet article, une approche hybride pour la résolution du sac à dos multidimensionnel en variables 0-1. Cette approche combine la programmation linéaire et la méthode tabou. L'algorithme ainsi obtenu améliore de manière significative les meilleurs résultats connus sur des instances jugées difficiles.

Mots-clés : sac-à-dos multidimensionnel, programmation linéaire, recherche tabou 
@article{RO_2001__35_4_415_0,
     author = {Vasquez, Michel and Hao, Jin-Kao},
     title = {Une approche hybride pour le sac \`a dos multidimensionnel en variables 0-1},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {415--438},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {4},
     year = {2001},
     zbl = {1015.90056},
     language = {fr},
     url = {https://www.numdam.org/item/RO_2001__35_4_415_0/}
}
TY  - JOUR
AU  - Vasquez, Michel
AU  - Hao, Jin-Kao
TI  - Une approche hybride pour le sac à dos multidimensionnel en variables 0-1
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2001
SP  - 415
EP  - 438
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/item/RO_2001__35_4_415_0/
LA  - fr
ID  - RO_2001__35_4_415_0
ER  - 
%0 Journal Article
%A Vasquez, Michel
%A Hao, Jin-Kao
%T Une approche hybride pour le sac à dos multidimensionnel en variables 0-1
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2001
%P 415-438
%V 35
%N 4
%I EDP-Sciences
%U https://www.numdam.org/item/RO_2001__35_4_415_0/
%G fr
%F RO_2001__35_4_415_0
Vasquez, Michel; Hao, Jin-Kao. Une approche hybride pour le sac à dos multidimensionnel en variables 0-1. RAIRO - Operations Research - Recherche Opérationnelle, Volume 35 (2001) no. 4, pp. 415-438. https://www.numdam.org/item/RO_2001__35_4_415_0/

[1] R. Aboudi et K. Jörnsten, Tabu Search for General Zero-One Integer Programs using the Pivot and Complement Heuristic. ORSA J. Comput. 6 (1994) 82-93. | Zbl

[2] E. Balas et C.H. Martin, Pivot and Complement a Heuristic for 0-1 Programming. Management Sci. 26 (1980) 86-96. | Zbl

[3] R. Battiti et G. Tecchiolli, The reactive tabu search. ORSA J. Comput. 6 (1994) 128-140. | Zbl

[4] R. Bellman et D. Stuart, Applied Dynamic Programming. Princeton University Press (1962). | MR | Zbl

[5] P. Boucher et G. Plateau, Étude des méthodes de bruitage appliquées au problème du sac à dos à plusieurs contraintes en variables 0-11999) 151-162.

[6] I. Charon et O. Hudry, The noising method : A new method for combinatorial optimization. Oper. Res. Lett. 14 (1993) 133-137. | MR | Zbl

[7] P.C. Chu et J.E. Beasley, A genetic algorithm for the multidimensional knapsack problem. J. Heuristic 4 (1998) 63-86. | Zbl

[8] F. Dammeyer et S. Voß, Dynamic tabu list management using the reverse elimination method. Ann. Oper. Res. 41 (1993) 31-46. | Zbl

[9] G.B. Dantzig, Discrete-variable extremum problems. Oper. Res. 5 (1957) 266-277. | MR

[10] A. Drexl, A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing 40 (1988) 1-8. | MR | Zbl

[11] A. Fréville et G. Plateau, Heuristic and reduction methods for multiple constraints 0-1 linear programming problems. Eur. J. Oper. Res. 24 (1986) 206-215. | Zbl

[12] A. Fréville et G. Plateau, Sac à dos multidimensionnel en variable 0-1 : encadrement de la somme des variables à l'optimum. RAIRO : Oper. Res. 27 (1993) 169-187. | Numdam | Zbl

[13] A. Fréville et G. Plateau, The 0-1 bidimensional knapsack problem : Toward an efficient high-level primitive tool. J. Heuristics 2 (1997) 147-167. | Zbl

[14] X. Gandibleux et A. Fréville, The multiobjective tabu search method customized on the 0/1 multiobjective knapsack problem : The two objectives case. J. Heuristics (à paraître). | Zbl

[15] M. Garey et D. Johnson, Computers & Intractability A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979). | MR | Zbl

[16] B. Gavish et H. Pirkul, Allocation of data bases and processors in a distributed computting system. Management of Distributed Data Processing 31 (1982) 215-231.

[17] B. Gavish et H. Pirkul, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math. Programming 31 (1985) 78-105. | MR | Zbl

[18] P.C. Gilmore et R.E. Gomory, The theory and computation of knapsack functions. Oper. Res. 14 (1966) 1045-1074. | MR | Zbl

[19] F. Glover, Tabu search. ORSA J. Computing 2 (1990) 4-32. | Zbl

[20] F. Glover et G.A. Kochenberger, Critical event tabu search for multidimensional knapsack problems, edité par I.H. Osman et J.P. Kelly, Metaheuristics : The Theory and Applications. Kluwer Academic Publishers (1996) 407-427. | Zbl

[21] M. Gondran et M. Minoux, Graphes & algorithmes. Eyrolles (1985). | MR | Zbl

[22] S. Hanafi, A. El Abdellaoui et A. Fréville, Extension de la Méthode d'Élimination Inverse pour une gestion dynamique de la liste tabou. RAIRO (à paraître).

[23] S. Hanafi et A. Fréville, An efficient tabu search approach for the 0-1 multidimensional knapsack problem. Eur. J. Oper. Res. 106 (1998) 659-675. | Zbl

[24] J.S. Lee et M. Guignard, An approximate algorithm for multidimensional zero-one knapsack problems a parametric approach. Management Sci. 34 (1998) 402-410. | MR | Zbl

[25] J. Lorie et L.J. Savage, Three problems in capital rationing. J. Business 28 (1955) 229-239.

[26] A. Løkketangen et F. Glover, Solving zéro-one mixed integer programming problems using tabu search. Eur. J. Oper. Res. 106 (1998). Special Issue on Tabu Search. | Zbl

[27] A. Løkketangen et F. Glover, Candidate list and exploration strategies for solving 0/1 mip problems using a pivot neighborhood, dans Metaheuristics. Kluwer Academic Publishers (1999). | MR | Zbl

[28] S. Martello et P. Toth, Knapsack Problems : Algorithms and Computer Implementations. John Wiley (1990). | MR | Zbl

[29] M.A. Osorio, F. Glover et P. Hammer, Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions, Technical report. Hearin Center for Enterprise Science. Report HCES-08-00 (2000).

[30] W.H. Press, S.A. Teukolsky, W.T. Vetterling et B.P. Flannery, Numerical Recipes in C. Cambridge University Press (1992). | MR | Zbl

[31] W. Shih, A branch & bound method for the multiconstraint zero-one knapsack problem. J. Oper. Res. Soc. 30 (1979) 369-378. | Zbl

[32] Y. Toyoda, A simplified algorithm for obtaining approximate solutions to zero-one programming problem. Management Sci. 21 (1975) 1417-1427. | MR | Zbl