Алгоритм оптимального распределения ролей на собрании на основе заявленного уровня заинтересованности участников

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

  • активно стремится исполнить роль, если это возможно («А»)
  • хочет исполнить эту роль, но не очень к этому относится ("W")
  • не желает исполнять роль ("U").

Например, возможная входная матрица будет следующей:

Цель состоит в том, чтобы максимально увеличить количество совпадений для участников с ролями, для которых они отметили «A», при следующих ограничениях:

  • Все роли заняты ровно одним участником
  • Матчи, в которых участник отмечен знаком «U», запрещены.

Для этого примера оптимальным решением будет следующее, где 4/5 ролей заполняются с использованием совпадений «А».

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

Спасибо!


optimization algorithm linear-programming branch-and-bound tabu-search
person ForsakenCubist    schedule 04.07.2016    source источник
comment
Может ли участник занять › 1 роль?   -  person sascha    schedule 05.07.2016
comment
Нет; каждый участник может взять либо 0 (т. е. просто наблюдать), либо 1 роль.   -  person ForsakenCubist    schedule 08.07.2016

Ответы (1)


arrow_upward
0
arrow_downward

Подход

Вот простой подход целочисленного программирования, реализованный с помощью cvxpy в python.

Код

import numpy as np
from cvxpy import *

""" INPUT """
N_ATTENDEES = 6
N_ROLES = 5
ATTENDEE_CAN_TAKE_MULTIPLE_ROLES = False  # Modelling-decision

A_ROLES = np.array([[1,1,0,0,0],
                    [0,0,0,0,1],
                    [0,1,0,0,0],
                    [1,1,0,0,0],
                    [1,0,0,0,0],
                    [0,1,1,1,0]], dtype=bool)

W_ROLES = np.array([[0,0,0,1,0],
                    [0,0,1,1,0],
                    [1,0,0,1,1],
                    [0,0,0,0,0],
                    [0,0,1,0,1],
                    [0,0,0,0,1]], dtype=bool)

U_ROLES = np.ones((N_ATTENDEES, N_ROLES), dtype=bool) - A_ROLES - W_ROLES

""" Variables """
X = Bool(N_ATTENDEES, N_ROLES)  # 1 -> attendee takes role

""" Constraints """
constraints = []

# (1) All roles assigned to exactly one attendee
for r in range(N_ROLES):
    constraints.append(sum_entries(X[:, r]) == 1)

# (2) Forbidden roles
constraints.append(X <= (1-U_ROLES))

# (3) optional: max one role per attendee
if not ATTENDEE_CAN_TAKE_MULTIPLE_ROLES:
    for a in range(N_ATTENDEES):
        constraints.append(sum_entries(X[a, :]) <= 1)

""" Objective """
objective = Maximize(sum_entries(mul_elemwise(A_ROLES, X)))

""" Solve """
problem = Problem(objective, constraints)
problem.solve()

""" Output """
print(problem.status, problem.value)
print('assignments: \n' + str(np.array(np.round(X.value), dtype=int)))  # pretty-printing of ASSIGNMENTS
print('a-roles taken: \n' + str(np.array(np.round(mul_elemwise(A_ROLES, X).value), dtype=int)))  # pretty-printing of hitted A-roles

Вывод

('optimal', 4.000000000087978)
assignments: 
[[1 0 0 0 0]
 [0 0 0 0 1]
 [0 0 0 0 0]
 [0 1 0 0 0]
 [0 0 1 0 0]
 [0 0 0 1 0]]
a-roles taken: 
[[1 0 0 0 0]
 [0 0 0 0 1]
 [0 0 0 0 0]
 [0 1 0 0 0]
 [0 0 0 0 0]
 [0 0 0 1 0]]

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

Я также ленив, и MIP-подход, по крайней мере, лучше в отношении численной стабильности.

person sascha    schedule 04.07.2016