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

 (pganalyze.com)
1 Punkte von GN⁺ 2024-07-05 | 1 Kommentare | Auf WhatsApp teilen
  • Constraint Programming (CP) ist ein deklarativer Ansatz für diskrete Optimierungsprobleme: Statt sie mit prozeduralem Code zu beschreiben, werden sie mit Variablen, Domänen und Constraints modelliert, sodass der Solver eine Lösung findet, die die Bedingungen erfüllt.
  • Der Kern eines Modells besteht aus Variablen als gesuchte Werte, Domänen als Bereich möglicher Werte und Constraints, die die Beziehungen zwischen den Variablen einschränken; bei Bedarf kann mit einer Zielfunktion eine bessere Lösung ausgewählt werden.
  • Das Beispiel zur Aufteilung der Bonbonkosten zwischen Alice, Bob und Carol zeigt mit alldifferent, maximum und minimize, wie eine gültige Lösung zu einer ausgewogeneren Lösung verbessert werden kann.
  • Das Praxisbeispiel erstellt mit dem Open-Source-Solver CP-SAT aus Google OR-Tools und Python einen wöchentlichen Dienstplan für 4 Mitarbeitende mit 7 Tagen, 3 Schichten und 2 Rollen.
  • Dem gleichen Modell lassen sich schrittweise Bedingungen wie eine Obergrenze von 40 Wochenstunden, Unterrichtszeiten, unzulässige Kombinationen von Mitarbeitenden, eine gleichmäßige Verteilung von Wochenenddiensten, Urlaubsanfragen und eine Minimierung von Unterschieden bei der Anzahl der Schichten hinzufügen.

Grundlegende Denkweise des Constraint Programming

  • Constraint Programming (CP) ist ein deklaratives Paradigma zur Lösung diskreter Optimierungsprobleme.
  • In der imperativen Programmierung wird das Verfahren zum Erreichen eines Ergebnisses Schritt für Schritt beschrieben, während der deklarative Ansatz die Bedingungen des gewünschten Ergebnisses formuliert und das Ausführungssystem dieses Ergebnis finden lässt.
  • Im Beispiel zum Ermitteln einer Liste von Erwachsenen würde imperativer Code eine Personenliste durchlaufen und Age >= 18 prüfen, während deklaratives SQL die Bedingung direkt ausdrückt, etwa mit SELECT person_name FROM people WHERE age >= 18;.
  • Auch CP beschreibt das gewünschte Ergebnis als Modell; die zentralen Bestandteile sind Variablen, Domänen und Constraints.
    • Variablen geben an, was gesucht wird.
    • Domänen sind die Mengen von Werten, die Variablen annehmen können.
    • Constraints begrenzen die Beziehungen zwischen Variablen.

Variablen, Domänen, Constraints und Zielfunktion

  • Eine Lösung ist eine Belegung, bei der jede Variable einen Wert aus ihrer Domäne annimmt und gleichzeitig alle Constraints erfüllt.
  • Das Beispiel mit den Bonbonkosten beschreibt das Problem, dass Alice, Bob und Carol jeweils höchstens 20 Dollar haben und gemeinsam Geld für Bonbons im Wert von 50 Dollar sammeln.
    • Die Variablen a, b, c sind die Beträge, die jede Person bezahlt.
    • Die Domäne aller drei Variablen ist {0, ..., 20}.
    • Mit a + b + c == 50 wird die Gesamtsumme festgelegt.
    • Mit a >= b wird erzwungen, dass Alice mindestens so viel wie Bob zahlt.
    • Mit c % 5 == 0 wird Carols Betrag auf Vielfache von 5 beschränkt.
    • Damit nicht zwei Personen den gleichen Betrag zahlen, können a != b, a != c und b != c gesetzt werden.
  • Bedingungen über mehrere Variablen hinweg lassen sich als globale Constraints (global constraints) ausdrücken; alldifferent(a, b, c) stellt sicher, dass alle drei Variablen unterschiedliche Werte haben.
  • Der Solver nimmt das Modell als Eingabe und gibt eine gültige Lösung zurück.
    • Eine Beispiellösung a = 19, b = 11, c = 20 erfüllt alle Constraints.
    • Allerdings zahlt Carol fast doppelt so viel wie Bob, daher könnte es eine ausgewogenere Lösung geben.
  • Eine Zielfunktion minimiert oder maximiert unter den zulässigen Lösungen einen bestimmten Ausdruck.
    • Eine neue Variable x steht für den größten Einzelbeitrag, zusammen mit maximum(x, [a, b, c]).
    • Mit minimize: x erhält man a = 18, b = 17, c = 15, x = 18.
    • Die Differenz zwischen dem größten und dem kleinsten Beitrag sinkt dadurch von 9 Dollar auf 3 Dollar.

