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

20

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.

Gerrit Jan
fonte
1
Oi GerritJan. Bem-vindo ao Scicomp! :) Você está familiarizado com a heurística lagrangiana do problema de atribuição generalizada? sciencedirect.com/science/article/pii/S0898122110002609 ou irma-international.org/viewtitle/58969 ou crcnetbase.com/doi/abs/10.1201/9781420010749.ch48 ?
Paul
1
Parece-me que o caso de atribuir partes de uma tarefa a vários agentes pode ser modelado, pelo menos nos casos em que os custos são linearmente distribuídos, tratando a tarefa como se fossem várias subtarefas. Sem mais detalhes, é difícil saber como seus problemas podem ser mais "gerais" do que problemas de atribuição generalizados. O artigo da Wikipeida tem uma boa exposição e links para algumas referências sobre o tópico.
hardmath
Obrigado, @Paul. Vou examinar os papéis, embora eles pareçam bastante complicados para os meus olhos destreinados. Por outro lado, suspeito que o problema seja complicado e provavelmente terei que simplificar. o problema é basicamente o de distribuir energia em uma rede: os nós de suprimento e demanda precisam ser correspondidos usando as conexões (ponderadas) entre eles, da maneira mais ideal, com um uso mínimo de suprimento para atender a toda demanda. Claro, restrições adicionais podem ser usados, como capacidade máxima nas conexões, etc.
Gerrit Jan
1
@GerritJan: É um problema np-difícil, portanto exigirá um esquema de aproximação. Se você precisar de uma boa aproximação, seu algoritmo pode ter que ser um pouco complexo.
Paul
2
@GerritJan: Significa que a solução exata 'ideal' só pode ser garantida através da verificação de todas as configurações possíveis. Essas possíveis soluções crescem (pelo menos) exponencialmente ao longo do tempo, tornando até mesmo problemas de tamanho relativamente modesto praticamente impossíveis de resolver exatamente em um período de tempo razoável.
Paul

Respostas:

1

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.

Maik
fonte
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

Nikos M.
fonte