Algorithmen für ein verallgemeinertes Viele-zu-Viele-Zuweisungsproblem

Ich kann anscheinend keine Literatur zu Algorithmen finden, die zur Lösung eines vielen zu vielen allgemeinen Zuweisungsproblems (GAP) verwendet werden können, dh Modelle, bei denen nicht nur einem Agenten mehr Aufgaben zugewiesen werden können, sondern auch mehreren Agenten Einer Aufgabe zugewiesen (Eins-zu-Eins- und Eins-zu-Viele-APs werden in einem Artikel von Pentico besprochen). Ich weiß so gut wie nichts über Zuordnungsprobleme, aber ich bin während meiner Recherche auf ein solches Problem gestoßen und möchte mehr darüber erfahren, wie man sie löst. Ist es möglich, dass eine solche GAP von vielen zu vielen unter einem anderen Namen bekannt ist, oder gibt es einen anderen Grund, warum so wenig Literatur darüber gefunden werden kann?

Pentico, D. Zuweisungsprobleme: Eine Umfrage zum goldenen Jahrestag . European Journal of Operational Research (2007); 176 (2): 774 & ndash; 793.

Ihr Problem scheint nicht zu sein, "dass die Summe der" Agenten "für jeden einzelnen Bedarf genau einen diskreten Teil der Energie oder gar nichts liefern muss ...", oder? Oder du hast mich nicht verstanden. Also werde ich versuchen, mein Problem besser zu beschreiben, auch weil ich eine Lösung gefunden habe.

In meinem Problem habe ich eine Reihe von Agenten, bei denen jeder über ein Budget von bestimmten Ressourcen verfügt, die sich die Kosten für Aufgaben teilen können, die 1 Mal "ausgeführt" werden sollen oder nicht (viele-zu-viele-Zuweisungen, ohne dass dies erforderlich ist) jede Aufgabe "ausführen"). Dies bedeutet: Die Summe der Teillösungen der Agenten für Aufgabe x sollte kleiner oder gleich den Kosten für Aufgabe x sein. Ziel ist es, die Aufgaben zu finden, die für die Agenten am wertvollsten sind.

Ich arbeite mit Gams-Software, daher beschreibe ich sie im Gams-Stil: Setze einen Agenten, t Aufgaben, Parameter, Kosten (t), Wert (t), Parameter, Ressourcen (a).

positive Variable y (a, t) (nicht int), Teil von Agent a für die Kosten der Aufgabe t Ziel:

maxvalue =e= sum((a,t), value(t) * y(a,t) / cost(t) );
agentresource_max_constraint(a).. sum(t, y(a,t)) =l= resources(a);
taskcost_max_constraint.. sum(a, y(a,t)) =l= cost(t);

Wie ich schrieb, hatte ich eine Lösung, wusste aber nicht, wie ich Teillösungen trennen sollte. Aber jetzt habe ich herausgefunden, dass ich mit a eine Einschränkung aufbauen kann

binäre Variable z(t)

taskcost_bin_constraint z(t) =e= sum(a, y(a,t)) / cost(t);

sum(a, y(a,t)) / cost(t)in der gleichungsformulierung ist etwas zwischen 0 und 1 und nach dieser einschränkung zist 0 für alle kleiner als 1 und 1 für 1. mit diesem taskcost_bin_constraintziel wäre:

maxvalue =e= sum(t, value(t) * z(t));

Ich habe mich gefragt, aber das funktioniert und gibt mir bessere Lösungen unter der Bedingung, eine Aufgabe voll zu erstellen oder nicht.

Vielleicht können Sie auch eine solche Einschränkung hinzufügen? Eine Einschränkung, um die Anforderungen genau zu erfüllen, ausgedrückt in einem Ausdruck mit einem Wert zwischen 0 und 1.

Es gibt einen deterministischen Annealing-Algorithmus, der das Eins-zu-Eins-Zuweisungsproblem oder gleichwertig das Dyadic-Matrix-Partitionsproblem löst.

Anstatt jedoch ganzzahlige [0, 1] -Werte zu verwenden, können auch gebrochene Werte verwendet werden (der Algorithmus bleibt also derselbe) oder er kann sogar erweitert werden, um mehr als eine Zuweisung zu verarbeiten (indem eine innere Schleife hinzugefügt wird und die Matrix im Wesentlichen zu einem hyperdimensionalen Array wird) oder Tensor)

Das Papier ist hier: http://www.researchgate.net/publication/2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing/file/d912f50c75945d835b.pdf