Algoritmos para um problema de atribuição generalizada de muitos para muitos

Não consigo encontrar nenhuma literatura sobre algoritmos que possa ser usada para resolver um problema de atribuição generalizada (GAP) muitos para muitos, ou seja, modelos em que não apenas mais tarefas podem ser atribuídas a um agente, mas vários agentes também podem ser usados. atribuídos a uma tarefa (APs um para um e um para muitos são discutidos em um artigo do Pentico). Não sei quase nada sobre problemas de atribuição, mas me deparei com um problema como esse durante minha pesquisa e gostaria de saber mais sobre como resolvê-los. É possível que esse GAP muitos-para-muitos seja conhecido sob outro nome ou há uma razão diferente para que tão pouca literatura possa ser encontrada?

Pentico, D. Problemas de atribuição: uma pesquisa de aniversário de ouro . Jornal Europeu de Pesquisa Operacional (2007); 176 (2): 774-793.

Seu problema não parece ser "que a soma dos" agentes "precisa fornecer exatamente uma porção discreta de energia ou nada para cada demanda ...", certo? Ou você não me entendeu. Então, tentarei descrever melhor meu problema, também porque encontrei uma solução.

No meu problema, tenho um conjunto de agentes em que cada um tem um orçamento de certos recursos, que podem compartilhar o custo das tarefas, que devem ser "executadas" 1 vez ou não (atribuição de muitos para muitos sem a necessidade de "execute" todas as tarefas). Significa: a soma de soluções parciais de agentes para a tarefa x deve ser menor ou igual ao custo da tarefa x. O objetivo é encontrar o conjunto de tarefas com maior valor que os agentes podem pagar.

Estou trabalhando com o software gams, para descrevê-lo no estilo gams: defina um agente, t tarefa parâmetro cost (t), value (t) parameter resources (a)

variável positiva y (a, t) (não int), parte do agente a para o custo da tarefa t objetivo:

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

Como escrevi, eu tinha uma solução, mas não sabia como separar soluções de tarefas parciais. Mas agora descobri que posso criar uma restrição com um

variável binária z(t)

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

sum(a, y(a,t)) / cost(t)na formulação da equação é algo entre 0 e 1 e, por essa restrição, zé 0 para todos menos de 1 e 1 para 1. com esse taskcost_bin_constraintobjetivo seria:

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

Fiquei pensando, mas isso funciona e me dá melhores soluções sob a restrição, para construir uma tarefa completa ou não.

Talvez você também possa adicionar essa restrição? Uma restrição para atender exatamente às demandas, expressa em uma expressão com valor entre 0 e 1.

Existe um algoritmo determinístico de recozimento que resolve o problema de atribuição um-para-um ou equivalentemente o problema de partição de matriz diádica.

No entanto, em vez de usar valores inteiros [0, 1], é possível usar valores fracionários (para que o algoritmo permaneça o mesmo) ou até estendê-lo para lidar com mais de uma atribuição (adicionando um loop interno e, essencialmente, a matriz se torna um array hiperdimensional ou tensor)

O artigo está aqui: http://www.researchgate.net/publication/2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing/file/d912f50c75945d835b.pdf