組合せ最適化で学会プログラムを作成する

学会プログラムを作成する

学会の研究発表会の実行委員であるあなたは、研究発表会のプログラムを作ることになりました。

• 60人の発表の申込みがありました。
  • 各発表には、関連するキーワードが1つまたは2つ指定されています。
• 4人の発表をまとめて、1セッションとし、全体で15セッション作ります。
• 各セッションには、それぞれ1つのセッションテーマがあります。
  • セッション内の発表は、テーマをキーワードに持っているものとします。
• あなたは、各申込みに対して、セッションテーマを決めて、15のセッションに振り分けないといけません。

考え方

• 全発表者の各キーワードを、選ぶかどうかの候補とします。
• キーワードに対し、その発表との関連度を(0-1)で設定する¹ものとします。
• 「選ばれた候補の関連度の総和」を最大化することにします。
• 各発表は、必ず、いずれかのセッションに割当てるものとします。
  • そのために、候補の中には、各発表ごとにダミーとして任意カテゴリを持たせます。
  • 任意カテゴリの関連度は非常に小さいもの(-10)とします。

組合せ最適化を用いることにより、上記の問題を解くことができます。
定式化してみましょう。

最大化	$\sum_i{関連度_i x_i}$	割当てられた候補の関連度の総和
変数	$ x_i \in \{0, 1\} $	$x_i$: $i$番目の候補を選ぶかどうか
	$ y_j \in 0以上の整数 $	$y_j$: $j$番目のカテゴリのセッション数
制約条件	$\sum_j{y_j} = 15$	全セッション数は15
	$\sum_{i \in F_h}{x_i} = 1 ~ ~ ~ \forall h \in H$	各発表は、ちょうど1つのキーワードが割当たる
	$\sum_{i \in G_k}{x_i} \le 4 y_j ~ ~ ~ \forall k \in C$	各カテゴリの発表数は枠数以下

ただし、$H$は発表者集合、$F_h$は発表者$h$の候補の集合、$C$はカテゴリの集合、$G_k$はカテゴリ$k$の候補の集合とします。

Pythonによる実行

申込みを表にしてみましょう。

python3

import numpy as np, pandas as pd
from pulp import *
np.random.seed(3)
nu = 4 # 1セッションの発表数
nr = 60 # 発表者数
cat = '通信 医療 物流 電力 土木 物理 化学 幾何 代数 地学 生物'.split() # カテゴリ
ns = nr / nu # セッション数
dat = [(i, j, np.random.rand()) for i in  range(nr)
       for j in np.random.choice(cat, np.random.randint(1, 3), replace=False)]
dat.extend([(i, '任意', -10) for i in range(nr)]) # 任意カテゴリの追加
a = pd.DataFrame(dat, columns=['発表者', 'カテゴリ', '関連度']) # 候補
a['vx'] = [LpVariable('vx%d'%i, cat=LpBinary) for i in a.index] # どの行を選ぶか
print(a[:3])

	発表者	カテゴリ	関連度	vx
0	0	物理	0.207243	vx0
1	1	電力	0.492636	vx1
2	1	生物	0.913301	vx2

vxは変数$x$に当たる列です。

カテゴリを表にしてみましょう。

python3

b = pd.DataFrame(cat, columns=['名称'])
b['vy'] = [LpVariable('vy%d'%j, cat=LpInteger, lowBound=0) for j in b.index] # セッション数
print(b[:3])

	名称	vy
0	通信	vy0
1	医療	vy1
2	物流	vy2

vyは変数$y$に当たる列です。

定式化して解き、カテゴリが任意となってしまった割当を見ます。

python3

m = LpProblem(sense=LpMaximize)
m += lpDot(a.関連度, a.vx)
m += lpSum(b.vy) == ns # 総セッション数は等しい
for i in range(nr):
    m += lpSum(a.vx[a.発表者==i]) == 1 # 発表者は1カテゴリを選ぶ
for _, r in b.iterrows():
    m += lpSum(a.vx[a.カテゴリ==r.名称]) <= r.vy * nu # 発表は枠数以下
m.solve()
a['rx'] = a.vx.apply(value) # 割当結果
b['ry'] = b.vy.apply(value) # セッション数結果
print(a[(a.rx > 0)&(a.カテゴリ=='任意')])

	発表者	カテゴリ	関連度	vx	rx
117	26	任意	-10.0	vx117	1.0

rxは変数$x$の結果に当たる列です。
発表者"26"さんが任意カテゴリに割当たっています。

各カテゴリごとの発表数を見てみましょう。

python3

print(a.カテゴリ[(a.rx>0)].value_counts())

	カテゴリ
通信	12
電力	8
物理	8
生物	7
幾何	4
土木	4
物流	4
医療	4
地学	4
化学	4
任意	1

生物カテゴリが4の倍数でないので、あぶれた26さんは、ここに入ることになります。

以上

1. 例えば、Word2Vecで算出することも考えられます。 ↩