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

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.

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.

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 = {http://archive.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  - http://archive.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 http://archive.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, Tome 35 (2001) no. 4, pp. 415-438. http://archive.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