学術講演会のプログラム編成 〜組み合わせ最適化問題〜
複数の会場で講演が同時進行する学術講演会や研究会のプログラム編成は，複雑で大変な作業です． 講演情報が集まった後のプログラム編成の流れは，大まかには次のようになものです．
- 同じ分野の講演を集めて適切なセッションを組む．
- それぞれのセッションに時間枠を割り当てる．
- 発表会場をそれぞれのセッションに割り当てる．
特に大変なのは，各セッションに時間枠を割り当てる作業です． 重複講演者に注意しなくてはいけませんし， 同一分野または聴衆が重複するセッションは，同じ時間枠を避ける必要があります． ここでは，各講演が適切なセッションに割り振られていることを仮定して， それぞれのセッションに時間枠を割り当てる問題を考えます． これは，組み合わせ最適化問題の一種であるグラフの彩色問題と対応しています．
グラフ彩色と反強磁性ポッツ模型
グラフとは，下図のように点(丸)を線で結んだ図です． グラフの点彩色では，辺で結ばれた点同士が同じ色にならないように，各点に色を割り当てます．
この問題を，エネルギーの最小化問題として解くことを考えます． グラフ彩色の言葉で言うと，辺で結ばれた頂点が同じ色の場合，および それぞれの点が避けたい色に塗られた場合に，増加するようなエネルギーを考えます． これは，反強磁性ポッツ模型で表現できます． ポッツ模型は，イジング模型と同様にスピン同士の相互作用を表したものです． グラフ彩色，プログラム編成，反強磁性ポッツ模型の間の対応関係は，下の表のようになります．
| グラフ彩色 | プログラム編成 | 反強磁性ポッツ模型 |
|---|---|---|
| 点 | セッション | ポッツスピン |
| 辺 | 重複制約 | 反強磁性的相互作用 |
| 色 | 時間枠 | ポッツスピンの状態 |
反強磁性ポッツ模型をプログラム編成に利用すると，エネルギーは次の式で表せます． \begin{align} H = \sum_{i,j}J_{ij}\delta(s_i,s_j) + \sum_{i=1}^N\sum_{k=1}^q w_{ik}\delta(s_i,k) + \sum_{k=1}^q \max(N_k-R_k,0) \label{H} \end{align} 変数$s_i$はセッション$i$に割り当てられた時間枠を表します． $\delta(s_i,s_j)$はクロネッカーのデルタです． 割り当て可能な時間枠数を$q$, 全セッション数を$N$とします ($s_i=1,\ldots, q$, $i=1,\ldots, N$). 右辺の各項は，それぞれ次の寄与を表しています．
- 第1項: 重複制約
- セッション$i$と$j$を同じ時間枠に重ねたくない場合は$J_{ij}>0$, それ以外は$J_{ij}=0$.
- 第2項: 回避制約
- セッション$i$に時間枠$k$を割り当てたくない場合は$w_{ik}>0$, それ以外は$w_{ik}=0$
- 第3項: 教室数制限
- $N_k=\sum_{i=1}^N\delta(s_i,k)$は，時間枠$k$に割り当てられたセッションの数．$R_k$は時間枠$k$で使用可能な教室数．$N_k>R_k$のときだけ，寄与がある．
$H=0$のときに全ての制約が満たされて，プログラム編成が成功します． 式\eqref{H}のようなエネルギーを最小化するアルゴリズムは，いくつも存在します． この式に必要なパラメータを設定すれば，編成されたプログラムが計算結果として得られます．この意味で，プログラムの半自動化が可能となります．
実際の学術講演会のプログラム編成への適用例
日本物理学会のプログラム編成(特に領域11)に適用した例を紹介します． 日本物理学会では，素粒子・核物理・宇宙線など6領域，および物性関係13領域に分かれて，基本的には領域ごとにプログラム編成を行います． 領域11(物性基礎論，統計力学，流体物理，応用数学，社会経済物理)はその中でも最も大きな領域の1つです．毎大会の講演数は口頭発表だけでも200件を超え，セッション数は約30個あります． それを，大会期間の4日間に収めなければなりません． 時間枠は秋季大会が8枠，年次大会が7枠です． 1セッションは13講演が基準で，講演者が指定した第1キーワードをもとにセッションを組みます． 1つのキーワードの講演者数が多ければ2つ以上のセッションに分割し，逆に少なければ他の近いキーワードの講演と一緒にしてセッションを組みます．
領域11のプログラム編成には，バッティングルールというものが存在します． 聴衆が重なる，あるいは非常に近い分野のセッションは，同じ時間枠に重ならないようにするためのルールです． 2017年3月の年次大会で実際に用いられたバッティングルールは，下図のような複雑なものです． (現在は，バッティングルールが改正されて，もっと簡素になっているかもしれません．) 赤線は，当時明文化されていたルール，青線は明文化されていなかった慣例的なルールです．
このバッティングルールは，式\eqref{H}の第1項に対応します． 他にも以下のような制約を考える必要があります．
- 複数登壇者 [第1項に対応]
- 他の領域の関連セッションとのバッティング [第2項に対応]
- セッションの長さ [第2項に対応]
... 基本講演数より大幅に多い場合は午前中を避ける． - 各時間帯のセッション数 [第3項に対応]
... 教室数の制限．ポスターセッションやシンポジウムの考慮．
筆者が領域運営委員を務めていた2017年3月の年次大会では，実際にここで説明した方法を使って領域11のプログラム編成を行いました． エネルギー最小化にはシミュレーテッド・アニーリング法を用いましたが， 容易に(実行時間は数秒〜数十秒程度で)，設定した制約を満たすタイムテーブルを作成できました．
まとめ
ここでは，反強磁性ポッツ模型を使った学術講演会のプログラム編成の半自動化のアイデアを紹介しました． セッションに時間枠を割り当てることに焦点を絞れば，半自動化は可能だということが分かりました． ここで紹介した内容は，論文[1]にまとめられています． この論文ではさらに，回避制約を増やした場合の成功率の変化や，ランダムグラフとの比較なども議論しています． (この内容は，文献[2]でも解説しています．)
学術講演会のプログラム編成全体の自動化には，まだまだ課題が残されています． たとえば，今回は時間枠の割り当て自体は成功しましたが，制約条件の設定は人がしなければなりませんでした． また，ここでは議論しなかった発表会場の割り当ても，現実には難しい問題です． そして，前提条件としていた各講演の適切なセッションへの割り振りも，非常に大きな課題です． 今後この問題に取り組む研究者が増えて，近い将来，学術講演会のプログラム編成の自動化が実現することを願っています．
参考文献
[1] Kazue Kudo, "Academic Meeting Scheduling Using an Antiferromagnetic Potts Model", J. Phys. Soc. Jpn. 86, 075002 (2017); (arXiv:1706.04362 [physics.soc-ph]).
[2] 工藤和恵, 「学会プログラム編成の半自動化を反強磁性ポッツ模型で実現」, 日本物理学会誌 73, 227-229 (2018).