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

# <i class='fa fa-bank' /> 学会プログラムを作成する
学会の研究発表会の実行委員である**あなた**は、研究発表会のプログラムを作ることになりました。

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

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

[^1]: 例えば、Word2Vecで算出することも考えられます。

[組合せ最適化](http://qiita.com/Tsutomu-KKE@github/items/bfbf4c185ed7004b5721)を用いることにより、上記の問題を解くことができます。
定式化してみましょう。

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

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

# <i class='fa fa-bank' /> Pythonによる実行
申込みを表にしてみましょう。

```py3: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])
```

<table>
  <thead>
    <tr>
      <th></th>
      <th>発表者</th>
      <th>カテゴリ</th>
      <th>関連度</th>
      <th>vx</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>0</td>
      <td>物理</td>
      <td>0.207243</td>
      <td>vx0</td>
    </tr>
    <tr>
      <th>1</th>
      <td>1</td>
      <td>電力</td>
      <td>0.492636</td>
      <td>vx1</td>
    </tr>
    <tr>
      <th>2</th>
      <td>1</td>
      <td>生物</td>
      <td>0.913301</td>
      <td>vx2</td>
    </tr>
  </tbody>
</table>

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

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

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

<table>
  <thead>
    <tr>
      <th></th>
      <th>名称</th>
      <th>vy</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>通信</td>
      <td>vy0</td>
    </tr>
    <tr>
      <th>1</th>
      <td>医療</td>
      <td>vy1</td>
    </tr>
    <tr>
      <th>2</th>
      <td>物流</td>
      <td>vy2</td>
    </tr>
  </tbody>
</table>

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

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

```py3: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.カテゴリ=='任意')])
```

<table>
  <thead>
    <tr>
      <th></th>
      <th>発表者</th>
      <th>カテゴリ</th>
      <th>関連度</th>
      <th>vx</th>
      <th>rx</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>117</th>
      <td>26</td>
      <td>任意</td>
      <td>-10.0</td>
      <td>vx117</td>
      <td>1.0</td>
    </tr>
  </tbody>
</table>

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

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

```py3:python3
print(a.カテゴリ[(a.rx>0)].value_counts())
```

<table>
  <thead>
    <tr>
      <th></th>
      <th>カテゴリ</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>通信</th>
      <td>12</td>
    </tr>
    <tr>
      <th>電力</th>
      <td>8</td>
    </tr>
    <tr>
      <th>物理</th>
      <td>8</td>
    </tr>
    <tr>
      <th>生物</th>
      <td>7</td>
    </tr>
    <tr>
      <th>幾何</th>
      <td>4</td>
    </tr>
    <tr>
      <th>土木</th>
      <td>4</td>
    </tr>
    <tr>
      <th>物流</th>
      <td>4</td>
    </tr>
    <tr>
      <th>医療</th>
      <td>4</td>
    </tr>
    <tr>
      <th>地学</th>
      <td>4</td>
    </tr>
    <tr>
      <th>化学</th>
      <td>4</td>
    </tr>
    <tr>
      <th>任意</th>
      <td>1</td>
    </tr>
  </tbody>
</table>

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

以上