Htmligure
Version & licenses
Creative Commons License

Algorithmique et recherche opérationnelle

Cours.

Voici des notes de cours en anglais sur la programmation linéaire. Le contenu ne correspond pas tout à fait au cours du Master Informatique d'AMU, mais certaines parties se recoupent.

TP.

Les TP sont organisés en trois devoirs :

  1. Modélisation et résolution de problèmes en programmation linéaire avec glpsol (une séance de TP).
  2. Résoudre le problème du sac-à-dos avec la technique du branch-and-bound (deux séances de TP).
  3. Résoudre le problème de la découpe (cutting-stock) avec la technique de la génération de colonnes (deux séances de TP).

Utilisation de GLPK.

Pour le problème de découpe, il sera nécessaire d'appeler un solveur de programme linéaire depuis un programme. Pour cela on utilisera l'API de glpk. Voici un exemple de programme linéaire résolu avec glpk en C (il est fourni sous la forme d'un pdf car vous n'êtes pas supposé le copier-coller !). Vous pouvez y retrouver comment s'utilisent les principales fonctions de l'API, mais la consultation de la documentation de GLPK sera de toute façon nécessaire.

Instances pour le sac-à-dos.

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

fichier objectif maximum nombre de nœuds calculés nombre total de nœuds
sac0 1036211017
sac1 207767210131029114
sac2 20958787033 ??? (trop gros pour le calculer)
sac3 213253120605 ??? (encore plus)
sac4 2166542210285 ??? (encore plus)

Instances pour le problème de découpe.

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

fichier objectif fractionnaire minimum nombre d'itérations effectuées plusieurs initiales ?
instance1 452.252
non instance2 1048.92
9oui instance3 2143.4
314oui instance4
106589non instance5
858.2118non