Praktische Einführung in Constraint Programming mit CP-SAT und Python

Praktische Einführung in Constraint Programming: CP-SAT und Python

Deklaratives Paradigma

• Constraint Programming (CP) ist ein deklaratives Paradigma zur Lösung diskreter Optimierungsprobleme
• Anders als bei der imperativen Programmierung beschreibt man das gewünschte Ergebnis, und das Programm leitet die Lösung selbst ab
• Am Beispiel der Extraktion einer Liste von Erwachsenen wird der Unterschied zwischen imperativem und deklarativem Ansatz erläutert

Grundlagen des Constraint Programming (CP)

• Modell: die Beschreibung des gewünschten Ergebnisses eines Problems
• Variablen: die zu findenden Werte; jede Variable hat eine Domäne (Menge zulässiger Werte)
• Constraints: beschreiben die Beziehungen zwischen Variablen
• Lösung: eine Zuweisung von Werten zu Variablen, die alle Constraints erfüllt

Praktisches Beispiel mit Python und CP-SAT

• Problem: Erstellen eines wöchentlichen Dienstplans für Mitarbeitende
• Modellerstellung: Mit CP-SAT wird ein leeres Modell erzeugt
• Daten: Definition von Mitarbeitendenliste und Rollen, Arbeitstagen und Schichten
• Variablendefinition: Erzeugung boolescher Variablen, die angeben, ob eine Person arbeitet
• Hinzufügen von Constraints: Entsprechend der Problembeschreibung werden den Variablen Constraints hinzugefügt

Lösen des Modells

• Lösung: Das Modell wird gelöst und ein Ergebnis ermittelt
• Zusätzliche Constraints: Es werden weitere Constraints hinzugefügt, etwa zur Vermeidung von Überstunden, zur Begrenzung der Arbeitszeit bestimmter Mitarbeitender oder zur Vermeidung überlappender Arbeitszeiten bestimmter Personen

Zwischenteil: Lösungsstatus

• Lösungsstatus: Es werden Statuswerte wie optimal, zulässig, unzulässig und unbekannt zurückgegeben
• Beispiel: Anhand eines einfachen Beispiels werden die einzelnen Status erklärt

"Tut mir leid, Emma"

• Unzulässiger Status: Es ist nicht möglich, dass Emma unter der Woche an 5 Tagen frei hat
• Alternativvorschlag: Vorgeschlagen wird, dass Emma nur an 3 Tagen unter der Woche frei hat

Ziel: Gleichmäßige Verteilung der Arbeitszeit

• Ziel hinzufügen: Es wird ein Ziel ergänzt, um die Arbeitszeit gleichmäßig zu verteilen
• Ergebnis: Die Arbeitszeit wird gleichmäßig auf die einzelnen Mitarbeitenden verteilt

Fazit

• Einführung in Grundkonzepte: Die grundlegenden Konzepte des Constraint Programming werden eingeführt und anhand eines praktischen Beispiels erläutert
• Ausblick auf den nächsten Artikel: Im nächsten Beitrag soll gezeigt werden, wie Constraint Programming für die Indexauswahl in Postgres genutzt werden kann

Meinung von GN⁺

• Nutzen von Constraint Programming: Sehr nützlich zur Lösung komplexer Optimierungsprobleme
• Stärken von CP-SAT: CP-SAT, entwickelt als Teil von Googles OR-Tools-Projekt, bietet eine starke Performance
• Praxisnahe Einsatzfälle: Lässt sich auf reale Probleme wie die Erstellung von Dienstplänen anwenden
• Aspekte bei der Einführung der Technologie: Bei der Einführung neuer Technologien sollten Lernkurve und Integrationsfragen mit bestehenden Systemen berücksichtigt werden
• Empfehlung ähnlicher Projekte: Kommerzielle Solver wie IBM CPLEX oder Gurobi bieten ähnliche Funktionen

[GN⁺]

Hacker-News-Kommentare

• Ich habe in der Vergangenheit Constraint Solver verwendet, und diese Tools liefern wirklich erstaunliche Performance.

  • Das Problem ist, dass es kaum Material für Einsteiger gibt.
  • Das meiste Material besteht entweder daraus, wie man Sudoku löst, oder aus hochtechnischen Forschungsunterlagen.
  • Ich wünschte, mehr Tools, mit denen man mehr Probleme lösen kann, wären zugänglicher.
  • Zugänglich bedeutet dabei immer noch, dass man Programmierer braucht.

• Ich schreibe gerade ein kurzes Kapitel aus meinem alten Buch über die Verwendung von MiniZinc und Python neu.

  • MiniZinc ist ein Constraint-Programming-System.
  • Auf Coursera gibt es einen guten Kurs, der MiniZinc verwendet.

• Viele Programme versuchen, eine einzige Datenrepräsentation zu haben, aber das ist in den meisten Fällen unvernünftig.

  • Es erfordert viel Verbiegen, um Algorithmen mit einer neuen Repräsentation zum Laufen zu bringen.
  • Ich bedaure immer, dass Repräsentationen nicht häufiger transformiert werden.
  • Wenn man Repräsentationen transformiert, kann man eine sehr kompakte Darstellung erhalten, die eine schnellere Ausführung ermöglicht.

• Ich habe einen Kunden, der Sportcamps betreibt.

  • Kinder können den Sport angeben, den sie wollen, und Freunde nennen.
  • Das erzeugt ein Terminplanungsproblem, das für Menschen schwierig ist.
  • Ich habe mit einem auf OR-Tools basierenden Optimierungswerkzeug ein einfaches System gebaut.
  • Jetzt ist der Zeitplan mit ein paar Klicks fertig.

• Ich habe Anfang der 2000er viele Solver verwendet.

  • Derzeit arbeite ich an Software (Web) mit Python.
  • Ich freue mich, eine tiefgehende Auseinandersetzung mit diesem Thema zu sehen.
  • Constraints in ein Modell zu übersetzen ist 90 % der Arbeit und der schwierigste Teil.

• Ich frage mich, ob es parametrisches CAD gibt, das hauptsächlich mit Constraint Solvern arbeitet.

  • Es ist oft lästig, anfangs Parameterwerte schätzen zu müssen, die einen nicht interessieren.
  • Stattdessen würde ich lieber die Parameter, die mich interessieren, einschränken und den Rest optimieren.

• Ich frage mich, wie es im Vergleich zu Mixed-Integer Programming abschneidet.