米国 ナショナルフットボール･リーグ

はじめに

技術は、過去数十年間に格段の進歩を遂げ、以前は解決できなかった問題が、今や数秒足らずで解決できるまでになりました。当然ながら、これほどの進歩の結果として、より大規模で複雑な問題に取り組めるようになったのです。

その最たる例が、米国のナショナル フットボール リーグ（NFL）です。4人の担当者が、10週間かけて17週間にわたるシーズンの256試合のスケジュールを組みます。決定することが少ないわりには、時間は十分にあるように見受けられるかもしれません。ところが実際にやってみると、考えられるスケジュールの数はゆうに数百京にも上ります。想像してみてください。これは、1の後にゼロが19個も並ぶ数です。

データ サイエンティストが、この膨大な数の選択肢の中から適切なスケジュールを選び出すとなったら、何年もかかることでしょう。この問題をさらに難しくしているのが、追加される多くの制約条件です。たとえば、NYジェッツとNYジャイアンツなど、チームの本拠地が同じチームは同じ日時にプレーしない、どのチームも遠征試合が1週間内で連続3試合を超えてはならない、シーズン最後の数週間に地域対戦試合を可能なかぎり集中させてシーズンの終盤を盛り上げる、等々の制約条件を考慮しなければなりません。

木製ボードからコンピュータへ

10年ほど前までは、6フィート四方の木製のボードの横17列をシーズン17週分と見做し、総チーム数と同じ数の32を縦列として格子上に区切り、これを壁に掛けて、どのチームとどのチームが、いつ、どこで対戦するか書き込んでスケジュールを組んでいました。その際の最初の目標は、実現可能なスケジュールを見つけることであり、この作業を計画立案に充てることができる時間の90％を費やし、残りの時間は、特定のチームまたはネットワークのスケジュールのどちらかを改善するための調整に充てていました。

木製ボードからコンピュータに切り替わり、最適化のパワーが増すと、状況は劇的に変化しました。スケジュールを組むこと自体、ほんの2～3年前とは比べものにならないほど複雑化してはいるのですが、作業の焦点は、スケジュール作成からスケジュール分析へとシフトしたのです。以前は、計画立案をするチームが直面する問いは、単に「このスケジュールでいけるか？」ということでしたが、現在は実現可能な最善のスケジュールを見つけることが重要になっています。

科学としての芸術

この変化が重要であるのは、素晴らしいスケジュールを組むことは、科学であると同時に芸術でもあるからです。例えば、スケジューリングプロセスの一つの目標は、視聴者を最大限に確保できるTV放映時間帯に好カードを組むことですが、これは、そう簡単にできることではありません。1週間内での各チームの連続アウェイゲーム数の上限など、数々の制約条件を満たしたスケジュールであることを保証しながら、対戦カードの主観的評価が必要となるためです。さらに、フリーエージェントなどを含む様々な要因によって、スケジューリングプロセス中に、主観的評価が大幅に変化することもあります。

芸術的要素は、スケジューリングプロセスの中心です。計画立案者たちは現在、システムから与えられたどのスケジュールも評価でき、そのスケジュールで何を変更したいかを見分けられ、また、それがスケジュール全体にどう影響するかも確認することができます。変更後のスケジュールが良くなっていれば、それが新しいリーダーになり、そうでなければ捨てられます。ここ10年ほど前までは、計画立案者が見ることができるスケジュールは、実現可能な5計画だけだったかもしれません。2013年にGurobi を導入して以来、この数は劇的に増加し、現在では、計画立案者が毎年この処理に制約を追加しながらも、10,000を超える実現可能なスケジュールを計画し、比較することができます。

線形計画から並列最適化へ

NFLのスケジューリングにおける課題の複雑さは、この数年間で急激に増大しました。困難さの急激な増大に対処すべき戦略で、その大部分を占めているのは、最適化における線形から並列処理への移行でした。NFLは、当初単一の24コアマシンでスタートしましたが、2，3年前に、部屋一杯になるくらいの数の16コアのサーバマシンに移行しました。

新しいテクノロジーを採用する際にしばしば起こるのですが、従来の戦略を適用しても、そのすべての利点を活かしきることはできません。そこでOptimal Planning Solutions社は、Gurobiの開発チームと協力し、並列処理を有効活用するためのアプローチを再考しました。その結果NFLは、2014年に初めて新しいアプローチを採用することができたのです。

並列化アプローチの重要な利点は、一つの問題をいくつかのより小さい副問題に分割することに基づきます。副問題は問題解決のための資源プールに展開され、すべての資源は情報を共有でき、協調的な探索効果を作り出します。

このアプローチによってNFLは、次のようなことが可能になりました。

• 少数の既知解の狭い近傍を探索する方法に比べて、解空間全体からサンプリングすることで、実質的に解の質が向上しました。
• 複数のマルチコアの問題解決をするボックスから、より小さく安価なハードウェア構成またはクラウドベースのテクノロジーに移行する選択肢も含め、将来のハードウェア構成により柔軟に対応できるようになりました。

将来の展望

2017年には、NFLのスケジューリング問題は、960コア以上が接続されているネットワーク上で解を得ました。将来にわたり、更なる難しいスケジューリングの要件が継続的に追加されるたびに、この数は確実に増え続けるでしょう。
NFLは、設備投資への必要性を最小限に抑えながら驚異的な計算能力を得るために、クラウド環境に移行ました。最適化ツールの強化と結びついた問題の複雑さが増していくなか、NFLのような経験豊富なエンドユーザと、Optimal Planningのようなコンサルティング会社、そしてGurobiのようなソルバーの開発に専念している開発者集団の強固なパートナーシップは、よりいっそう重要性を増していくでしょう。

Gurobiのチームに切り替え協力できたことは、とても良い経験でした。GurobiのソルバーはNFLの高い期待に応えるもので、そのサポート体制も素晴らしいものでした。

– Michael North, Sr. Director, NFL

Gurobiのチームは、最高のパートナーでした。開発スタッフもサポートスタッフも、対応が迅速です。彼らのアイデアのおかげで、素晴らしい結果を出すことができました。

– Rick Stone, President, Optimal Planning Solutions