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 :

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.