0

最適化の問題を解決するのに役立つ最適な手法やリソースを見つけようとしています。問題は、会議の出席者を事前定義された役割と最適に一致させることです。会議の前に、参加者は役割ごとに次のことを決定します。

  • 可能であれば積極的にその役割を果たそうとする (「A」)
  • 喜んでその役割を果たすが、それについて強く感じていない ("W")
  • 役割を果たしたくない（「U」）。

たとえば、可能な入力行列は次のようになります。

目的は、次の制約の下で、「A」とマークされた役割を持つ出席者の一致数を最大にすることです。

  • すべての役割は、正確に 1 人の出席者によって満たされます
  • 「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 に答える