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

Michel Vasquez; Jin-Kao Hao

RAIRO - Operations Research (2010)

  • Volume: 35, Issue: 4, page 415-438
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Vasquez, Michel, and Hao, Jin-Kao. "Une approche hybride pour le sac à dos multidimensionnel en variables 0–1." RAIRO - Operations Research 35.4 (2010): 415-438. <http://eudml.org/doc/197839>.

@article{Vasquez2010,
abstract = {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. },
author = {Vasquez, Michel, Hao, Jin-Kao},
journal = {RAIRO - Operations Research},
keywords = {Sac-à-dos multidimensionnel; programmation linéaire; recherche tabou.; 0-1 multidimensional knapsack problem; linear programming; tabu search},
language = {fre},
month = {3},
number = {4},
pages = {415-438},
publisher = {EDP Sciences},
title = {Une approche hybride pour le sac à dos multidimensionnel en variables 0–1},
url = {http://eudml.org/doc/197839},
volume = {35},
year = {2010},
}

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
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 4
SP - 415
EP - 438
AB - 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.
LA - fre
KW - Sac-à-dos multidimensionnel; programmation linéaire; recherche tabou.; 0-1 multidimensional knapsack problem; linear programming; tabu search
UR - http://eudml.org/doc/197839
ER -

References

top
  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.  
  2. E. Balas et C.H. Martin, Pivot and Complement a Heuristic for 0-1 Programming. Management Sci.26 (1980) 86-96.  
  3. R. Battiti et G. Tecchiolli, The reactive tabu search. ORSA J. Comput.6 (1994) 128-140.  
  4. R. Bellman et D. Stuart, Applied Dynamic Programming. Princeton University Press (1962).  
  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 5es journées nationales sur la résolution pratique de problèmes NP-complets (1999) 151-162.  
  6. I. Charon et O. Hudry, The noising method: A new method for combinatorial optimization. Oper. Res. Lett.14 (1993) 133-137.  
  7. P.C. Chu et J.E. Beasley, A genetic algorithm for the multidimensional knapsack problem. J. Heuristic4 (1998) 63-86.  
  8. F. Dammeyer et S. Voß, Dynamic tabu list management using the reverse elimination method. Ann. Oper. Res.41 (1993) 31-46.  
  9. G.B. Dantzig, Discrete-variable extremum problems. Oper. Res.5 (1957) 266-277.  
  10. A. Drexl, A simulated annealing approach to the multiconstraint zero-one knapsack problem. Computing40 (1988) 1-8.  
  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.  
  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.  
  13. A. Fréville et G. Plateau, The 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool. J. Heuristics2 (1997) 147-167.  
  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).  
  15. M. Garey et D. Johnson, Computers & Intractability A Guide to the Theory of NP-Completeness. W.H. Freeman and Company (1979).  
  16. B. Gavish et H. Pirkul, Allocation of data bases and processors in a distributed computting system. Management of Distributed Data Processing31 (1982) 215-231.  
  17. B. Gavish et H. Pirkul, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math. Programming31 (1985) 78-105.  
  18. P.C. Gilmore et R.E. Gomory, The theory and computation of knapsack functions. Oper. Res.14 (1966) 1045-1074.  
  19. F. Glover, Tabu search. ORSA J. Computing2 (1990) 4-32.  
  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.  
  21. M. Gondran et M. Minoux, Graphes & algorithmes. Eyrolles (1985).  
  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.  
  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.  
  25. J. Lorie et L.J. Savage, Three problems in capital rationing. J. Business28 (1955) 229-239.  
  26. A. Lo/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.  
  27. A. Lo/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).  
  28. S. Martello et P. Toth, Knapsack Problems: Algorithms and Computer Implementations. John Wiley (1990).  
  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).  
  31. W. Shih, A branch & bound method for the multiconstraint zero-one knapsack problem. J. Oper. Res. Soc.30 (1979) 369-378.  
  32. Y. Toyoda, A simplified algorithm for obtaining approximate solutions to zero-one programming problem. Management Sci.21 (1975) 1417-1427.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.