Callcc/Guyslain/Teaching/aro

Version & licenses
Creative Commons License
  1. {`frametitle "Algorithmique et recherche opérationnelle"}
  2. {`menu "guyslain"}
  3. {`leftpicture af://guyslain/images/maths/teaching.png}

  4. {section 3 Cours.}

  5. Voici des {link af://guyslain/teaching/comp566-lecture-notes.pdf notes
  6. de cours} en anglais sur la programmation linéaire. Le contenu ne
  7. correspond pas tout à fait au cours du Master Informatique d'AMU, mais
  8. certaines parties se recoupent.


  9. {section 3 TP.}

  10. Les TP sont organisés en trois devoirs :

  11. + {link af://guyslain/teaching/aro/TP1.pdf Modélisation et résolution} de
  12. problèmes en programmation linéaire avec glpsol (une séance de TP).
  13. + Résoudre le problème du {link af://guyslain/teaching/aro/TP2.pdf
  14. sac-à-dos} avec la technique du branch-and-bound (deux séances de TP).
  15. + Résoudre le problème de la {link af://guyslain/teaching/aro/TP4.pdf
  16. découpe ({emph cutting-stock})} avec la technique de la génération de
  17. colonnes (deux séances de TP).

  18. {section 4 Utilisation de GLPK.}

  19. Pour le problème de découpe, il sera nécessaire d'appeler un solveur
  20. de programme linéaire depuis un programme. Pour cela on utilisera
  21. l'API de glpk. Voici {link af://guyslain/teaching/aro/glpk_example.pdf
  22. un exemple} de programme linéaire résolu avec glpk en C (il est fourni
  23. sous la forme d'un pdf car vous n'êtes pas supposé le copier-coller
  24. !). Vous pouvez y retrouver comment s'utilisent les principales
  25. fonctions de l'API, mais la consultation de la documentation de GLPK
  26. sera de toute façon nécessaire.


  27. {section 4 Instances pour le sac-à-dos.}

  28. Voici des instances du problème de sac-à-dos à résoudre, avec le
  29. nombre de nœuds que mon algorithme a parcouru pour trouver la solution
  30. :

  31. {array 6 4 {`head 1}
  32. fichier { objectif maximum } { nombre de nœuds calculés } { nombre total de nœuds }
  33. {link af://guyslain/teaching/aro/sac0 sac0} 103 62 11017
  34. {link af://guyslain/teaching/aro/sac1 sac1} 2077672 1013 1029114
  35. {link af://guyslain/teaching/aro/sac2 sac2} 2095878 7033 {??? (trop gros pour le calculer)}
  36. {link af://guyslain/teaching/aro/sac3 sac3} 2132531 20605 {??? (encore plus)}
  37. {link af://guyslain/teaching/aro/sac4 sac4} 2166542 210285 {??? (encore plus)}
  38. }


  39. {section 4 Instances pour le problème de découpe.}

  40. Voici des instances pour le problème de découpe. Certaines instances
  41. ont plusieurs largeurs initiales, il faut donc généraliser le
  42. programme pour pouvoir les résoudre. La première instance est celle
  43. dans le sujet.

  44. {array 6 4 {`head 1}
  45. fichier {objectif fractionnaire minimum}
  46. {nombre d'itérations effectuées} {plusieurs initiales ?}
  47. {link af://guyslain/teaching/aro/instance1 instance1} 452.25 2 non
  48. {link af://guyslain/teaching/aro/instance2 instance2} 1048.92 9 oui
  49. {link af://guyslain/teaching/aro/instance3 instance3} 2143.43 14 oui
  50. {link af://guyslain/teaching/aro/instance4 instance4} 1065 89 non
  51. {link af://guyslain/teaching/aro/instance5 instance5} 858.21 18 non
  52. }