Определение алгоритма распределения ресурсов?

Question

Может кто-нибудь помочь мне решить или указать, что это за проблема:

У меня есть набор ресурсов и количество пользователей, и для каждого пользователя есть определенное подмножество ресурсов, которое может выбрать один ресурс из для распределения. Два разных пользователя не могут быть назначены одному и тому же ресурсу. Мне нужно распределить ресурсы для пользователей, чтобы максимизировать распределение. например:

R = {R1, R2, R3, R4}% Набор ресурсов

U = {u1, u2, u3, U4}% Множество пользователей

u1 может выбрать один ресурс от: {r1, r2, r3}

и2 может выбрать один ресурс из: {r1, r2}

и3 может выбрать один ресурс из: {r1, r4}

U4 может выберите один ресурс: {r2}

в этом случае я должен выделить

3-> u1, R1-> u2, 4-> и3, R2-> U4.

Если было выделено иначе, у u4 не будет выделенного ресурса.

Это только для объяснения проблемы. Мне нужно решить эту проблему для 200 пользователей и 100 ресурсов. Могу ли я узнать ваши рекомендации относительно того, какой алгоритм использовать или как его решить?

Answer 1

Я часто решаю эти проблемы с назначением с помощью решателя LP/MIP. Размер не слишком большой, поэтому почти любой решатель будет делать, и есть много легкодоступных. Это может показаться немного излишним, но по моему опыту он предлагает некоторую полезную гибкость (например, исправление некоторых заданий, позволяющих использовать дополнительные специальные ограничения).

Ваша проблема может быть сформулирована следующим образом:

Я решил проблему как RMIP, которая просто LP (рентгеновское переменные автоматически целое число для данного типа задачи).

В ответ на ваш вопрос позвольте мне попытаться объяснить уравнения.

Прежде всего необходимо отметить, что переменные x (u, r) принимают только значения 0 или 1. Это свойство задач линейного присваивания. Причина не совсем очевидна, но хорошая книга по линейному программированию может рассказать вам больше.

Первое уравнение assign1 говорит: мы можем назначить каждому пользователю не более одного ресурса. Например. для пользователя u1 У нас есть: x (u1, r1) + x (u1, r2) + x (u1, r3) < = 1. Это уравнение запрещает пользователю назначать два или более ресурсов. Мы допускаем неназначенных пользователей в случае нехватки ресурсов (например, если у нас есть набор данных с двумя пользователями и всего один ресурс). Поскольку пользователь не может быть назначен всем ресурсам, мы не суммируем все r, но только по допустимым комбинациям.

Второе уравнение assign2 говорит: мы можем назначить каждый ресурс не более чем одному пользователю. Например. для ресурса r1 У нас есть: x (u1, r1) + x (u2, r1) + x (u3, r1) < = 1. Это уравнение запрещает присвоение ресурса двум или более пользователям. Нам нужен этот вариант, иначе другим пользователям может быть присвоен один и тот же ресурс. Мы допускаем неназначенные ресурсы в случае, если нам не хватает пользователей (например, для случая, когда у нас есть 2 ресурса и всего 1 пользователь). Поскольку ресурс не может быть назначен ни одному пользователю, мы не суммируем все u, но только по допустимым комбинациям.

Идентификатор Объект подсчитывает, сколько действительных назначений было выполнено. Это значение, которое мы хотим максимизировать. Трюк снова должен суммировать допустимые комбинации для предотвращения незаконных присвоений.

Модель представляет собой небольшое изменение на модели LP, описанной here. Гораздо больше информации о проблеме назначения можно найти в this book.

Для вашего маленького набора данных, здесь входные данные и результаты:

Answer 2

Я написал простой ассемблер, который выделяет переменные в регистры. То, что я нашел наиболее эффективным, чтобы сделать самое сложное распределение в первую очередь, а затем перейти к следующему сложнее.

В вашем случае у вас есть список пользователей, которым требуется выделение. Поскольку у каждого пользователя есть другое правило для выделения, вам нужно создать счет для каждого из доступных ресурсов.

Затем действуйте следующим образом:

1. с использованием конкретных правил, рассчитывать имеющиеся ресурсы
2. выберите пользователя с минимальным
3. в случаях связей, randomally выбрать один
4. выделить ресурс для выбранный пользователь
5. повтор

Таким образом, вы отдаете приоритет тем пользователям, для которых наиболее сложно выделить. Но, учитывая пользователей и ресурсы, может не быть решения, поэтому вам может потребоваться повторить несколько раз. Если после N попытки, решение не найдено.