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.

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.