Algoritmos para un problema de asignación generalizada de muchos a muchos

Parece que no puedo encontrar ninguna literatura sobre algoritmos que pueda usarse para resolver un problema de asignación generalizada de muchos a muchos (GAP), es decir, modelos en los que no solo se pueden asignar más tareas a un agente, sino que también se pueden asignar varios agentes asignado a una tarea (los AP de uno a uno y uno a muchos se discuten en un documento de Pentico). Sé casi nada de problemas de asignación, pero me encontré con un problema como este durante mi investigación y me gustaría saber más sobre cómo resolverlos. ¿Es posible que un GAP de tantos a muchos se conozca con otro nombre, o hay una razón diferente por la que se puede encontrar tan poca literatura al respecto?

Pentico, D. Problemas de asignación: una encuesta sobre el aniversario de oro . European Journal Of Operational Research (2007); 176 (2): 774-793.

Su problema no parece ser "que la suma de los" agentes "tenga que suministrar exactamente una porción discreta de energía o nada para cada demanda ...", ¿verdad? O no me entendiste. Así que intentaré describir mejor mi problema, también porque encontré una solución.

En mi problema, tengo un conjunto de agentes donde cada uno tiene un presupuesto de ciertos recursos, que pueden compartir el costo de las tareas, que deben "ejecutarse" 1 vez o no (asignación de muchos a muchos sin la necesidad de "ejecutar" cada tarea). Significa: la suma de las soluciones parciales de los agentes para la tarea x debe ser menor o igual al costo de la tarea x. El objetivo es encontrar el conjunto de tareas con más valor que los agentes pueden pagar.

Estoy trabajando con el software gams, así que lo describo en estilo gams: establezca un agente, t tareas costo de parámetro (t), valor (t) recursos de parámetro (a)

variable positiva y (a, t) (no int), parte del agente a para el costo de la tarea 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);

Mientras escribía, tenía una solución pero no sabía cómo separar las soluciones de tareas parciales. Pero ahora descubrí que puedo construir una restricción con un

variable binaria z(t)

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

sum(a, y(a,t)) / cost(t)en la formulación de la ecuación hay algo entre 0 y 1 y por esta restricción, zes 0 para todos menos de 1 y 1 para 1. con este taskcost_bin_constraintobjetivo sería:

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

Me preguntaba, pero esto funciona y me da mejores soluciones bajo la restricción, para construir una tarea completa o no.

¿Quizás también puede agregar tal restricción? Una restricción para satisfacer las demandas exactamente, expresada en una expresión con valor entre 0 y 1.

Existe un algoritmo de recocido determinista que resuelve el problema de asignación uno a uno o, de manera equivalente, el problema de la partición de la matriz diádica.

Sin embargo, en lugar de usar valores enteros [0, 1], uno puede usar valores fraccionarios (para que el algoritmo permanezca igual) o incluso extenderlo para manejar más de una asignación (agregando un bucle interno y esencialmente la matriz se convierte en una matriz hiperdimensional o tensor)

El documento está aquí: http://www.researchgate.net/publication/2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing/file/d912f50c75945d835b.pdf