Schneller Algorithmus für gewichtetes zweiteiliges Matching-Problem

8

Ich habe eine Reihe von Agenten und eine Reihe von n Aufgaben, und ich muss jeden Agenten genau einer Aufgabe zuordnen, damit die Kosten minimiert werden. Einige Agenten sind mit einigen Aufgaben nicht kompatibel.nn

Ich habe eine Implementierung des ungarischen Algorithmus, deren Lösung für meine Matrix ungefähr eine Minute dauert . Für verbotene Aufgaben setze ich die Kosten auf ∞ . ( In meinem Problem gibt es immer eine praktikable Lösung).640×640∞

Ich habe es auch als Binärprogramm in CPLEX eingerichtet, was ungefähr 9 Sekunden dauert, um das gleiche Problem zu lösen. Das BIP-Modell schließt verbotene Zuweisungen vollständig aus, indem diese Variablen weggelassen werden.

Ich habe noch nicht untersucht, wie ich es als Netzwerkmodell in CPLEX einrichten kann, aber das wird wahrscheinlich mein nächster Schritt sein. Die Kommunikation mit CPLEX verursacht jedoch Leistungskosten. Ich bin daher sicher, dass ein dedizierter Algorithmus eine bessere Leistung erzielen sollte.

Dieses zweigliedrige Übereinstimmungsproblem ist ein Kernel innerhalb eines anderen iterativen Suchalgorithmus, daher muss es so schnell wie möglich ausgeführt werden .

Gibt es Algorithmen, die ich implementieren kann und die in diesem Fall den ungarischen Algorithmus übertreffen? Oder haben Sie weitere Vorschläge, wie ich die Leistung dieses Kernels verbessern kann?

graph-algorithms optimization matching Ozzah
quelle
Nur als Randnotiz ist die zweiteilige Übereinstimmung für den minimalen maximalen Fluss von hoher Relevanz, und wie ich sehe, haben Sie eine dynamische Situation und Ihr ursprünglicher Graph ändert sich möglicherweise nicht zu stark in zwei aufeinanderfolgenden Iterationen, sodass Sie möglicherweise etwas Relevantes finden können Ihre Arbeit entlang dieser Frage und Antwort .
Saeed
@Saeed, danke, ich hatte überlegt, es als Min-Cost-Netzwerk darzustellen, wobei ich die Informationen aus der vorherigen Iteration als erste praktikable Lösung verwendete.
Ozzah

Antworten:

7

Sie können einen der auktionsbasierten Algorithmen für zweiteilige Übereinstimmungen ausprobieren. (Siehe z. B. Vorlesungsunterlagen, in denen eine einfache Variante beschrieben wird: https://staff.fnwi.uva.nl/nswalton/Notes/Bertsekas_Auction.pdf , weitere Optimierungen sind jedoch möglich.)

Diese Algorithmen haben nicht unbedingt die beste Worst-Case-Laufzeit, sondern erfordern nur sehr einfache Operationen und sind daher in der Praxis häufig effizient und können parallelisiert werden. (Und sie können als Grundlage für die Wiederherstellung der bekanntesten Worst-Case-Laufzeiten verwendet werden, siehe: http://agtb.wordpress.com/2009/07/13/auction-algorithm-for-bipartite-matching/

Aaron Roth
quelle