Résolution de programmes linéaires entiers ou mixtes à l'aide de la forme normale de Hermite

J. Maublanc; A. Quilliot

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

  • Volume: 31, Issue: 4, page 399-427
  • ISSN: 0399-0559

How to cite

top

Maublanc, J., and Quilliot, A.. "Résolution de programmes linéaires entiers ou mixtes à l'aide de la forme normale de Hermite." RAIRO - Operations Research - Recherche Opérationnelle 31.4 (1997): 399-427. <http://eudml.org/doc/105158>.

@article{Maublanc1997,
author = {Maublanc, J., Quilliot, A.},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {Hermite normal form decompositions; cutting plane methods; branch and bound methods},
language = {fre},
number = {4},
pages = {399-427},
publisher = {EDP-Sciences},
title = {Résolution de programmes linéaires entiers ou mixtes à l'aide de la forme normale de Hermite},
url = {http://eudml.org/doc/105158},
volume = {31},
year = {1997},
}

TY - JOUR
AU - Maublanc, J.
AU - Quilliot, A.
TI - Résolution de programmes linéaires entiers ou mixtes à l'aide de la forme normale de Hermite
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1997
PB - EDP-Sciences
VL - 31
IS - 4
SP - 399
EP - 427
LA - fre
KW - Hermite normal form decompositions; cutting plane methods; branch and bound methods
UR - http://eudml.org/doc/105158
ER -

References

top
  1. 1. E. B. BALAS, Intersection n-cuts-a new type of cutting planes for integer programming, Operat. Research, 1971, 19, p. 19-39. Zbl0219.90035
  2. 2. F. L. BAUER, Algorithms 153 Gomory; Comunications of the ACM, 1963, 6, p. 68. 
  3. 3. R. BIXBY et W. CUNNINGHAM, Converting linear programs to network problems; Maths of Operat. Research, 1980, 5, p. 321-357. Zbl0442.90095MR594849
  4. 4. V. J. BOWMAN et G. L. NEMHAUSER, A finiteness proof for modified Dantzig cuts in integer programming: Naval Research Log Quarter, 1970, 17, p. 309-313. Zbl0215.59001MR275874
  5. 5. V. J. BOWMAN et G. L. NEMHAUSER, Deep cuts in integer programming; Operat Research, 1971, 8, p. 89-111. MR312902
  6. 6. M. CARTER, A survey on practical applications of examination timetabling algorithms; Operat Research, 1986, 34, 2, p. 193-302. MR861041
  7. 7. A. CHARNES et W. COOPER, Management models and industrial applications of linear programming, J. WILEY and sons, 1961. Zbl0107.37004MR157773
  8. 8. V. CHVATAL, Cutting planes and combinatorics; European Journal of combinatorics, 1985, 6, p. 217-226. Zbl0581.05015MR818595
  9. 9. R. J. DAKIN, A tree search algorithm for mixed integer programming problems, The Computer Journal, 1965, 8, p. 250-255. Zbl0154.42004MR187937
  10. 10. P. D. DAMICH, R. KANNAN et L. TROTTER, Hermite normal form computation using modulo determinant arithmetic: Math. Operat. Research, 1987, 12, 1, p. 50-59. Zbl0624.65036MR882842
  11. 11. J. EDMONDS, F. GILES, Total dual integrality of linear inequality Systems in Progress in Combinatorial Optimization, Acad. Press. Toronto, 1984, p. 117-129. Zbl0555.90078MR771873
  12. 12. D. FAYARD et G. PLATEAU, An efficient algorithm for the 0-1 knapsack problem, R. M. NAUSS, Management Sciences, 1977, 24, p. 918-919. Zbl0806.90089
  13. 13. M. GAREY et D. JOHNSSON, Computer and intractability; W. FREEMAN and Co. N.Y., 1979. Zbl0411.68039
  14. 14. R. GARFINKEL et G. L. NEMHAUSER, Integer programming; J. WILEY and sons, N.Y., 1972. Zbl0259.90022MR381688
  15. 15. A. M. GEOFFRION, Lagrangean relaxation for integer programming; Math Programming Study 2, 1974, p. 82-114. Zbl0395.90056MR439172
  16. 16. F. GLOVER, Generalized cuts in Diophantine programming, Management Sciences 13, 1966-1967, p. 254-268. Zbl0158.18701MR202470
  17. 17. S. GODANO, Méthodes géométriques pour la programmation linéaire, Thèse Université Blaise Pascal, Clermont-Ferrand, 1994. 
  18. 18. R. E. GOMORY, Outlines of an algorithm for integer solutions to linear programs, Bull American Math. Soc., 1958, 64, p. 275-278. Zbl0085.35807MR102437
  19. 19. R. E. GOMORY, An algorithm for integer solutions to linear programs, Recent Advances in Math. programming. (R. L. GRAVES and P. WOLFE Eds.), Mac Graw Hill, N.Y., 1963, p. 269-302. Zbl0235.90038MR174390
  20. 20. M. GONDRAN, Un outil pour la programmation en nombres entiers, la méthode des congruences décroissantes : RAIRO 3, 1973, p. 35-54. Zbl0274.90032MR373598
  21. 21. M. GROTSCHEL, L. LOVACZ et A. SCHRIJVER, The ellipsoid method and combinatorial optimization, Springer-Verlag, Heidelberg, 1986. 
  22. 22. M. HELD et R. KARP, The travelling salesman problem and minimum spanning trees, Operat. Research 18, 1970, p. 1138-1162. Zbl0226.90047MR278710
  23. 23. A. HOFFMAN et J. KRUSKAL, Integral boundary points of integer polyedra in Linear Inequalities and Related Systems, H. KUHN and A. TUCKER Eds., Princeton Univ. Press, 1986, p. 223-246. Zbl0072.37803
  24. 24. R. KANNAN et A. BACHEM, Polynomial algorithms for Computing the Smith and Hermite normal forms of an integer matrix; SIAM Journ. Comput 8, 1979, 4, p. 499-507. Zbl0446.65015
  25. 25. H. LANGMAACK, Algorithm 263 Gomory 1 [H]; Communications of the ACM, 1965, 8, p. 601-602. 
  26. 26. H. LENSTRA, Integer Programming with a flxed number of variables, Maths of Operat. Research, 1983, 8, p. 538-548. Zbl0524.90067
  27. 27. L. G. PROLL, Certification of algorithm 263A [H] Gomory 1, Comm. ACM 13, 1970, p. 326-327. 
  28. 28. I. ROSEMBERG, On Chvatal's cutting planes in integer programming, Mathematische Operation Forschung und Statistik, 1975, 6, p. 511-522. Zbl0324.90046MR403657
  29. 29. A. SCHRIJVER, Theory of linear and integer programming, Wiley, Chichester, 1986. Zbl0970.90052MR874114
  30. 30 A. V. SRINIVASAN, An investigation of some computational aspects of integer programming, JACM 12, 1965, p. 525-535. Zbl0154.42003

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.