Lab Optimisation : modèles linéaires, en nombres entiers et sous contraintes avec PuLP et OR-Tools dans une VM Ubuntu privée

Ce lab donne à chaque élève les solveurs qu’utilise une équipe de recherche opérationnelle, dans une seule VM Ubuntu. L’élève écrit une décision sous forme de modèle, un objectif et des limites, la confie à un solveur et lit la réponse : d’abord le statut, puis le plan, puis ce que vaut chaque limite. Deux modèles écrits par l’élève sont notés par un script qui les exécute sur des instances que l’élève ne voit jamais.

Rien n’est installé sur l’ordinateur de l’élève. PuLP avec le solveur CBC vient de l’archive d’Ubuntu, et OR-Tools de Google, avec son solveur de contraintes CP-SAT, s’installe depuis PyPI dans la VM au premier démarrage. Le module de recherche opérationnelle résout ses problèmes avec SciPy dans le lab JupyterLab ; ce lab est l’endroit où l’élève rencontre les outils de modélisation et les solveurs employés en pratique.

Ce que les élèves apprennent

Comment une décision devient un modèle. Un programme linéaire en PuLP fabrique des tables et des chaises avec du bois, des heures et un espace de stockage limités, et le rapport donne le statut, le plan, la marge de chaque limite et son prix fantôme, qui dit pour quelle limite il vaut la peine d’en avoir plus. Un programme en nombres entiers choisit des projets entiers : le même modèle est résolu avec et sans fractions, et arrondir la première réponse enfreint une limite. Un modèle CP-SAT construit un planning d’infirmières à partir de règles et de souhaits, et lit OPTIMAL, FEASIBLE ou INFEASIBLE dans la réponse du solveur.

Les cinq parties

D’abord un programme linéaire : lp.py est lancé, son statut, son plan et ses prix fantômes sont lus, puis une limite est modifiée et le gain est comparé au prix fantôme. Deuxièmement les nombres entiers : integer.py résout le même genre de modèle avec et sans fractions. Troisièmement un modèle sous contraintes : shifts.py construit un planning avec CP-SAT, et l’élève ajoute une règle et en enfreint une. Quatrièmement les trois modèles modifiés à la main. Cinquièmement deux modèles que l’élève écrit, plan.py et rota.py, à partir d’un commentaire qui dit exactement ce que chacun doit lire et afficher. Tout ce que l’élève modifie est dans le dossier optimisation, et README.md dans le dossier personnel dit quoi faire et ne donne aucune réponse.

Le lancer dans votre navigateur

Les labs VM se donnent comme tâche de lab dans un module, et l’exemple se trouve sur la page du lab. La machine est petite : un processeur, 1 Go de mémoire et 10 Go de disque. Un modèle se résout en bien moins d’une seconde.

  1. Ajouter le lab. Dans un module que vous enseignez, ajoutez une tâche et choisissez la carte Lab VM Ubuntu. La page affiche une courte description de la machine au lieu d’un fichier compose.
  2. Partir de l’exemple. La page propose des labs prêts à l’emploi pour démarrer. Choisissez Optimisation. Utiliser un exemple remplace le texte, et Annuler rend le vôtre.
  3. Publier et démarrer votre propre copie. Publiez, puis Démarrez. Le script setup du lab installe PuLP, les solveurs CBC et GLPK et OR-Tools depuis l’archive d’Ubuntu et depuis PyPI, et écrit la commande d’aide opt, les modèles de travail et le README, au premier démarrage de la VM, en une minute ou deux.
  4. Ouvrir le terminal. Ouvrez son terminal et lisez README.md dans le dossier personnel. Rien ne s’ouvre dans le navigateur : le lab, c’est le terminal.

Une leçon de base sur ce lab

Optimisation Basics est une petite leçon donnée dans ce lab, une VM Ubuntu. Elle a une accroche, un objectif « Je peux », des mots-clés, une question de départ, une vérification après chaque idée, une erreur courante et une vérification finale, et chaque étape a un bouton Exécuter qui tape sa commande dans le terminal de la machine. L’élève lance le programme linéaire et lit ses prix fantômes, lance le programme en nombres entiers pour voir pourquoi l’arrondi échoue, puis lance le planning.

