Eines der bekanntesten kombinatorischen Optimierungsprobleme ist das Zuweisungsproblem. Beispiel: Angenommen, eine Gruppe von Workern muss eine Reihe von Aufgaben ausführen und für jeden Worker und jede Aufgabe fallen Kosten an, wenn Sie den Worker einer Aufgabe zuweisen. Das Problem besteht darin, jedem Worker höchstens eine Aufgabe zuzuweisen, ohne dass zwei Worker die gleiche Aufgabe ausführen. Gleichzeitig müssen die Gesamtkosten minimiert werden.
Sie können dieses Problem anhand der Grafik unten visualisieren, in der es vier Worker und vier Aufgaben gibt. Die Kanten stellen alle möglichen Möglichkeiten für die Zuweisung von Workern zu Aufgaben dar. Die Beschriftungen an den Rändern geben die Kosten an, die für die Zuweisung von Workern zu Aufgaben anfallen.
Eine Zuweisung entspricht einer Teilmenge der Edges, bei denen für jeden Worker höchstens eine Edge heraustritt und keine der Kanten von zwei Workern zur selben Aufgabe führt. Unten sehen Sie eine mögliche Zuweisung.
Die Gesamtkosten für die Zuweisung betragen 70 + 55 + 95 + 45 = 265.
Im nächsten Abschnitt wird gezeigt, wie Sie ein Zuweisungsproblem sowohl mit dem MIP-Rechner als auch mit dem CP-SAT-Rechner lösen.
Andere Tools zum Lösen von Aufgabenproblemen
OR-Tools bietet außerdem einige weitere Tools zum Lösen von Zuweisungsproblemen, die schneller sind als die MIP- oder CP-Belöser:
Mit diesen Tools lassen sich jedoch nur einfache Arten von Zuweisungsproblemen lösen. Daher empfehlen wir für allgemeine Solver, die eine Vielzahl von Problemen lösen können (und für die meisten Anwendungen schnell genug sind), die MIP- und CP-SAT-Belöser.