Optimierungs-Lab: lineare, ganzzahlige und Constraint-Modelle mit PuLP und OR-Tools in einer privaten Ubuntu-VM

Dieses Lab gibt jeder Schülerin und jedem Schüler die Solver, die ein Team für Operations Research benutzt, in einer einzigen Ubuntu-VM. Sie schreiben eine Entscheidung als Modell, mit einem Ziel und einigen Grenzen, übergeben es einem Solver und lesen die Antwort: zuerst den Status, dann den Plan, dann den Wert jeder Grenze. Zwei Modelle, die sie selbst schreiben, bewertet ein Skript, das sie auf Instanzen ausführt, die sie nie sehen.

Auf dem Computer der Lernenden wird nichts installiert. PuLP mit dem Solver CBC stammt aus dem Ubuntu-Archiv, und OR-Tools von Google mit dem Constraint-Solver CP-SAT wird beim ersten Start der VM von PyPI installiert. Das Modul Operations Research löst seine Aufgaben mit SciPy im JupyterLab-Lab; dieses Lab ist der Ort, an dem die Lernenden die Modellierungswerkzeuge und Solver aus der Praxis kennenlernen.

Was die Lernenden lernen

Wie aus einer Entscheidung ein Modell wird. Ein lineares Programm in PuLP stellt Tische und Stühle aus begrenztem Holz, begrenzten Stunden und begrenztem Lagerplatz her, und der Bericht zeigt den Status, den Plan, den Schlupf jeder Grenze und ihren Schattenpreis, der sagt, von welcher Grenze sich mehr lohnt. Ein ganzzahliges Programm wählt ganze Projekte: Dasselbe Modell wird mit und ohne Bruchteile gelöst, und die erste Antwort zu runden verletzt eine Grenze. Ein CP-SAT-Modell erstellt aus Regeln und Wünschen einen Dienstplan für Pflegekräfte und liest OPTIMAL, FEASIBLE oder INFEASIBLE aus der Antwort des Solvers.

Die fünf Teile

Erstens ein lineares Programm: lp.py wird ausgeführt, Status, Plan und Schattenpreise werden gelesen, dann wird eine Grenze geändert und der Gewinn mit dem Schattenpreis verglichen. Zweitens ganze Zahlen: integer.py löst dieselbe Art Modell mit und ohne Bruchteile. Drittens ein Constraint-Modell: shifts.py erstellt mit CP-SAT einen Dienstplan, und die Lernenden fügen eine Regel hinzu und verletzen einen Wunsch. Viertens die drei Modelle, von Hand geändert. Fünftens zwei Modelle, die sie selbst schreiben, plan.py und rota.py, anhand eines Kommentars, der genau sagt, was jedes lesen und ausgeben muss. Alles, was sie bearbeiten, liegt im Ordner optimisation, und README.md im Home-Ordner sagt, was zu tun ist, und gibt keine Antworten.

Im Browser ausführen

VM-Labs werden in einem Modul als Lab-Aufgabe eingerichtet, und das Beispiel steht auf der Seite des Labs. Die Maschine ist klein: eine CPU, 1 GB Arbeitsspeicher und 10 GB Festplatte. Ein Modell ist in weit weniger als einer Sekunde gelöst.

  1. Lab hinzufügen. Fügen Sie in einem Modul, das Sie unterrichten, eine Aufgabe hinzu und wählen Sie die Karte für das Ubuntu-VM-Lab. Die Seite zeigt statt einer Compose-Datei eine kurze Beschreibung der Maschine.
  2. Mit dem Beispiel beginnen. Die Seite bietet fertige Labs als Ausgangspunkt an. Wählen Sie Optimisation. Ein Beispiel ersetzt den Text, und Rückgängig bringt Ihren eigenen zurück.
  3. Veröffentlichen und die eigene Kopie starten. Veröffentlichen Sie, dann Starten. Das Setup-Skript des Labs installiert PuLP, die Solver CBC und GLPK sowie OR-Tools aus dem Ubuntu-Archiv und von PyPI und schreibt den Hilfsbefehl opt, die Modelle zum Arbeiten und die README, beim ersten Start der VM, in ein bis zwei Minuten.
  4. Das Terminal öffnen. Öffnen Sie das Terminal und lesen Sie README.md im Home-Ordner. Im Browser öffnet sich nichts: Das Lab ist das Terminal.

Eine Basislektion zu diesem Lab

Optimisation Basics ist eine kleine Lektion, die in diesem Lab, einer Ubuntu-VM, durchgeführt wird. Sie hat einen Einstieg, ein Ziel in der Form „Ich kann“, Schlüsselwörter, eine Startfrage, eine Kontrolle nach jeder Idee, einen häufigen Fehler und eine Abschlusskontrolle, und jeder Schritt hat eine Schaltfläche Ausführen, die seinen Befehl in das Terminal der Maschine tippt. Die Lernenden führen das lineare Programm aus und lesen seine Schattenpreise, führen das ganzzahlige Programm aus, um zu sehen, warum Runden scheitert, und führen den Dienstplan aus.