Ein Dienstplanmodell mit CP-SAT und Python erstellen

  • Das Praxisbeispiel behandelt die Erstellung eines wöchentlichen Dienstplans für ein kleines Geschäft.
    • Das Geschäft ist täglich von 8 bis 20 Uhr geöffnet.
    • Ein Tag besteht aus drei Schichten: Morning, Afternoon und Evening, jeweils 4 Stunden lang.
    • Es gibt zwei Rollen: Cashier und Restocker.
    • Die Mitarbeitenden sind Phil, Emma, David und Rebecca.
  • CP-SAT ist ein Open-Source-CP-Solver in Google OR-Tools.
  • Ein leeres Modell wird mit ortools.sat.python und cp_model.CpModel() erzeugt.
  • Die möglichen Rollen pro Mitarbeitendem sind wie folgt:
    • Phil: Restocker
    • Emma: Cashier, Restocker
    • David: Cashier, Restocker
    • Rebecca: Cashier
  • Der Dienstplan wird als boolesche Variablen dargestellt, die Mitarbeitende, Rolle, Wochentag und Schicht kombinieren.
    • schedule["Emma"]["Restocker"]["Monday"]["Evening"] ist 1, wenn Emma am Montag in der Evening-Schicht als Restocker arbeitet, sonst 0.
    • model.new_bool_var() erzeugt eine Variable mit der Domäne {0, 1}.

Grundlegende Schicht-Constraints

  • Da in jedem Zeitslot genau eine Kassierkraft benötigt wird, muss für jeden Wochentag und jede Schicht die Summe der Cashier-Rollen 1 sein.
  • Für das Einräumen der Waren wird pro Tag nur eine Schicht benötigt, daher wird für jeden Wochentag die Gesamtsumme der Restocker-Rolle auf 1 gesetzt.
  • Damit auf eine Restocker-Evening-Schicht am Vortag nicht direkt eine Restocker-Morning-Schicht am nächsten Tag folgt, wird die Summe dieser beiden Zuweisungen auf höchstens 1 begrenzt.
  • Eine Person darf in derselben Schicht nicht gleichzeitig zwei Rollen übernehmen, daher muss die Summe der Rollen pro Mitarbeitendem, Wochentag und Schicht höchstens 1 sein.
  • Damit keine unqualifizierten Rollen zugewiesen werden, werden alle Variablen für Rollen, die eine Person nicht übernehmen kann, fest auf 0 gesetzt.
  • Die maximale Arbeitszeit pro Tag beträgt 8 Stunden, also 2 Schichten.
    • Wenn Morning und Evening am selben Tag zugleich zugewiesen würden, entstünde in der Afternoon-Zeit eine 4-stündige Leerlaufphase.
    • Deshalb wird die Summe der Morning- und Evening-Zuweisungen pro Mitarbeitendem und Tag auf höchstens 1 begrenzt, um sowohl mehr als 2 Schichten pro Tag als auch diese Leerlaufzeit dazwischen zu verhindern.

