Einschränkungsoptimierung oder Constraint-Programmierung (CP) ist der Name, mit dem sich aus einer sehr großen Anzahl von Kandidaten durchführbare Lösungen identifizieren lassen, bei denen das Problem in Bezug auf beliebige Einschränkungen modelliert werden kann. CP-Probleme treten in vielen wissenschaftlichen und technischen Disziplinen auf. (Das Wort "Programmierung" ist etwas falsch, ähnlich wie "Computer" einst "eine Person, die berechnet" bedeutet. Hier bezieht sich „Programmierung“ auf die Anordnung eines Plans und nicht die Programmierung in einer Computersprache.
CP basiert auf der Machbarkeit (Finden einer durchführbaren Lösung) und nicht auf der Optimierung (Finden einer optimalen Lösung) und konzentriert sich auf die Einschränkungen und Variablen anstatt auf die objektive Funktion. Tatsächlich hat ein CP-Problem nicht einmal eine objektive Funktion. Das Ziel kann darin bestehen, eine sehr große Menge möglicher Lösungen auf eine überschaubare Teilmenge einzugrenzen, indem dem Problem Einschränkungen hinzugefügt werden.
Ein Beispiel für ein Problem, das sich gut für CP eignet, ist die Mitarbeiterplanung.
Das Problem tritt auf, wenn Unternehmen, die kontinuierlich arbeiten, wie Fabriken, wöchentliche Zeitpläne für ihre Mitarbeiter erstellen müssen. Ein sehr vereinfachtes Beispiel: Ein Unternehmen führt täglich drei 8-Stunden-Schichten und weist drei seiner vier Mitarbeiter täglich verschiedenen Schichten zu, während dem vierten Tag freie Tage zugewiesen sind. Selbst in so einem kleinen Fall ist die Anzahl der möglichen Zeitpläne enorm: Pro Tag gibt es 4! = 4 * 3 * 2 * 1 = 24 mögliche Mitarbeiteraufträge, die Anzahl der möglichen wöchentlichen Zeitpläne beträgt also 247, also mehr als 4.5.
In der Regel gibt es weitere Einschränkungen, die die Anzahl der durchführbaren Lösungen reduzieren, z. B. dass jeder Mitarbeiter mindestens eine Mindestanzahl von Tagen pro Woche arbeitet. Bei der CP-Methode wird erfasst, welche Lösungen machbar bleiben, wenn Sie neue Einschränkungen hinzufügen. Dadurch ist sie ein leistungsstarkes Werkzeug zum Lösen großer, realer Planungsprobleme.
CP hat eine weitverbreitete und sehr aktive Community auf der ganzen Welt mit speziellen wissenschaftlichen Zeitschriften, Konferenzen und einem Arsenal an verschiedenen Lösungstechniken. CP wurde bei der Planung, Planung und zahlreichen anderen Domains mit heterogenen Einschränkungen erfolgreich angewendet.
Tools
Google bietet mehrere Möglichkeiten zum Lösen von CP-Problemen:
- CP-SAT-Resolver: Ein Einschränkungs-Programmier-Löser, der SAT-Methoden (Erfüllbarkeit) verwendet.
- Ursprünglicher CP-Resolver: Ein in der Routing-Bibliothek verwendeter Lösungslöser für Einschränkungsprogrammierung.
Wenn Ihr Problem mit einem linearen Ziel und linearen Einschränkungen modelliert werden kann, haben Sie ein lineares Programmierproblem und sollten MPSolver in Betracht ziehen. Routenprobleme lassen sich jedoch in der Regel am besten mit unserer Fahrzeugroutenbibliothek lösen, selbst wenn sie mit einem linearen Modell dargestellt werden können.
Beispiele
Im nächsten Abschnitt wird der CP-SAT-Resolver beschrieben, der primäre OR-Tools-Rechner für die Einschränkungsprogrammierung. SAT steht für Satisfiability (Erfüllbarkeit): Der Solver verwendet Techniken zum Lösen von SAT-Problemen zusammen mit CP-Methoden.
Hier sind einige Beispiele für Planungsprobleme, die sich gut für den CP-SAT-Rechner eignen:
Zwei klassische CP-Probleme sind das N-Quens-Problem und kryptarithmetische Rätsel.