Algorytmy uogólnionego problemu przydziału od wielu do wielu

Nie mogę znaleźć literatury na temat algorytmów, która mogłaby zostać wykorzystana do rozwiązania problemu uogólnionego przypisania wiele do wielu (GAP), tj. Modeli, w których nie tylko można przypisać więcej zadań do jednego agenta, ale także wielu agentów przypisane do jednego zadania (punkty AP jeden do jednego i jeden do wielu są omówione w dokumencie Pentico). Prawie nic nie wiem o zadaniach, ale podczas moich badań natknąłem się na taki problem i chciałbym dowiedzieć się więcej o tym, jak je rozwiązać. Czy to możliwe, że tak wiele do wielu GAP jest znane pod inną nazwą, czy jest inny powód, dla którego tak mało literatury na ten temat można znaleźć?

Pentico, D. Problemy z zadaniami : ankieta na temat złotej rocznicy . European Journal Of Operational Research (2007); 176 (2): 774–793.

Twoim problemem nie wydaje się być „to, że suma„ agentów ”musi dostarczyć dokładnie dyskretną porcję energii lub nic na każde pojedyncze zapotrzebowanie…”, prawda? Albo mnie nie zrozumiałeś. Spróbuję więc lepiej opisać mój problem, również dlatego, że znalazłem rozwiązanie.

W moim problemie mam zestaw agentów, w których każdy ma budżet określonych zasobów, którzy mogą dzielić koszty zadań, które powinny być „wykonane” 1 raz lub nie (wiele do wielu zadań bez potrzeby „wykonaj” każde zadanie). Oznacza to: suma częściowych rozwiązań agentów dla zadania x powinna być mniejsza lub równa kosztowi zadania x. Celem jest znalezienie zestawu zadań o największej wartości, które agenci mogą zapłacić.

Pracuję z oprogramowaniem do gier, więc opisuję to w stylu gier: ustaw agentów, t zadania parametr koszt (t), wartość (t) parametr zasoby (a)

zmienna dodatnia y (a, t) (nie int), część agenta a dla kosztu zadania t cel:

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);

Jak napisałem, miałem rozwiązanie, ale nie wiedziałem, jak rozdzielić częściowe rozwiązania zadań. Ale teraz dowiedziałem się, że mogę zbudować ograniczenie za pomocą

zmienna binarna z(t)

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

sum(a, y(a,t)) / cost(t)w równaniu sformułowanie wynosi od 0 do 1 i przez to ograniczenie zwynosi 0 dla wszystkich mniejszych niż 1 i 1 dla 1. przy tym taskcost_bin_constraintcelu byłoby:

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

Zastanawiałem się, ale to działa i daje mi lepsze rozwiązania pod ograniczeniem, aby zbudować zadanie pełne lub nie.

Może możesz również dodać takie ograniczenie? Ograniczenie do dokładnego spełnienia wymagań wyrażone w wyrażeniu o wartości od 0 do 1.

Istnieje algorytm deterministycznego wyżarzania, który rozwiązuje problem przypisania jeden do jednego lub równoważnie problem podziału matrycy diadadowej.

Jednak zamiast używać liczb całkowitych [0, 1] można użyć wartości ułamkowych (więc algorytm pozostaje ten sam) lub nawet rozszerzyć go, aby obsługiwał więcej niż jedno przypisanie (przez dodanie wewnętrznej pętli i, w konsekwencji, macierz staje się macierzą hiperwymiarową lub tensor)

Artykuł jest tutaj: http://www.researchgate.net/publication/2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing/file/d912f50c75945d835b.pdf