Une approche hybride pour le sac à dos multidimensionnel en variables 0–1

 Access to full text

 Full (PDF)

1. [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. Zbl0798.90105
2. [2] E. Balas et C.H. Martin, Pivot and Complement a Heuristic for 0–1 Programming. Management Sci. 26 (1980) 86-96. Zbl0442.90060
3. [3] R. Battiti et G. Tecchiolli, The reactive tabu search. ORSA J. Comput. 6 (1994) 128-140. Zbl0807.90094
4. [4] R. Bellman et D. Stuart, Applied Dynamic Programming. Princeton University Press (1962). Zbl0106.34901MR140369
5. [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–1, dans JNPCC’99 $5^{\mathrm{es}}$ journées nationales sur la résolution pratique de problèmes NP-complets (1999) 151-162. 
6. [6] I. Charon et O. Hudry, The noising method : A new method for combinatorial optimization. Oper. Res. Lett. 14 (1993) 133-137. Zbl0798.90118MR1246967
7. [7] P.C. Chu et J.E. Beasley, A genetic algorithm for the multidimensional knapsack problem. J. Heuristic 4 (1998) 63-86. Zbl0913.90218
8. [8] F. Dammeyer et S. Voß, Dynamic tabu list management using the reverse elimination method. Ann. Oper. Res. 41 (1993) 31-46. Zbl0775.90290
9. [9] G.B. Dantzig, Discrete-variable extremum problems. Oper. Res. 5 (1957) 266-277. MR89098
10. [10] A. Drexl, A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing 40 (1988) 1-8. Zbl0638.65053MR938161
11. [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. Zbl0579.90066
12. [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. Zbl0777.90032
13. [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. Zbl0870.90084
14. [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). Zbl0969.90079
15. [15] M. Garey et D. Johnson, Computers & Intractability A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979). Zbl0411.68039MR519066
16. [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. [17] B. Gavish et H. Pirkul, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math. Programming 31 (1985) 78-105. Zbl0571.90065MR787388
18. [18] P.C. Gilmore et R.E. Gomory, The theory and computation of knapsack functions. Oper. Res. 14 (1966) 1045-1074. Zbl0173.21502MR204149
19. [19] F. Glover, Tabu search. ORSA J. Computing 2 (1990) 4-32. Zbl0771.90084
20. [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. Zbl0877.90055
21. [21] M. Gondran et M. Minoux, Graphes & algorithmes. Eyrolles (1985). Zbl0497.05023MR868083
22. [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. [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. Zbl0991.90089
24. [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. Zbl0638.90069MR938772
25. [25] J. Lorie et L.J. Savage, Three problems in capital rationing. J. Business 28 (1955) 229-239. 
26. [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. Zbl0991.90091
27. [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). Zbl0970.90078MR1788689
28. [28] S. Martello et P. Toth, Knapsack Problems : Algorithms and Computer Implementations. John Wiley (1990). Zbl0708.68002MR1086874
29. [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. [30] W.H. Press, S.A. Teukolsky, W.T. Vetterling et B.P. Flannery, Numerical Recipes in C. Cambridge University Press (1992). Zbl0845.65001MR1201159
31. [31] W. Shih, A branch & bound method for the multiconstraint zero-one knapsack problem. J. Oper. Res. Soc. 30 (1979) 369-378. Zbl0411.90050
32. [32] Y. Toyoda, A simplified algorithm for obtaining approximate solutions to zero-one programming problem. Management Sci. 21 (1975) 1417-1427. Zbl0307.90056MR441358