トークのスケジューリングを組合せ最適化問題として解く

　PyCon JP 2018 システムチームの池田(@ikedaosushi)です。

　いよいよPyConJP 2018開催まで1週間に迫りました。トーク、ポスター、LTとタイトルと概要だけ見ても興味深い内容ばかりで当日が待ち遠しいです。

　さて、先日HP上で全体タイムテーブルを公開し、トークのスケジュールを皆さんにお知らせすることができました。タイムテーブル詳細については是非HPをチェックしてください。(https://pycon.jp/2018/event/conference)



　トークのスケジューリング(スケジュール作成)は、一見すると簡単そう、単純そうに思えるかもしれません。しかし、参加者の皆さんの体験をより良いものにするためには、言語・ジャンル等の複数の要素を鑑みながらバランスよく割当をする必要があり、意外と人間が直接解くには難しい問題です。この投稿では、PyCon JP2018をより良いカンファレンスにするために、どのようにトークのスケジューリングに取り組んだのか共有したいと思います。

問題

　「意外と難しい問題」と書いたのですが、何が実際に難しいのか、問題なのか、を説明します。例えば、言語やジャンルを1つとっても一様に分布しているわけではないので、何も考えずに割当をしてしまうと

• 日本語がわからないが英語のトークが特定の時間帯に固まってしまっていて、その時間に聞けるトークがない
• Djangoのトークが聞きたいか特定の時間帯に固まってしまっていて、聞けないトークがたくさんあった

のような問題が発生する可能性があります。そこでできるだけ参加者にとって最適な割当を行うことが必要になります。

トークの特徴を可視化する

　それでは実際のデータを覗き見して、上述した問題が起こりうるのかを確かめます。採択されたトークがどんな特徴を持っているかを可視化してみたいと思います。

言語の割合

　言語の割合としては日本語のトークが多く、英語のトークの約3倍ありました。割当時には英語のトークをバランスよく割り当てる必要があることがわかります。

ジャンルの割合

　次にジャンルの割合です。PyCon JPではプロポーザルの送信時にはジャンルの指定を行っていないため、ここでジャンルいうは自分が1つ1つトーク内容をチェックしていき、分けたものです。最初は「ML(Machine Learning)、データ解析」「WebApplication」がとても多くなってしまったため、一部切り分けるために「Jupyter」「Django」という細かいジャンルを作るなど工夫してできるだけ割合が均等になるようにしました。ただ、それでも偏りは完全になくすことができず、「ML(Machine Learning)、データ解析」ジャンルの人気を感じる結果になりました。

　このように、「言語の偏り」「ジャンルの偏り」が顕著にあることを確かめることができました。それでは実際にどうこの問題を解決するかを考えていきたいと思います。

組合せ最適化問題

　問題へのアプローチには様々な選択肢がありますが、今回は、組合せ最適化問題の中の割当問題として解こうと考えました。割当問題は従業員の勤務時間をスケジューリングする問題や工場での最適なオペレーションを出力する問題などに適用されています。

　ちなみに組合せ最適化問題についてはPyCon JP 2015で、斉藤努さんが「組合せ最適化を体系的に知ってPythonで実行してみよう」というタイトルで発表されているので興味ある方はそちらも御覧ください。(https://www.slideshare.net/SaitoTsutomu/python-pycon-2015)

定式化

　割当問題として解くにあたり、下記のように定式化を行いました。

　部屋、時間、トーク、ジャンルの集合として定義し、x, y, zはその組み合わせが該当するような変数として定義しました。y, zはもう決まっているので

目的変数と制約条件は下記のように設定しました。

　ごちゃごちゃしているので少し分かりづらいですが、やりたいこととしては

1. 各時間帯で言語の偏りを最小化する
2. 各時間帯でのジャンルの中で最も偏っている差を最小化する

の2つになります。荒っぽい定式化なのですが、後述するようにこれをベースにして最終的には運営チームによって完成させるため、プロトタイプ最速で作ることを重視しました。

Greedy Algorithm

　この定式化した問題を取り組むアプローチとして、Greedy Algorithmを採用しました。Greedy Algorithmは離散最適化問題を解くアルゴリズムの1つで、現時点で取れる最も効率的な選択肢を1つ選び(貪欲選択)、残った問題を部分問題として再帰的に解いていく手法です。


　今回の例でいうと、「ある枠に対して、割当可能な中で最も効率的な1つのトークを割り当てる」のが貪欲選択になり、「残った枠、残ったトークに割当を行う問題を解く」のが部分問題を解く部分になります。


　Greedy Algorithmで解いた解が厳密解であることが保証されている条件は、貪欲選択性と部分構造の最適性を満たしていることなります。今回の問題設計だと、それが満たされていないため、厳密解であることは保証されていないのですが、今回はアドホックな要件(このトークの性質上、別のあるトークの後に配置したい、など)があり得たので貪欲選択時に要件に対して比較的簡単に対応できると考えられるGreedy Algorithmを選択しました。

割当してみました

　Greedy Algorithmを(もちろん)Pythonで実装し結果を出力しました。

　最終的な割当は是非HP(https://pycon.jp/2018/event/conference) をチェックしていてください。注意点として、

• Greedy Algorithmではベースの割当を行い、その後、運営チームで目視し問題がないか確認、調整などを行った
• 割当後に、ご家族の都合などでトーク辞退や日付移動の依頼があった関係で、完璧に偏りのない割当は実現ができていない

ことがあるのでご留意ください。

割当結果の可視化

　最終的な割当結果を可視化してみました。

言語

　言語に関しては「2日目 11:15 - 12:00」の時間帯は上述した注意事項の理由から日本語のトークのみになってしまいましたが、それ以外の時間帯に関しては英語のトークが大きな偏りなく配置できました。

ジャンル

　ジャンルに関しても1つの時間帯に特定のジャンルが偏ることなくバランスよく配分できました。言語に比べてジャンルは種類が多いので、人間が表とにらめっこをしながら割当を行った場合、バランスよく配分するのが難しいため、この結果には満足しています。

まとめ

上記のように、PyCon JP2018 では参加者の方により楽しんでいただけるように最適なトークの割当を考え、実際に割当を行っています。当日皆さんがPyCon JPを楽しんでいただければ幸いです。
　それでは来週、会場でお会いしましょう！