プログラミングコンテスト優勝者・小島健介が生み出す最適化Solverの新アルゴリズム

2022.09.30S0: Solverオプション(最適化) , X1:アスプローバ社員インタビュー

アスプローバ社　プログラマーインタビュー　小島健介

　スケジューラーに革命を起こしつつある「Solver」。その第一号であるS1の開発に携わったプログラマー小島健介さんに、Solver誕生前後のことを中心に聞きました。小島さんは広島市の出身。京都大学大学院情報科学研究科で博士後期課程修了後、京大で博士研究員、特定講師を務めました。2020年アスプローバ社に入社。プログラミングコンテスト上位入賞の常連で、入社後も存分に力を発揮し「小島マジック」とも評されています。

プロコンがきっかけに

ー 大学での研究がどのようにスケジューラーに結びついたのでしょうか

　もともと数学と論理学を専門にしていました。問題を数学的に定式化して、解くためのアルゴリズムを考えるのが得意です。

　アスプローバ社のことを知ったのは、2018〜2019年の年末年始に行われた 第2回Asprova プログラミングコンテストに参加したことです。出題されたのは、生産スケジューリングの問題で、それは「組合せ最適化」と呼ばれる分野の一つです。ちょうど興味を持ってその分野の勉強を始め、雰囲気がわかってきたころでした。結果は6位で、当時は入賞が5位までだったので惜しかったなと思っていたら、特別賞を出すという連絡がありました。当時は京都に住んでいましたが、せっかくなので新幹線で懇親会の会場まで行きました。その後もプロコンに参加し、第3回と第5回で１位になることができ、入社の誘いを受けました。

ー Solverのアイデアはどこから出たのでしょう

　2020年の暮れ、S1 、つまり平準化生産を実現するスケジューラーの案件を聞きました。それまでは基本的にルールに基づくというか、人間的な感覚に基づいて Solver を作ろうとしていましたが、これはなかなか難しいなという感じがあったように記憶しています。

　そこで実験的に、ルールらしいルールはなしにして、乱数でとにかくいろいろ探索してみたら、予想以上にうまく動きました。それで、こういうやり方でやってみてもいいんじゃないかという社内の雰囲気になりました。

　今の S1 の内部は、いろいろな制約に対応するための処理は追加されていますが、最適化の基本的な部分はその頃に作ったプログラムからほとんど変わっていません。

大きな数は直感で理解できない

ー それが小島マジックなのですね。それまで誰も試してみなかったのでしょうか

　学術的な研究としては、小規模なデータを対象にするものが多く、実問題にはそのままでは適用しにくかったようです。開発部の他のメンバーも、そういう手法の存在は以前から認識していたと思います。

　問題によっては、ランダムな探索の反復だけで最適化がうまくいくということは、一度プログラムを書いて経験したことがないと想像しづらいかもしれません。一回一回のステップでは改善する可能性は高くないし、ちょっとしか改善しないのですが、試行回数を十分多くすれば意外といい解にたどり着いてしまう、ということなのだと思います。

　どうも人間は大きな数に対する直感がそんなに働かない。数十万回の反復をした後にどうなっているかというのは、直感的にわからないようです。

　たとえばホチキスの針（厚さ0.5㍉）を100万本並べるとどのくらいの長さになると思いますか。部屋の端から端までくらいかな、と直感的には思われますが、0.5㍉×100万は500㍍。16両編成の新幹線の先頭から最後尾までよりも長くなるのです。

ー プロコン式の取り組みがSolverでも役立ったと社内で聞きました

　Solver の開発を行うときに、1. 解くべき問題をプロコンっぽく定義する　2. その問題を解くプログラムを作る　3. 作ったプログラムを Asprova から利用できるようにする–というステップに分割することが多いのですが、これは私が意識的にやっていたところで、このことを指しているのかなと思います。

　ルールに基づかない反復改善で上手くいく（こともある）という認識は、私が S1 の実験をしてから定着したところがあるようです。もしかしたらそっちのことかもしれません。

ー スケジューラーに組合せ最適化を持ち込む時の考え方について教えてください。

　組合せ最適化問題を解くときに考えることは大きく分けて二つあると思います。どちらの要素も大事だと思いますが、これらの比重は問題ごとに違っている気がします。

　一つは、理屈で説明がついたり、論理的な説明まではできなくても人間の直感に基づいてこうすればよさそうだと思えるアイデアに基づいて解くやり方です。生産スケジュールだったら、納期の早いものからやる、段取りが出ないものを次にやる、などです。

　もう一つは、「こうすればよさそう」というルールが見つからない部分を、コンピュータの速度を活かして幅広く探索するやり方です。たとえば段取りを最小化するために次にどの品目を選べばいいかは、その場ですぐに最適なものが選べないので、いろんな選択肢を試します。

　２つは、はっきり分割できるわけではありません。S1 の場合は、人間的な工夫に比べて探索の速度に頼る部分がかなり大きいと思います。より人間っぽい考えに基づいた工夫ももうちょっと入れられると思いますが、そこまでしなくてもある程度の結果が出せています。S1 以外では、もっと人間っぽい工夫をしている Solver が多いと思います。たとえば、段取りを増やさないように、同じ品目をある程度まとめて作るなどの処理を意図的に入れることがこれにあたります。

ー プライベートの楽しみなどはありますか

　京都にいたときは、京大のそば、吉田山の斜面に住んでいました。歩いて1分で山の中。緑あふれる環境でした。鴨川も近くて、よく散策しました。東京に来てからは五反田近辺に住んでおり、なかなかそういう場所が見当たらないですね。プログラミングのことをずっと考えていると、たまに気分転換したくなります。いい散歩の場所を探しています。