進化する最適化技術 VOL.2
～最適化問題を解決に導くNSSOLの技術と実績 －量子アニーリングは万能ではない－～
左から樋川 暁さん、山本 政さん、塩見 雄佑さん（全員システム研究開発センター所属）※所属は取材当時のものになります。
目的地までの最短経路を考える。数多くチームがあるプロスポーツの試合日程を組む。このような膨大な選択肢の中から最適な答えを導き出す技術を「最適化技術」と言います。NSSOLでは、この最適化技術を長年研究してきました。そして、サッカーJリーグの試合日程や製造現場における工程計画をはじめとして様々な最適化ソリューションをお客様に提供しています。
連載2回目となる今回は、最適化を実現する技術について、システム研究開発センター（以下、シス研）で同分野の研究に従事している、山本 政さん、塩見 雄佑さん、樋川 暁さんに話を聞きました（本シリーズは3回連載です）。
「最適化」は身のまわりにも一般的にある事象
――「最適化」とはそもそも何なのか。改めて、教えてもらえますか。
山本：どのようなスケジュールにすれば、1日を効率よく過ごせるか。工場の生産計画を最も効率化するには、どのようなフローにすればよいか。私たちはふだん、生活でもビジネスの現場でも、多くの「意思決定」をしています。そしてこの意思決定は言い方を変えれば、どの組合せがベストなのかを考えて判断することでもあります。
塩見：「どの組合せがベストなのかを考えていること」が、まさしく最適化問題を解いているということです。
樋川：少し専門的な話をすると、最適化は「連続最適化」と「組合せ最適化」に大別され、私たちが研究しているのは後者になります。
もう少しだけ補足すると、組合せ最適化（問題）は以下のように定義され、数式で表現します。
① 多数の選択肢 (変数)から
② 制約条件を満たし、
③ 評価点 (目的関数)が一番良くなる
変数の組合せを見つける問題
――具体的で簡単な最適化問題の例を教えてください。
山本：「ナップサック問題」はよく取り上げられます。１キログラムまでの荷物を入れることができるナップサックがあります、ここにおにぎりや焼き芋などといったアイテムを合計１キログラム以内におさまるように入れなさい、ただ各アイテムには「価値」がついていて、価値が最大になるように組合せて入れなさいという問題が「ナップサック問題」です。このような問題では、おにぎりは入れる、入れない、焼き芋は入れる、入れないというようにアイテムを組合せて決めていきます。
――その問題はわかりやすいですね。遠足の時によくやりましたね。
樋川：先ほどの定義にナップサック問題を当てはめると、以下のようになります。
- 重さと価値を持つさまざまなアイテム（おにぎりなど）から（多数の選択肢／変数）
- ナップサックの容量1キログラムを超えない範囲で（制約条件）
- 価値（値段）の合計が最大になるアイテムの組合せを選ぶ問題（評価点／目的関数）
――なるほど。では身近なITサービスとして我々が普段使っている最適化の例というとどのようなものがありますか？
塩見：みなさんがよく使っているのは電車の乗り換え案内ではないかと思います。
――あ、なるほど。あれは便利ですね。
塩見：目的地まで一番早く着けるルートであるとか、一番安く行けるルートなど自分の知りたいポイント（評価点）でいくつかおすすめのルートを表示してくれて、私たちは自分に合ったものを選択できます。あれも様々な路線、運賃、時刻表などを組合せて答えを出しています。
組合せ最適化問題の難しさ「組合せ爆発」
――乗換案内も組合せだというのはわかりますが、組合せは膨大ですよね。全ての組合せからベストな答えを導き出しているのでしょうか。
樋川：もちろん全ての組合せをしらみつぶしに調べていくというやり方はありますし、全ての組合せを比較するのがベストではあります。先ほどのナップサック問題程度であればそれは可能ですが、乗換案内も含め私たちのビジネスで扱う組合せ最適化問題ではそれはできないんです。
――できないというのは？
樋川：「組合せ爆発」というのがあって、組合せの計算がとんでもない数になってしまうので、基本的にはしらみつぶしというのはできないということです。
――組合せが爆発してしまう？
山本：そうなんです。簡単な例で説明すると、組合せ最適化問題に「巡回セールスマン問題」という教科書にもでてくるような典型例があります。お客様が点在していて一筆書きで周ってくる一番短い経路を探すという問題です。（図2）その周り方のパターン数を全て調べると、巡回点が５か所で60の組合せになります。60通りくらいならばコンピュータを使えば簡単ですが、30か所を回る組合せになるととんでもない数字になります。どれくらいだと思いますか？
――京（ケイ）とか垓（ガイ）ですか？
山本：そんなものでは済まないですね。
――え、どれくらいですか？
山本：1.3×10の32乗。1京の1京倍といったところでしょうか。
――それは手計算では到底、無理ですね。
アルゴリズムの選定が肝
樋川：この巡回セールスマンの30か所を周る組合せを総当たりで計算させると「スーパーコンピュータでも8億年かかる」とある記事に載っていました。
――8億年？そのような問題をどうやって解いているのですか？
山本：アルゴリズムを使います。最適化問題を解くためのアルゴリズムはたくさんあって、巡回セールスマン問題を解くのに適したアルゴリズムを使えば30都市程度ならあっという間に解けます。
――アルゴリズムですか。
山本：そうです。アルゴリズムを使うと1000都市でも１分もかかりません。ちなみに、1000都市をしらみつぶしに当たっていくと10の2500乗ほどになります。10の2500乗ってどれくらいかというと宇宙の中にある水素原子の数を全部集めても10の80乗くらいしかないんですね。天文学にもない数字になるんですよ。
――みなさんはそのアルゴリズムの研究をしているのですか
山本：アルゴリズム自体の研究ではなく、アルゴリズムをビジネスにどう応用するかを研究しています。
組合せ最適化は適用分野が多い
――先ほど電車の乗り換えのお話がありましたが、組合せ最適化はどういった分野に応用されているのでしょうか。
山本：組合せ最適化の応用分野はかなり広いです。一例ですが、ORwikiでは生産販売計画、財務・金融、交通などの括りで20以上の応用分野をあげています。
――なるほど、実は組合せ最適化はいろいろなところで使われているのですね。具体的にはどのような問題を解いているのでしょうか。
山本：例を簡単に示したのが図５になります。マルの中の数字が制約条件で、それを超えないように満足度や利益、回収確率が最大化する組合せを考える、というものになります。
――これもアルゴリズムを用いて最適解をだしていくのですね。
塩見：そうです。ただ、単にアルゴリズムを用いれば解が出るというものではありません。まず、それぞれの最適化問題に向いているアルゴリズムを選定する、その見極めが難しいのです。言い方を変えると、適さないアルゴリズムを使うと、最適な解は出ません。
樋川：私たちの強みのひとつでもあるのですが、どういう問題にどういうアルゴリズムが合うかを知っていることがとても重要です。
――確かに専門家じゃないと選定は難しそうですね。
山本：最適化問題は一つひとつ異なりますし、すべての問題を解ける万能なアルゴリズムはないですからね。
樋川：だいたいのアルゴリズムは本当の最適な答えを出すには膨大な時間がかかりますが、それに近しい答えをみつけるのにはそこまで時間がかからないです。なので、どれくらいの時間をかけてどれくらいの精度の答えがでてくるのかを見極めることも大切です。
塩見：やみくもに精度を上げるために長く時間がかかってしまっては、それこそ使い勝手の悪いシステムになってしまいますから、お客様が許容できる時間との兼ね合いも考慮しなければならないのです。
――もう少し具体的にお聞きしたいのですが、お客様から組合せ最適化のシステム開発を依頼されたらまず何をするのでしょうか？
樋川：まずはお客様の現場を訪れ、業務の要件や求める計画の精度についてヒアリングを実施します。その上で、対象の業務問題に適したアルゴリズムを選択します。そしてプロトタイプをつくってチューニングをしていきます。
――チューニングとはシステムの性能をあげるためのチューニングですか？
塩見：性能のチューニングもありますけれど、チューニングの狙いは出てきた答えがお客様の業務に使えるかどうかです。出てきた答えをお客様にまず見ていただいて足りないところをたくさん指摘していただくことが重要です。
――足りないというのは何が足りないのですか
山本：先ほどの巡回セールスマン問題の応用例に「配車計画」というのがあります。配達とか集配とかのスケジュールです。たとえば我々が最初に提示した答えを見ていただいたときに、「このお客さんは午前中に行かなければならない」とか「Aのお客さんのあとにすぐにBのお客さんにいかなければならない」などのより具体的な条件がポロポロと出てきます。
――なるほど。最適化問題は一つひとつ異なるというのはそういうことですね。
山本：そうです。お客様の固有の条件を考慮しないと使えるシステムにならないのですが、最初のヒアリングですぐに出てくるわけではないんですよ。
塩見：最初に大まかな業務の条件をうかがって、その条件で出した答えを見てもらうと当然ダメ出しされます。そこで再度ヒアリングして出た答えを見てもらう、ということを何回も繰り返すんですね。そうするとだんだん使える答えになってきます。
樋川：問題が難しすぎる場合は問題を分割して解くこともあります。例えば多品種少量生産の工場で、ロット単位の生産を行う工程スケジュールを立てる場合、どういう注文のまとまりでロットをつくるのか。ロット内でどういう順番でモノをつくるのか。どの設備でつくるのかを同時にやらなくてはならない。その時には、まずロットのまとまりを作ってから設備ごとに並べるとか、並び方を考えてからまとまりをつくるとかひと工夫しないと解けないことがあります。
――結構時間がかかりますね。プロトタイプを作るのにどれくらいかかるのですか。
塩見：短くても一か月はかかりますし、標準的には3か月くらいかかります。
――みなさんはひたすら数式を解いているのですか
樋川：「こういう条件があります」と言われたらその制約条件を表現するような数式を定義して、それを追加して問題をアップデートしています。いろんなアルゴリズムを組合せてひとつの問題を解くということもしています。
組合せ最適化問題を1秒で解く量子アニーリング方式で何が変わるのか？
――最近、量子アニーリング方式で組合せ最適化問題が解けるということが話題になっているようですね。
山本：量子アニーリング方式は、2014年頃にカナダのD-Waveという企業が量子効果を利用して最適化問題を解く装置をつくりました。それをGoogleが実験して既存のコンピュータより1億倍はやく解けると発表して大きな話題になりました。それを引き継ぐかたちで日本のいくつかの企業が開発に取り組んでいます。
――日本が先行しているのですか？
山本：日本では盛んに研究されていますが世界的にはまだそれほど注目されている技術ではありません。いわゆるCPUを搭載したコンピュータみたいにいろんな計算ができるわけではなく、半導体のチップで「イジングモデル」という限られた組合せ最適化問題を解こうとしています。
――組合せ最適化問題を1秒で解くという記事もあるようですが
山本：私たちも各社の製品を調査しました。各社とも特徴が少しずつ違いますが、特定の問題に絞れば従来の方法に匹敵する性能が出ることもあることがわかりました。ただ組合せ最適化問題全般を解けるわけではなくまだ実用段階ではないと考えています。
樋川：ある特定の最適化問題が解けても実際の業務問題が解決できるかといったら別の問題です。
――なるほど。特定の問題が得意だということなら、単純に新しいアルゴリズムのひとつととらえればいいのですね。
山本：現段階ではその通りです。量子アニーラのツールを否定するわけではないんですが、それも含めていろんなアルゴリズムがあって、それをどういう問題にどう当てるのか、そのノウハウを持っていないと組合せ最適化問題はうまく解けません。
NSSOLが組合せ最適化問題に強いワケ
――NSSOLがこれまで手掛けてきたのはどのような分野ですか？
山本：私たちの親会社である日本製鉄の生産計画はたくさん手掛けています。製鉄所は広大な敷地にいろいろな工場がたくさんあります。ドロドロの鉄の成分を調整し固める工場から、固めたものを切っていく工場、鉄を薄くのばしていく工場など。各工程でロスが最小になるように、生産性を下げないように、かつ在庫を持ち過ぎないようになど、いろいろな指標がある中で、どういう順番で、どう組合せてどう最終製品をつくっていくか。組合せ最適化問題の宝庫です。
――製鉄の現場での適用というと歴史も古そうですね。
塩見：そうですね、歴史は結構長くてNSSOLの最適化の事例は20年くらい。シス研の源流は新日鉄時代にさかのぼるので、そこからカウントすると30年くらいでしょうか。私が小学生くらいの時から当社の最適化の歴史は始まっています（笑）。
――製鉄以外の分野というとどのような事例がありますか？
山本：鉄道は最適化が多く扱われている領域です。例えば時刻表です。時刻表って一般客からみると乗るほうしか書いてないですが、あの裏には車両の取り回しと人の取り回しがあって、間に回送列車も走っているんですね。そういうところまで全部決めないとならないし、車両に関しても何キロ走ったら点検するというルールがあります。社員にも労働時間や休憩時間があります。そういう条件を守っていくとなるとすごく大変なんです。
――生産計画だけでなくいろいろな分野に対応しているのですね。NSSOLの強みはそうした汎用性でしょうか。
山本：そうです。やはり生産計画が一番の強みですが、流通サービス系や物流分野も近しいです。
樋川：Jリーグさんは製造とは関係のない分野ですけど、技術を転用して実用化までもっていきました。
――なるほど。今までどれくらい実績があるんですか
山本：100例は軽く超えています。
塩見：我々の部隊には20名ほどメンバーがいますが、これだけの規模を持つ最適化の部隊はNSSOLだけだと思います。
――それだけニーズがあるということですね？
山本：おかげさまでたくさんお話をいただいています。
これから組合せ最適化問題で求められるもの
――今後、組合せ最適化はどのような方向に進むと思いますか。
山本：大きく2軸あると考えています。ひとつは、現在行っている最適化。特に生産現場における組合せ最適化を推し進めることで、これまで熟練の人材が行ってきた生産工程のノウハウをシステム化し、後世にも伝えていける体制を整えることです。
もうひとつは、トラブル発生時の意思決定の選択を提案できるような、言ってみれば広義でのAIのような機能を付帯させることで、より使い勝手のよい組合せ最適化ソリューションに発展させていくことです。
このような実ビジネスの応用は、まさにこれからシス研に求められているものでもあります。このあたりについては、また次回にお話しさせていただきます。
――そうですね。今日はどうもありがとうございました。次回も楽しみにしています！
