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://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
DA  - 2001///
SP  - 415
EP  - 438
VL  - 35
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/RO_2001__35_4_415_0/
UR  - https://zbmath.org/?q=an%3A1015.90056
LA  - fr
ID  - RO_2001__35_4_415_0
ER  - 
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://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 0798.90105

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

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

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

[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 1246967 | Zbl 0798.90118

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

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

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

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

[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 0579.90066

[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 0777.90032

[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 0870.90084

[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 0969.90079

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

[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 787388 | Zbl 0571.90065

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

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

[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 0877.90055

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

[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 0991.90089

[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 938772 | Zbl 0638.90069

[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 0991.90091

[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 1788689 | Zbl 0970.90078

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

[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 1201159 | Zbl 0845.65001

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

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