Solver ausführen und erstes Ergebnis

  • Zum Lösen des Modells wird cp_model.CpSolver() erstellt und solver.solve(model) aufgerufen.
  • Nachdem eine Lösung gefunden wurde, werden die Werte der schedule-Variablen mit solver.value(...) ausgelesen.
  • Der erste Dienstplan erfüllt alle grundlegenden Constraints, führt aber dazu, dass Rebecca in einer Woche 14 Schichten übernimmt.
  • Um Überstunden zu vermeiden, wird ein Constraint ergänzt, das die Wochenarbeitszeit pro Person auf höchstens 40 Stunden, also 10 Schichten, begrenzt.
  • Phil ist Vollzeitstudent, arbeitet deshalb genau 4 Schichten pro Woche und kann an Werktagen wegen seines Unterrichts nicht in Morning- und Afternoon-Schichten arbeiten.
  • Damit Phil und Emma nicht in derselben Schicht arbeiten, wird für jeden Wochentag und jede Schicht die Summe ihrer Zuweisungen auf höchstens 1 begrenzt.
  • Da Wochenenddienste bei allen unbeliebt sind, wird festgelegt, dass die insgesamt 8 Schichten an Samstag und Sonntag auf die vier Mitarbeitenden mit jeweils 2 Schichten verteilt werden.

Lösungsstatus: OPTIMAL, INFEASIBLE, FEASIBLE, UNKNOWN

  • Der Solver gibt für ein Modell einen Status und eine Lösung zurück.
  • OPTIMAL bedeutet, dass eine Lösung gefunden wurde, für die es keine bessere gibt.
    • Wenn zum Beispiel x + y >= 5 gilt und x + y minimiert werden soll, ist (x, y) = (5, 0) eine optimale Lösung.
    • Auch (x, y) = (3, 2) kann optimal sein, weil der Zielfunktionswert derselbe ist.
  • INFEASIBLE bedeutet, dass es keine Belegung der Variablen gibt, die alle Constraints erfüllt.
    • Wenn zum Beispiel x ∈ {0, ..., 10} gilt, aber x >= 15 gefordert wird, ist das unmöglich.
  • Wenn der Solver bei großen Problemen oder komplexen Zielfunktionen wegen eines Zeitlimits abgebrochen wird, sind zwei Status möglich.
    • FEASIBLE: Es wurde eine zulässige Lösung gefunden, aber es ist unklar, ob sie optimal ist.
    • UNKNOWN: Es wurde keine Lösung gefunden, und es ist auch nicht bekannt, ob überhaupt eine existiert.

Urlaubsanfragen und faire Verteilung

  • Wenn als Constraint hinzugefügt wird, dass Emma von Montag bis Freitag frei haben möchte, wird der Solver-Status INFEASIBLE.
    • Der Dienstplan lässt sich dann nicht mehr füllen, ohne andere Constraints zu verletzen.
  • Wird die Bedingung so geändert, dass Emma nur von Montag bis Mittwoch frei haben möchte, kann ein Dienstplan erstellt werden.
    • Phil arbeitet wie gewünscht genau 4 Schichten.
    • Emma übernimmt 6 Schichten, David 10 und Rebecca 8.
  • Um die Schichtanzahl zwischen Emma, David und Rebecca gleichmäßiger zu verteilen, wird eine Zielfunktion hinzugefügt.
    • Es werden Ganzzahlvariablen total_shifts erstellt, die die Gesamtzahl der Schichten je Mitarbeitendem darstellen.
    • Mit model.new_int_var(0, 10, ...) werden Integer-Variablen mit Werten von 0 bis 10 erzeugt.
    • Da Phil in Teilzeit arbeitet, wird er ausgeschlossen; mit model.add_min_equality(...) und model.add_max_equality(...) werden die minimale und maximale Schichtanzahl verfolgt.
    • Mit model.minimize(max_shifts - min_shifts) wird die Differenz zwischen der maximalen und der minimalen Schichtanzahl minimiert.
  • Das Endergebnis sind 4 Schichten für Phil, 6 für Emma, 9 für David und 9 für Rebecca.
    • Emma kommt auf 6 Schichten, weil sie 3 Tage frei hat.
    • David und Rebecca werden mit jeweils 9 Schichten gleich verteilt.