Die Lektion verschafft nur einen Überblick und überlässt die eigentliche Aufgabe des Labs, die beiden Modelle, den Lernenden, sodass sie keine Antworten verrät.

Wie bewertet wird

Das Lab hat eine Prüfung. Sie läuft auf einer Kopie der gespeicherten Maschine und führt plan.py auf drei Projektauswahl-Instanzen aus, die sie frisch erzeugt. Der ausgegebene Gewinn muss der bestmögliche sein, den die Prüfung durch Ausprobieren aller Pläne findet, der Plan muss Budget und Stunden einhalten, und die Schranke muss dem Wert entsprechen, den ein anderer Solver, GLPK, für dasselbe Modell mit erlaubten Bruchteilen ermittelt. Sie führt rota.py auf zwei frisch erzeugten Dienstplänen und auf einem unmöglichen aus: Die Kosten müssen die kleinste Zahl verletzter Wünsche sein, die die Prüfung mit einem anderen Verfahren berechnet, jede Regel des Dienstplans wird geprüft, und der unmögliche muss INFEASIBLE ausgeben. Die Programme laufen als die Lernenden, und die Prüfung zählt, dass jedes wirklich einen Solver aufgerufen hat. Ein Programm, das ein anderes Programm startet oder weder PuLP noch OR-Tools verwendet, wird abgelehnt. Die erste Zeile der Ausgabe der Prüfung sagt, warum.

  1. Verteilen. Weisen Sie das Lab wie jede Aufgabe zu, auf Wunsch mit Abgabefrist. Jede Schülerin und jeder Schüler bekommt eine eigene VM, die zwischen den Sitzungen erhalten bleibt.
  2. Die Prüfung ausführen. Drücken Sie in der Zeile einer Schülerin oder eines Schülers in der Klassenliste auf Prüfung ausführen. Sie startet eine Kopie der gespeicherten Maschine, die nicht zurückgespeichert wird, führt das Prüfskript des Labs als root aus und zeigt, ob es bestanden wurde, was es ausgegeben hat und wann. Die Schülerin oder der Schüler erfährt das Ergebnis nicht.
  3. Bewerten. Lesen Sie die erste Zeile dessen, was die Prüfung ausgegeben hat: Sie sagt, was nicht stimmt, etwa einen besten Plan, der weniger wert ist als der beste, oder einen Dienstplan, der mehr Wünsche verletzt als nötig. Geben Sie die Arbeit mit einer Begründung zurück, wenn mehr nötig ist.

Die Definition auf GitHub

Die Datei ist die ganze Lab-Definition, derselbe Text, den die Plattform ausführt: Größe, Setup-Skript, Hilfsbefehl, die Modelle zum Arbeiten, die README und die Prüfung. Kopieren Sie sie und ändern Sie die Zahlen oder die Probleme, um ein längeres Lab zu machen.

Dieses Lab ausprobieren, und was es kostet

Mit einem kostenlosen persönlichen Konto können Sie die Grundlagenlektionen in diesem Lab durcharbeiten, mit genug kostenlosem Guthaben pro Monat für die meisten Lektionen und ohne Karte. Für eine Klasse sind die ersten 365 Tage für eine Schule kostenlos, für bis zu 50 Lernende; danach zahlt sie je lernender Person und Jahr, alle Labs inklusive und Lehrkräfte kostenlos.

Häufige Fragen

Braucht das Lab eine Lizenz?
Nein. OR-Tools steht unter Apache-2.0, PuLP unter MIT, und die Solver CBC und GLPK sind Open Source (EPL und GPL). Sie werden beim Start auf der VM der Lernenden aus dem Ubuntu-Archiv und von PyPI installiert, wir verteilen also keinen davon.
Warum zwei Werkzeuge, und wie unterscheidet sich das von SciPy im Modul Operations Research?
PuLP schreibt lineare und ganzzahlige Programme und übergibt sie einem Solver wie CBC. OR-Tools CP-SAT ist ein Constraint-Solver, gut für Dienstpläne, Stundenpläne und Touren. linprog aus SciPy löst nur lineare Programme. Das Modul lehrt die Methode mit SciPy, und dieses Lab lässt die Lernenden die Werkzeuge ausführen, die für größere Probleme und für ganze Zahlen verwendet werden.
Können die Lernenden etwas kaputt machen?
Nur ihre eigene Kopie. Die Maschine eines Besuchers ohne Konto erreicht das Ubuntu-Archiv und den Python-Paketindex und sonst nichts, und wenn jemand eine Datei kaputt macht, stellt opt reset sie so wieder her, wie sie ausgegeben wurde.
Wurde das Lab in einer echten Schüler-VM getestet?
Das Setup, die Befehle der Lektion und die Prüfung, mit jeder Art, sie zu täuschen, liefen in einem echten Ubuntu-26.04-Container, der die VM vertritt, auf einem arm64-Rechner. PyPI hat OR-Tools-Pakete für arm64 und amd64, aber eine gestartete Schüler-VM und die amd64-Installation sollten Sie vor einer Stunde einmal ausprobieren.