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

20

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

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

Геррит Ян
источник
1
Привет ГерритДжан. Добро пожаловать в Scicomp! :) Вы знакомы с лагранжевой эвристикой для обобщенной задачи присваивания? sciencedirect.com/science/article/pii/S0898122110002609 или irma-international.org/viewtitle/58969 или crcnetbase.com/doi/abs/10.1201/9781420010749.ch48 ?
Павел
1
Мне кажется, что случай назначения частей задачи нескольким агентам можно смоделировать, по крайней мере, в случаях, когда затраты линейно распределяются, обрабатывая одну задачу, как если бы она была вместо нескольких подзадач. Без более подробной информации трудно понять, как ваши проблемы могут быть более «общими», чем общие задачи с заданиями. Статья Wikipeida имеет некоторые хорошие экспозиции и ссылки на пару ссылок по теме.
hardthth
Спасибо, Пол. Я посмотрю на бумаги, хотя они кажутся довольно сложными для моего неподготовленного глаза. Опять же, я подозреваю, что проблема сложная, и мне, вероятно, придется сделать некоторое упрощение. В действительности, моя проблема в основном заключается в распределении энергии в сети: узлы спроса и предложения должны сопоставляться с использованием (взвешенных) связей между ними, наиболее оптимальным образом, с минимальным использованием предложения для удовлетворения всего спроса. Конечно, можно использовать дополнительные ограничения, такие как максимальная пропускная способность соединений и т. Д.
Геррит
1
@GerritJan: Это сложная задача, поэтому для нее потребуется схема аппроксимации. Если вам нужно хорошее приближение, ваш алгоритм может быть немного сложным.
Павел
2
@GerritJan: Это означает, что точное «оптимальное» решение может быть гарантировано только путем проверки всех возможных конфигураций. Эти возможные решения растут (по крайней мере) в геометрической прогрессии с течением времени, что делает даже относительно небольшие проблемы размера практически невозможно решить точно в разумные сроки.
Павел

Ответы:

1

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

В моей задаче у меня есть набор агентов, каждый из которых имеет бюджет определенных ресурсов, которые могут разделить стоимость задач, которые должны быть «выполнены» 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.

Maik
источник
1

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

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

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

Никос М.
источник