La leçon regarde autour d’elle et laisse à l’élève la tâche propre au lab, les deux modèles : elle ne donne donc aucune réponse.

Comment il est noté

Le lab a une vérification. Elle s’exécute sur une copie de la machine enregistrée et lance plan.py sur trois instances de choix de projets tirées à chaque fois. Le gain affiché doit être le meilleur possible, ce que la vérification trouve en essayant tous les plans, le plan doit respecter le budget et les heures, et la borne doit correspondre à ce que vaut le même modèle avec fractions selon un autre solveur, GLPK. Elle lance rota.py sur deux plannings d’infirmières tirés à chaque fois et sur un planning impossible : le coût doit être le plus petit nombre de souhaits rompus, que la vérification calcule par une autre méthode, chaque règle du planning est contrôlée, et le cas impossible doit afficher INFEASIBLE. Les programmes s’exécutent sous le compte de l’élève, et la vérification compte que chacun a bien appelé un solveur. Un programme qui en lance un autre, ou qui n’utilise ni PuLP ni OR-Tools, est refusé. La première ligne de ce que la vérification a affiché dit pourquoi.

  1. Le distribuer. Attribuez le lab comme n’importe quelle tâche, avec une échéance si vous le souhaitez. Chaque élève reçoit une VM à lui, conservée d’une séance à l’autre.
  2. Lancer la vérification. Sur la ligne d’un élève dans la liste de la classe, appuyez sur Lancer la vérification. Elle démarre une copie de sa machine enregistrée, qui n’est pas sauvegardée ensuite, exécute le script de vérification du lab en root et indique s’il a réussi, ce qu’il a affiché et quand. L’élève n’est pas informé du résultat.
  3. Noter. Lisez la première ligne de ce que la vérification a affiché : elle dit ce qui ne va pas, par exemple un meilleur plan qui vaut moins que le vrai meilleur, ou un planning qui rompt plus de souhaits que nécessaire. Renvoyez le travail avec un motif s’il faut aller plus loin.

La définition sur GitHub

Le fichier est toute la définition du lab, le texte même que la plateforme exécute : taille, script setup, commande d’aide, modèles de travail, README et vérification. Copiez-le et changez les nombres ou les problèmes pour faire un lab plus long.

Essayer ce lab, et ce qu’il coûte

Un compte personnel gratuit permet de suivre les leçons de base de ce lab, avec chaque mois assez de crédit gratuit pour suivre la plupart des leçons, sans carte. Pour une classe, un établissement a ses 365 premiers jours gratuits pour 50 élèves au plus, puis paie par élève et par an, tous les labs compris et les enseignants gratuits.

Questions fréquentes

Le lab demande-t-il une licence ?
Non. OR-Tools est sous licence Apache-2.0, PuLP sous licence MIT, et les solveurs CBC et GLPK sont libres (EPL et GPL). Ils sont installés dans la VM de l’élève à son démarrage, depuis l’archive d’Ubuntu et depuis PyPI : nous n’en distribuons aucun.
Pourquoi deux outils, et en quoi est-ce différent de SciPy dans le module de recherche opérationnelle ?
PuLP écrit des programmes linéaires et en nombres entiers et les confie à un solveur comme CBC. OR-Tools CP-SAT est un solveur de contraintes, adapté aux plannings, aux emplois du temps et aux tournées. linprog de SciPy ne résout que des programmes linéaires. Le module enseigne la méthode avec SciPy, et ce lab permet de lancer les outils utilisés pour des problèmes plus gros et pour les nombres entiers.
Les élèves peuvent-ils casser quelque chose ?
Seulement leur propre copie. La machine d’un visiteur sans compte joint l’archive d’Ubuntu et l’index des paquets Python, et rien d’autre, et si un élève abîme un fichier, opt reset le remet comme il a été donné.
Le lab a-t-il été testé dans une vraie VM d’élève ?
Le script setup, les commandes de la leçon et la vérification, avec chaque façon de la tromper, ont été exécutés dans un vrai conteneur Ubuntu 26.04 qui tient lieu de VM, sur une machine arm64. PyPI propose des paquets OR-Tools pour arm64 et pour amd64, mais une VM d’élève démarrée et l’installation amd64 méritent un essai avant un cours.