Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum

Arnaud Fréville; G. Plateau

RAIRO - Operations Research - Recherche Opérationnelle (1993)

  • Volume: 27, Issue: 2, page 169-187
  • ISSN: 0399-0559

How to cite

top

Fréville, Arnaud, and Plateau, G.. "Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum." RAIRO - Operations Research - Recherche Opérationnelle 27.2 (1993): 169-187. <http://eudml.org/doc/105055>.

@article{Fréville1993,
author = {Fréville, Arnaud, Plateau, G.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {bidimensional knapsack; surrogate dual; tight bounds; 0-1 multidimensional knapsack problem},
language = {fre},
number = {2},
pages = {169-187},
publisher = {EDP-Sciences},
title = {Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum},
url = {http://eudml.org/doc/105055},
volume = {27},
year = {1993},
}

TY - JOUR
AU - Fréville, Arnaud
AU - Plateau, G.
TI - Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1993
PB - EDP-Sciences
VL - 27
IS - 2
SP - 169
EP - 187
LA - fre
KW - bidimensional knapsack; surrogate dual; tight bounds; 0-1 multidimensional knapsack problem
UR - http://eudml.org/doc/105055
ER -

References

top
  1. [BOPL91] P. BOURGEOIS and G. PLATEAU, BPK90 : A Revisited Hybrid Algorithm for the 0-1 Knapsack Problem, Publication LIPN, 1991, n° 91-2.Université Paris-Nord. 
  2. [DYE80] H. E. DYER, Calculating Surrogate Constraints, Mathematical Programming 19, 1980, p. 255-278. Zbl0464.90067MR589258
  3. [FAPL82] D. FAYARD and G. PLATEAU, An Algorithm for the Solution of the 0-1 Knapsack Problem, Compting, 1982, 28, p. 269-287. Zbl0468.90045
  4. [FAPL92] D. FAYARD and G. PLATEAU, An Exact Algorithm for the 0-1 Collapsing Knapsack Problem. Proceedings de la conférence "Viewpoints on Optimization", Grimentz, Suisse, Août 1990, à paraître dans Discrete Applied Mathematics. Zbl0806.90089
  5. [FLP90] A. FRÉVILLE, L. A. N. LORENA and G. PLATEAU, A Monotone Decreasing Algorithm for Solving the Surrogate Dual of 0-1 Multiknapsack Problems, Publication LIPN, 1990, n° 90-13, Université Paris-Nord. 
  6. [FRE91] A. FRÉVILLE, Contribution à l'optimisation en nombres entiers, Thèse d'habilitation à diriger des recherches, Université Paris-Nord, 1991. 
  7. [FRPL86] A. FRÉVILLE and G. PLATEAU, Heuristics and Reduction Methods for Multiple Constraints 0-1 Linear Programming Problems, European Journal of Operational Research, 1986, 24, p. 206-215. Zbl0579.90066MR827232
  8. [FRPL90] A. FRÉVILLE and G. PLATEAU, Hard 0-1 Multiknapsack Test Problems for Size Reduction Methods, Investigation Operativa 1, 1990, p. 251-270. 
  9. [FRPL92a] A. FRÉVILLE and G. PLATEAU, An Efficient Preprocessing Procedure for the Solution of the 0-1 Multiknapsack Problem, Proceedings de la conférence "Viewpoints on Optirnization", Grimentz, Suisse, août 1990, à paraître dans Discrete Applied Mathematics. Zbl0802.90077
  10. [FRPL92b] A. FRÉVILLE and G. PLATEAU, FPBK92 : An Implicit Enumeration Code for the Solution of the 0-1 Bidimensional Knapsack Problem Based on Surrogate Duality, Graphs and Optimization Colloquium, Grimentz, Suisse, août 1992. Zbl0782.90069
  11. [FRPL93] A. FRÉVILLE and G. PLATEAU, SADE2 : An Exact Algorithm for Solving the Biknapsack Surrogate Dual, à paraître dans European Journal of Operational Research, 66, 1993. 
  12. [GAPI85] B. GAVISH and H. PIRKUL, Efficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality, Mathematical Programming, 1985, 31, p. 78-105. Zbl0571.90065MR787388
  13. [GLO65] F. GLOVER, A Multiphase Dual Algorithm for the Zero-One Integer Programming Problem Operations Research, 1965, 13 (6), p. 879-919. Zbl0163.41301
  14. [MAMA57] A. S MANNE and H. M. MARKOWITZ, On the Solution of Discrete Programming Problems, Econometrica, 1957, 25, p. 84-110. Zbl0078.34005MR85968
  15. [MATO92] S. MARTELLO and P. TOTH, Exact Solution of Hard Knapsack Problems, EURO XII-TIMS XXXI, Helsinki, Finlande, juin 1992. 
  16. [PET67] C. C. PETERSEN, Computational Experience With Variants of the Balas Algorithm Applied to the Selection for R & D Projects, Management Science, 1967, 13 (9), p. 736-750. 
  17. [SETO68] S. SENJU and Y. TOYODA, An Approach to Linear Programming with 0-1 Variables, Management Science, 1968, 15 (4), p. 196-205. 
  18. [WENE67] H. M. WEINGARTNER and D. N. NESS, Method for the Solution of the Multidimensional 0-1 Knapsack Problem, Operations Research, 1967, 15 (1), p. 83-103. 

NotesEmbed ?

top

You must be logged in to post comments.