Алгоритмы для обобщенной задачи присваивания «многие ко многим»

Кажется, я не могу найти какую-либо литературу по алгоритмам, которые могут быть использованы для решения обобщенной задачи назначения (GAP) «многие ко многим», то есть моделей, в которых не только можно назначить большее количество задач одному агенту, но также можно назначить несколько агентов. назначается одной задаче (точки доступа «один-к-одному» и «один-ко-многим» обсуждаются в документе Pentico). Я почти ничего не знаю о проблемах с заданиями, но я столкнулся с такой проблемой во время исследования и хотел бы узнать больше о том, как их решать. Возможно ли, что такой много-ко-многим GAP известен под другим именем, или есть другая причина, почему так мало литературы по нему можно найти?

Пентико Д. Проблемы с назначением: обзор золотой годовщины . Европейский журнал операционных исследований (2007); 176 (2): 774-793.

Ваша проблема, похоже, не в том, что «сумма агентов» должна поставлять ровно определенную порцию энергии или ничего для каждого отдельного спроса ... », верно? Или ты меня не понял. Поэтому я постараюсь описать мою проблему лучше, потому что я нашел решение.

В моей задаче у меня есть набор агентов, каждый из которых имеет бюджет определенных ресурсов, которые могут разделить стоимость задач, которые должны быть «выполнены» 1 раз или нет (назначение «многие ко многим» без необходимости «выполнить» каждое задание). Это означает: сумма частичных решений агентов для задачи x должна быть меньше или равна стоимости задачи x. Цель состоит в том, чтобы найти набор задач с наибольшей ценностью, которые могут заплатить агенты.

Я работаю с игровым программным обеспечением, поэтому я описываю его в игровом стиле: установите агентов, t задач, стоимость (t), значение (t), ресурсы ресурсов (a)

положительная переменная y (a, t) (не-int), часть агента a для стоимости цели t задачи:

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

Как я уже писал, у меня было решение, но я не знал, как отделить частичные решения задач. Но теперь я узнал, что я могу построить ограничение с

двоичная переменная z(t)

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

sum(a, y(a,t)) / cost(t)в формуле уравнения это что-то между 0 и 1 и по этому ограничению, z0 для всех менее 1 и 1 для 1. с этой taskcost_bin_constraintцелью будет:

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

Мне было интересно, но это работает и дает мне лучшие решения в условиях ограничения, чтобы выполнить задачу полностью или нет.

Может быть, вы также можете добавить такое ограничение? Ограничение для точного выполнения требований, выраженное в выражении со значением от 0 до 1.

Существует детерминированный алгоритм отжига, который решает проблему взаимно-однозначного присваивания или, что то же самое, проблему разбиения двоичной матрицы.

Однако вместо использования целочисленных [0, 1] значений можно использовать дробные значения (таким образом, алгоритм остается прежним) или даже расширить его для обработки более чем одного назначения (добавив внутренний цикл и, по существу, матрица станет гиперпространственным массивом). или тензор)

Документ находится здесь: http://www.researchgate.net/publication/2382666_Pairwise_Data_Clustering_by_Deterministic_Annealing/file/d912f50c75945d835b.pdf