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

20

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.

Gerrit Jan
źródło
1
Cześć GerritJan. Witamy w Scicomp! :) Czy znasz teorię lagrangianu dla ogólnego problemu przydziału? sciencedirect.com/science/article/pii/S0898122110002609 lub irma-international.org/viewtitle/58969 lub crcnetbase.com/doi/abs/10.1201/9781420010749.ch48 ?
Paweł
1
Wydaje mi się, że przypadek przypisania części zadania wielu agentom można modelować, przynajmniej w przypadkach, w których koszty są liniowo rozdzielone, traktując jedno zadanie tak, jakby to było wiele podzadań. Bez dodatkowych szczegółów trudno jest ustalić, w jaki sposób problemy mogą być bardziej „ogólne” niż ogólne problemy z przypisaniem. Artykuł na Wikipeidzie ma dobrą ekspozycję i linki do kilku odnośników na ten temat.
hardmath
Dzięki, Paul. Przejrzę dokumenty, które wydają się być dość skomplikowane dla mojego niewprawnego oka. Z drugiej strony podejrzewam, że problem jest skomplikowany i prawdopodobnie będę musiał trochę uprościć. Zasadniczo moim problemem jest w zasadzie dystrybucja energii w sieci: węzły podażowe i popytowe muszą być dopasowane przy użyciu (ważonych) połączeń między nimi, w najbardziej optymalny sposób, przy minimalnym zużyciu podaży w celu zaspokojenia całego zapotrzebowania. Oczywiście można zastosować dodatkowe ograniczenia, takie jak maksymalna pojemność połączeń itp.
Gerrit
1
@GerritJan: To trudny problem, więc będzie wymagał schematu aproksymacji. Jeśli potrzebujesz dobrego przybliżenia, algorytm może być nieco skomplikowany.
Paweł
2
@GerritJan: Oznacza to, że dokładne „optymalne” rozwiązanie można zagwarantować tylko poprzez sprawdzenie wszystkich możliwych konfiguracji. Te możliwe rozwiązania rosną (przynajmniej) wykładniczo w czasie, co sprawia, że ​​nawet stosunkowo niewielkie problemy z rozmiarem są praktycznie niemożliwe do rozwiązania dokładnie w rozsądnym czasie.
Paweł

Odpowiedzi:

1

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.

Maik
źródło
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

Nikos M.
źródło