Beispielcode und nächstes Thema

  • Dieses Modell erzeugt einen Dienstplan, der sowohl die Anforderungen des Ladenbesitzers als auch die der Mitarbeitenden erfüllt.
  • In dasselbe CP-Modell können fortlaufend weitere Constraints eingebaut werden, um zu prüfen, ob Anforderungen überhaupt umsetzbar sind, und um unter den möglichen Lösungen per Zielfunktion eine fairere Verteilung zu finden.
  • Der Beispielcode ist auf pganalyze GitHub veröffentlicht.
  • Im nächsten Artikel geht es darum, wie Constraint Programming in Postgres zur Auswahl von Indizes eingesetzt werden kann.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-07-05
Meinungen auf Hacker News

  • Ich habe früher einmal Constraint Solver verwendet, und es wirkte wirklich magisch, was man damit alles tun kann. Das Problem ist, dass es nicht viele Materialien gibt, die für Einsteiger geeignet sind.
    Meist geht es entweder darum, Sudoku zu lösen (das Hello World dieses Bereichs), oder es handelt sich um hochgradig technische Primärliteratur für Domain-Experten.
    Schade ist das, weil man mit solchen Tools wohl enorm viele Probleme lösen könnte, wenn sie zugänglicher wären. Mit „zugänglich“ ist hier weiterhin gemeint, dass man Programmierer braucht; ein Problem in eine Constraint-DSL zu gießen, ist nichts, worin die meisten Menschen gut sind.

    • Ich denke, der Grund, warum solche Tools nicht ausreichend zugänglich sind, liegt vor allem darin, dass die meisten Solver auf Mixed-Integer Programming (MIP) basieren und man die Domäne daher als mathematische Gleichungen formulieren muss. Dafür müssen Nutzer sowohl die Domäne als auch die Mathematik verstehen, um Constraints korrekt ausdrücken zu können.
      Allerdings sind MIP-Solver nicht die ganze Welt. Es gibt auch Constraint Solver auf Basis von Local Search, und dieser Ansatz hat nicht die Einschränkung, dass alle Constraints als Beziehungen oder Gleichungen zwischen Integer-Variablen modelliert werden müssen.
      Bei Local-Search-Solvern behandelt man Constraints im Wesentlichen als Blackbox, die angibt, wie gut eine bestimmte Lösung ist. Deshalb ist es schwierig, eine optimale Lösung zu garantieren, ohne alle möglichen Lösungen zu testen; dafür findet man in vernünftiger Zeit meist annähernd optimale Lösungen.
      Timefold Solver ist einer dieser Local-Search-basierten Solver. Nutzer annotieren ihre Domäne, damit der Solver die Variablen und möglichen Werte kennt. Dadurch arbeiten Constraints nicht mit int, sondern mit Shift und Employee, und man kann auch auf deren Methoden zugreifen.
      Offenlegung: Ich arbeite an Timefold Solver.
    • Genau das stimmt. Die eigentliche Syntax oder API von Constraint Solvern ist so einfach, dass man sie schnell lernen kann. Der Teil, der wirklich Zeit und Expertise erfordert, ist es, das Problem auf diese Weise zu modellieren; Beispiele mit realistischem Umfang und realistischer Komplexität gibt es praktisch kaum.
      Ich habe etwa fünf Jahre Erfahrung damit, Scheduling-Probleme mit MiniZinc zu lösen, aber leider ist der gesamte Code proprietär und wird nicht als Open Source veröffentlicht werden.
      Ich würde gern ein vollständiges Beispiel für Constraint Programming erstellen, inklusive Containerisierung, Visualisierung und Modellierung, aber die Hürde ist, ein tatsächlich lohnendes Problem zu finden, für das nutzbare Open-Source-Daten existieren.
    • Ich stimme zu, dass die Reduktion viel schwieriger ist als die Theorie selbst. Dennis Yurichevs „SAT/SMT by Example“ (https://smt.st/) ist eine gute Ressource zu diesem Thema, aber ziemlich einschüchternd.
    • Die Aussage „die meisten Materialien sind entweder Sudoku-Lösen oder Forschungsliteratur nur für Domain-Experten“ trifft es genau. Ich wollte einen SAT-Solver in einer Rule Engine verwenden, hatte aber überhaupt kein Gefühl dafür, wie man das machen sollte.
      Nach einigem Herumüberlegen habe ich zwar einen grundlegenden Proof of Concept gebaut, konnte ihn aber nicht auf das tatsächlich benötigte Niveau skalieren. Die Lücke zwischen einer Spielzeugimplementierung und etwas Substanziellerem war sehr groß.
    • Ich habe lange programmiert, bin aber inzwischen etwas eingerostet. Letztes Jahr habe ich mit Googles OR-Tools einen Optimierer für Fußballteams gebaut, mit Auswahl-Constraints wie „mit einem Freund zusammenspielen“ und Bedingungen wie dem Ausbalancieren der Spielstärke zwischen Teams.
      Ein LLM war hilfreich, um mich recht schnell grob in die richtige Richtung zu bringen. Es schafft es derzeit nicht, alles exakt richtig zu machen, aber es hat mir genug geholfen, damit ich den Rest anschließend selbst fertigstellen konnte.

  • Der Kern von all dem besteht darin zu lernen, wie man etwas in eine Form modelliert, die man an einen Solver übergeben kann. Danach kommt die Frage, wie man die gefundene Lösung so ausdrückt, dass Menschen sie verstehen.
    Schade ist, dass die meisten Programme Daten nur in einer einzigen Darstellung halten wollen und damit gegen diese Denkweise arbeiten. In den meisten Fällen ist das nicht sinnvoll, und es entstehen viele Verrenkungen, um Algorithmen an die neue Darstellung anzupassen.
    Der Artikel berührt das am Anfang kurz beim Thema deklarative Ansätze. Ich bereue ständig, dass mein Code nicht häufiger zwischen Darstellungen transformiert. Damit kann man sehr knappe Darstellungen erhalten, und durch diese Knappheit bekommt man den doppelten Vorteil, dass es oft auch schneller wird.
    Natürlich ist mir klar, dass das letztlich viele Datenpipelines beschreibt: Strukturen, in denen man die meiste Zeit damit verbringt, Daten zu transformieren und an verschiedene Berechnungsorte zu verzweigen.

  • In einem meiner früheren Bücher, das ich derzeit neu schreibe, gibt es ein kurzes Kapitel zur Verwendung von MiniZinc in Python: https://leanpub.com/pythonai/read#constraint-programming-wit...
    MiniZinc ist ein Constraint-Programming-System. Es gibt auch einen guten Coursera-Kurs, der MiniZinc verwendet.

    • Ich würde gern wissen, ob es einen Link zum Coursera-Kurs gibt.

  • Nach meinem Studium der Ökonometrie habe ich Anfang der 2000er in einem Masterstudium zu Operations Research viel mit Solvern gearbeitet. Heute arbeite ich im Bereich Websoftware mit Python, und es freut mich, einen tiefgehenden Artikel zu diesem Thema zu sehen.
    Ich mag dieses Thema, und beim Lesen kamen viele Erinnerungen zurück. Mir wurde auch wieder klar, dass das Überführen der Constraints in ein Modell (Variablen, Struktur usw.) 90 % der Arbeit ausmacht und der schwierigste Teil ist.

    • Im Master habe ich ein Programm namens GAMS verwendet.
      Die Syntaxstruktur ist vollständig im Freiformat.
      https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
    • Beim Überführen von Constraints in ein Modell können LLMs ziemlich hilfreich sein. Ich wollte einmal einen Adapter ausprobieren, der von einem LLM in ein Constraint-Modell übersetzt.
      Das wirkt wie eine ziemlich leicht zu erntende Frucht, aber ich frage mich, ob auch andere davon profitieren würden.
    • Ich glaube, der schwierigste Teil ist, Probleme in einer Produktionsumgebung minimiert laufen zu lassen. Es dauert lange, das zu skalieren und robust gegenüber Datenänderungen zu machen.

  • Es gibt einen Kunden, der ein Sportcamp für Kinder betreibt. Die Kinder können angeben, welche Sportarten sie machen möchten und mit welchen Freunden sie in derselben Gruppe sein wollen.
    Dadurch entstand ein Scheduling-Problem, das für Menschen schwer zu lösen war; früher flossen jedes Jahr mehrere Wochen Arbeitszeit in diese Aufgabe. Wir haben ein einfaches System gebaut, das die Kundendaten an einen auf OR-Tools basierenden Optimierer anschließt, und jetzt ist die Planung mit ein paar Klicks erledigt.

    • Stimmt. Wenn man Daten, Constraints und Nutzenfunktion korrekt ins System einspeist, kann man sehr schnell sehr viele ausreichend gute Lösungen finden.
      Ich coache eine Basketball-Liga mit 8 Spielabschnitten. Kein Spieler darf mehr als 2 Abschnitte mehr spielen als ein anderer. Die Anzahl möglicher Lineups pro Spiel ist astronomisch groß, selbst wenn die Spielzeit-Constraints eingehalten werden.
      Eine Menge von Lineups zu finden, die die Constraints erfüllt, ist sehr einfach; eine optimale oder nahezu optimale Menge von Lineups zu finden, ist dagegen sehr schwer. Noch interessanter wird es, wenn man Spieler berücksichtigen muss, die zu spät kommen oder ohne Bescheid zu sagen fehlen.
      *Es ist nicht immer vollständig machbar
    • Ein Blogbeitrag, der im Detail beschreibt, wie das gemacht wurde, wäre bestimmt enorm beliebt.

  • Ich frage mich, ob es parametrisches CAD gibt, das hauptsächlich als Constraint-Solver funktioniert.
    Es nervt viel zu oft, dass man anfangs grob Werte für Parameter schätzen muss, die einen gar nicht interessieren. Es wäre schön, wenn man die relevanten Parameter als Constraints festlegen und den Rest optimieren könnte.

  • Ich frage mich, wie sich dieser Ansatz im Vergleich zu gemischt-ganzzahliger Programmierung schlägt. Wie wäre es bei physikalischen Problemen?

    • Viele Probleme lassen sich auf beide Arten formulieren. MILP hat immer eine Zielfunktion, und die Constraints sind immer lineare Kombinationen der Entscheidungsvariablen.
      Da Gurobi unglaublich schnell ist, kann es sich lohnen, ein Problem notfalls mit Gewalt in MILP-Form zu pressen, um eine Lösung zu bekommen.
    • CP-SAT ist rein ganzzahlig, daher dürfte es für Physik nicht besonders gut geeignet sein. Man kann reelle Zahlen zwar skalieren, aber das ist nicht so gut, wie direkt mit Fließkommazahlen zu arbeiten.
      Der Vorteil von CP-SAT ist, dass es boolesche und ganzzahlige Variablen sowie Constraints deutlich effizienter verarbeitet als ein MIP-Solver, besonders bei High-Level-Constraints wie all_different.
    • Ich vermute, dass sie im Großen und Ganzen ähnlich sind. https://www.amazon.com/gp/product/1107658799/ ist das letzte Buch, das ich zu diesem Thema gelesen habe, und es behandelt viele der gleichen Ideen.
      Insbesondere der Teil in diesem Artikel, in dem ein Wert minimiert werden soll, scheint im Grunde genau dasselbe direkt auszudrücken.