0

我试图找出最好的技术或资源来帮助我解决优化问题。问题在于将会议参与者与预定义角色进行最佳匹配。在会议之前，与会人员为每个角色决定他或她是否：

  • 如果可能的话，积极寻求填补这个角色（“A”）
  • 愿意担任该角色，但对此感觉不强烈（“W”）
  • 不愿意担任这个角色（“U”）。

例如，一个可能的输入矩阵是：

目标是在以下限制条件下，最大限度地增加角色标记为“A”的与会者的匹配次数：

  • 所有角色仅由一名与会者担任
  • 禁止参加者标记为“U”的比赛

对于此示例，最佳解决方案如下，其中 4/5 角色使用“A”匹配填充。

有谁知道是否有比蛮力更好的方法来解决这类问题（对于较大的矩阵来说，这很快变得不可行）？我愿意接受我自己实现的优化算法的一般建议（即禁忌搜索、遗传算法、分支定界等），甚至是指向现有包（如OptaPlanner ）中的功能的指针。

谢谢！

4

1 回答 1

0

方法

这是一个简单的整数编程方法，在 python 中使用cvxpy实现。

代码

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 方法至少在数值稳定性方面更好。

于 2016-07-04T23:28:02.980 回答