世界最速のPCが1年かかる問題に1秒以下で解答可能　ビジネスの課題を解く「数理最適化」の活用術

航空会社の運行スケジュール策定にも使われる、意思決定の仕組み

カート・ミュラー氏：みなさま、こんにちは。今日はお越しいただきましてありがとうございます。私はKurt Muellerと申します。営業のVPをしています。

私たちの使命ですが、「どこでもGurobiを使っていただきたい」という願いを込めて「Gurobi Everywhere」という言葉を挙げています。

というわけでパートナーさま、お客さま、クライアントのみなさま、日頃のご愛顧をいただきありがとうございます。すべてのお客さまにグローバルにGurobiをお使いいただきたいと考えています。

私たちは毎日個人レベルでも企業レベルでも大きな意思決定、また小さな意思決定をしています。そして適切な意思決定をする際にはデータが必要となります。

おそらく今日何を着たらいいのかに関しては、みなさんも人からの手助けは必要ないかと思います。みなさんご自身で決められるかとは思いますが、それでもデータが必要です。こういった問題を解決するのは、奥さまやご主人の方、ボーイフレンド、ガールフレンドの意見だったりしますね。



また、大きな意思決定で考えますと、基幹業務系の意思決定がございます。飛行機会社、航空会社では、日々の運航のスケジュールを決めていくような意思決定がございます。



こちらは、何百万というデータポイントが必要です。そして、燃料費を最低限にすると燃料需要の効率化を図っていけますし、エコシステムや世界経済に対しても価値を提供することができます。



この事例はGurobiがどれだけパワフルなのかを示しています。アメリカのすべての州都を結ぶ最短経路を探したい場合、「数理最適化技術」を活用すれば解決時間は1秒未満です。しかし、世界の中でも最速のコンピューターをもってしても、「数理最適化技術」の活用なく探索した場合、1年以上かかってしまいます。

顧客満足度98％、導入6ヶ月以内のROIは500％超

私たちがどういう企業なのか。



私たちGurobi社は、1987年にCPLEXを設立したDr. Bixbyと、Dr. Rothberg、Dr. Guの3人により、2008年に設立されました。現在エキスパートの中で35人以上が博士課程を修了しています。毎日お客さま、エンドユーザーの方々、そしてパートナーさまのお手伝いをしています。






このスライドの中で最も重要な数字は98パーセントです。これはお客さまの満足度のスコアになっています。もう1つは518パーセントで、導入後6ヶ月以内のROI（投資収益率）を達成しています。
※Forrester社に依頼した2022年9月の分析に基づく。この分析では、架空の顧客と仮想シナリオを用いて、Gurobi Optimizerの潜在的な財務効果を評価しました。



そして私たちの競争優位性ですが、私たちの創始者は世界で最も速く最もパワフルな数理最適化ソルバーの構築を目指したわけですが、それを実現できていると考えています。最初のバージョンのソルバーと現在のものを比べますと、そのスピードが80倍になっています。



では、Gurobi Everywhereという言葉ですが、世界中で投資をしているという意味で使っています。2025年および2026年ですが、日本やアジア太平洋地域で、非常に大きな財務的かつ人的な投資を行っていく予定です。

「数理最適化技術」とは何か？

中沢礼氏（以下、中沢）：続きまして、株式会社オクトーバー・スカイ最適化コンサルティング部シニアコンサルタント乾伸雄より、数理最適化の基本概念と実務への適用方法について説明させていただきます。乾さん、よろしくお願いいたします。

乾伸雄氏（以下、乾）：あらためまして、オクトーバー・スカイの乾と申します。どうぞよろしくお願いします。

今日は「数理最適化の基本概念と実務への適用方法」という堅苦しいタイトルです。最適化とは、私たちは最適化するために数理モデルを作っているんですが、何を考えて作っているかを説明します。Gurobiがどのようなところで使われているのかをご紹介したいと思います。



スライドのような流れで話していきたいと思います。最初の基本概念を説明する時に……この中でGurobiを使われている方がいると思うんですが、生産スケジュール作成に使われている方はどのくらいいるか、もしよろしかったら手を挙げていただけたらと思います。

（会場挙手）

何人かいらっしゃいますね。

まず、何を考えてやっているかについて話していきたいと思います。簡単に自己紹介いたしますと、オクトーバー・スカイに約10年前に入社しました。このようなコンサルティングやユーザーサポートの業務を行っています。



これまで20以上のプロジェクトを担当ということで、コンサルティングをしまして、お客さまからご依頼を受けて作っています。スライドに書いてあることで、何やっているのかが想像がつくと思いますが、いろいろな種類のものを担当させていただいています。

まず数理最適化は、数理モデルを作って、それをGurobiによって解かせることで問題を解決する手段になります。数理モデルとは、目的関数、制約条件、変数条件という3つの要素からなっています。これを言葉ではなく数式に落とします。



ここに数式、簡単な数式を書いています。この式の「X」や「Y」は変数と呼んでいますが、これが満たす条件も不等式みたいなもので書いてあげる。こういったものを数理モデルと呼んでいます。

特に、各々が何を意味しているかというと、目的関数はお客さまの何かを良くしたい、良くするような解を求めたいというものが普通です。「何かを良くしたい」というものが目的関数です。制約条件は「こういった解を満たしていなければいけない」という条件が書かれたものです。

こういう制約条件や目的関数をどうやって書くか。どんな変数を用意するのかという3つの要素からなっています。

生産スケジュールを例に数理最適化を解説

乾：今日の話は、生産スケジュールを例にしたものです。生産スケジュールで各々の目的関数や制約条件でいうと何に対応するのかというと、例えばこういったものが生産スケジュールにおける数理モデルで書かなければならない事柄になります。

さらに具体的にこの生産スケジュールの話をしていきたいと思います。いろいろな種類の生産スケジュールがあります。ここでは製品がAからHまでの製品があります。各々の製品、どれも工程1、工程2、工程3という3つの工程で作られるものになっています。

スライドに書いてある数字は、各製品を作るのにどのくらい工程で時間がかかるのかを数字にしたものになります。



各工程で使われる機械にどういう機械があるのかがここに書かれています。例えば、工程1だと2台の機械で作ることができます。どっちで割り当ててもいいんですが、どちらかの機械に割り当てて作ることができます。

実際の問題よりは、かなり問題を単純化しています。数理モデルというか、モデルを作る時にはこういうデータが必要になってきます。表にあるようなデータが必要です。どういったものが解か、どういったものを解としてほしいのかは考える必要があります。

例えば、出力のイメージとしてはこういうガントチャートになっています。このガントチャートは各々の機械ですね。

E1aという機械だと、最初はHをやってAをやってG、EをやってFをやる時間の流れに沿って、どの製品をこのE1aで処理していくのかが書かれているものです。この幅がここでの時間になります。

各々の機械があって、例えば機械から機械に、工程1から工程2に移っていきます。Hの製品は工程1が終わった後に工程2に進んで、工程3に進んでいって、（ガントチャートに図示しているように）時間がずれていく。こういったものが生産スケジュールのイメージになるかと思います。

私たちが数理モデルを作る時には、こういう入力が重要です。出力として欲しいものがどういうものかを頭の中でイメージしていく。

それに基づいて、先ほどの数式を作っていくことが必要になってくると思います。数理モデルは目的関数と制約条件と変数という3つの要素からなっていきます。

変数、制約条件、目的関数の順番で考える

乾：出力となるもの、ガントチャートを出力するのにどういった変数が必要になるのかを、次に考えなければいけないことになります。

なので、目的関数、制約条件、変数と書きましたが、順番は逆です。どちらかというと変数を最初に考えて、制約条件を考えて、目的関数を考える順番になるかなと思います。

このガントチャートを見た時にどんな変数が必要になるかを考えると、まず製品Xの各工程でどの機械を使うかで、1つの製品を生産するのに工程1から1つ、工程2、工程3から1つ選ぶので、どれかから選ばなければいけないのかを考える必要がある。これは変数の1つになります。



その次は、1つの機械で生産する時には、製品の間の順番関係がついてなければいけないことを考えなければいけません。この場合ですと、1つの機械に生産を割り当てられた時に、製品Aと製品Bはどっちを先の順番でやるかという、工程の順番を考えなければいけないかと思います。

その中で一番重要かもしれませんが、各機械で製品にする時に、この製品がいつ生産開始になるのかを考えなければいけないという3つですね。これは各製品の生産開始時刻でも、終了時刻でもかまわないです。

このガントチャートを見て、どういう変数が必要なのかと考えた時には、私は「どの機械にまでやっているのか」「どういう順番でやるのか」「いつやるのか」というものを、変数にしなければいけないかなと考えることにしています。

これは、人によって考え方がいろいろ違うかなと思います。

次は目的関数にいきますが、先ほどの変数を書いたら、今度の制約条件は最後に回します。この場合の目的関数とは何かを考えると、生産スケジュールでよくあるのは、一番最後に終わる時間ですね。一番最後に終わる時間を、一番短く小さい値にしたいことがあるかと思います。



この場合ですと、工程3が生産の一番最後の時間になるので、工程3の終わりの時刻ですね。（長さがまちまちなガントチャートを指しながら）一つひとつの製品は、ここで終わったり、ここで終わったりもすると思います。

たくさんの候補があった時に、この中で一番大きな数を一番小さくすることを考える必要がある。それも数式で書くことができるんですが、こういうことを目的関数として考えることになります。

制約条件を考える際に重要なポイント

乾：最後に制約条件で、これは複雑です。さきほど、変数でどの機械で生産するかを言ったんですが、変数だけでは決めることができません。それは制約条件として書いてあげる必要があります。



この場合だったら、製品ごとに各工程で使える機械を1つに割り当てます。その他、2つの製品を同じ機械で生産する時には、開始時刻の間に処理時間以上の間隔を空けなければいけません。

順番関係と開始の時間をさきほど変数で作ったんですが、それを使って並べるわけですね。こちらが最初だったら、この時刻に処理時間を足したもの以降じゃないと、この製品は生産できないと、制約条件として書いてあげることになります。

もう1つは比較的単純なものですが、ある1つの製品で工程1の生産が終了しないと工程2は開始できないという感じになります。こういう3つの制約条件を書くことによって、このガントチャートの意味していることを表現します。

ガントチャートからどういった制約条件が必要なのかを考えて書いていく。そんな感じで、数理モデルを作る過程はこうなるかなと思います。

これはGurobiで書いたプログラムなんですが、変数を作って、制約条件を作って、目的関数を設定するプロセスはプログラムで書くことができます。見たとおりプログラム自体はすごく短いです。



だいたい私がやっているようなプロジェクトでも、多くても数百行ぐらいかなという。モデルを作るのはそのくらいの規模です。モデルを作るプログラムはそんなに大きくないかなと思います。

ただ、どういうモデルを作るかは非常に重要なので、そこには時間をかけるべきだとは思います。基本的にはプログラム自体はそれほど大きくならないのが普通かなと思います。

こんな感じで、Gurobiのプログラムはお時間がありましたら、資料をご覧いただければと思います。

Gurobiは大規模な問題でも解くことができる

乾：Gurobiで実行すると、画面にGurobiの実行の履歴やログが表示されることになっています。だいたいのお客さまは、こういったGurobiのログを見て、ここに問題があるかなぁとか、いろいろな問題点を見つけることになります。



Gurobiはこういうログを提供していますので、実際に最適化している時の過程から、モデルの問題点や、何か改善しなければいけないような事柄を見つける感じで進めていただければと思います。

ログを初めて見られる方にとっては、たくさん書いてあってわからないかと思います。私たちはユーザーのサポートの一環として、こういうログの見方や、お客さまの実際のログを解析するサービスを提供しています。実際に使われている時には、いろいろご相談いただければと思っています。

先ほどはすごく小さい例だったんですが、100製品をやってみたもので、機械の数は変えていますがスライドのような感じです。

テストはかなり小さい規模の問題を扱ったんですが、実際のお客さまの問題は、大規模な問題があります。Gurobiの性能は、そういうお客さまの問題を解くのに十分使えると考えています。こんな大規模な問題も解くことができます。



その他に、お客さまによってはいろいろ目的関数を変えて、結果を見てみたいと言うお客さまもいらっしゃいます。

例えば、スライド上は一番最後の時間を短くする結果でした。その他に満遍なく各製品の終わる時間を短くしたいといった目的関数を設定して結果を見たい方もいます。



終わりの時間を合計したものを一番小さいかたちで最適化を行っていますが、結果が悪くなっていくんです。こういったところで早く終わる製品も多々あるという感じの結果が得られることになります。

こうやって、1つのモデルを作ったら目的関数を変えてみて、いろいろな結果を見ると、たくさんの発見があると思います。

AI学習とGurobiを組み合わせる事例も

乾：Gurobiが解ける問題はホームページにも出ています。最近はAI的な学習ツールがいろいろ揃っていますので、お客さまによってはデータから直接入力するのではなくて、入力データをある程度学習させて、数理モデルに入れて解かせるパターンのお客さまもいます。



例えば、需要予測みたいなものをAI学習で入れて、その需要予測に基づいて問題を解くという、AIの学習との組み合わせで問題を解くお客さまもいらっしゃいます。

そのためにも、Gurobiの中でもAI学習で作られた実際のモデルを、Gurobiの数理モデルの中に取り込むことができるメカニズムを用意していますので、もし機会がありましたら、活用いただければと思います。

既存のシステムでこういったGurobiを使った時に「どうやって、今まで自分たちの使っているシステムに入れていったらいいのか」という質問を受けることがあります。

これは一例なんですが、今までは入力の情報があって、使っているソフトウェアがあって、出力を出していました。使っているソフトウェアの中でGurobiを呼び出してもらったり、数理モデルを解くプログラムを呼び出すかたちで使われることが多いんじゃないかと思います。



お使いのたいていのソフトウェアでは、ファイルに出力したり、データベースに入れたりする機能があります。その時には、ファイルやデータベースの情報を入力情報としてプログラムが受け取って、最適化をして出力します。

そういったかたちで、特に今お使いのソフトウェアを直すことなく使える部分が多いんじゃないかとは考えています。

問題を分析して、条件と狙いを明確にするのが重要

乾：数理最適化の実務への適用ということで、弊社は例えばこういうシフトスケジュールのデモやカッティングストックのデモ、裁断計画のデモを用意しています。



Gurobiのホームページにいろいろなケーススタディが載っています。横にたくさん書いてありますが、いろいろな種類の分野、いろいろな産業の事柄に対してGurobiが使われている例になると思います。



こういうところを探されると、みなさまの考えているものが適合してくると思いますし、私個人としては既存のものだけではなくて、いろいろ新しいものにチャレンジしていきたいなと考えています。

最後のスライドになりますが、最適化のシステムを構築するにはいろいろな手順が考えられると思います。まず重要なのは問題を分析して、条件と狙いを明確にすることで、いわゆる要件仕様作りと呼ばれているところです。



曖昧なところから始めてしまうと、予想もしなかったような答えが得られてしまいます。問題を分析するところが重要かなと思います。その後に最適化問題として定式化するなどして、解いてみた結果の問題がある時には、ここに戻っていろいろと考え直すサイクルになるかなと思います。

今日はこんなかたちでお話をしてきましたが、Gurobiについて何か質問等ございましたらお答えできるかと思います。

中沢：「本番の時も色分けを使うのですか？　それとも今日の説明のために色分けを使ったのでしょうか？」というご質問をいただきました。

乾：そうですね。実際のシステムですと、目で確認するためにはガントチャートは重要なんですが、たいていの場合は、テキストファイルで出力することが多いです。今日はみなさんが見る時にわかるように色分けしていますね。

これはGurobiの機能でもなんでもなくて、Pythonのプログラムの機能で書いています。この色分けはわかるようにしている感じです。

たいていの場合は、例えば製品ごとに、製品Aの工程1はいつ始まって、いつ終わって、工程2はいつ始まって、いつ終わる。そんなかたちでテキストファイルで表示されるのが普通かなとは思います。

中沢：乾さん、ありがとうございました。

（会場拍手）

乳製品を巡る、知られざる複雑な問題

中沢：続きまして、Gurobi社APAC担当営業ディレクターのIain Jardinより、海外最新事例として乳製品会社A社さまの事例を紹介させていただきます。Iain、よろしくお願いします。

イアン・ジャーディン氏（以下、イアン）：本日はお招きいただきまして、どうもありがとうございます。日本に来られて非常にうれしく思っています。私はGurobiに入社して、2年ほど経過しています。

今日は、みなさんに牛について、非常におもしろいお話をさせていただきたいと思っています。

Gurobiで働いているすばらしい点の1つといたしまして、多くのお客さまや業界と接することができることにあります。お客さまが抱えている複雑な問題を、私たちのソリューションで解決できる点にあります。

そのお客さまの一例として、グローバルな乳製品会社がございます。こちらの会社ですが、世界で生産されている乳製品の30パーセントを製造しています。



牛乳は非常に特別な商品です。そのままでは24時間保たないんですね。ですから、その生乳を使って24時間以内にどのような製品に転化するかを考えなければいけません。ただ、その製品をどれに転化するかを考える時には、お客さまの需要も考慮する必要があります。

農場から生乳が送られてくる時には、そこに含まれる乳脂肪分はさまざまです。高い時もあれば低い時もあります。商品によっては、乳脂肪分が高いものには適さないものもありますし、そのまた逆で乳脂肪分が低いものが適さないという商品もあります。

また残念なことに、乳牛は、お客さまの需要に応じたかたちでの乳脂肪分の調整はできないんですね。ですから、実際にそこで生産される生乳の乳脂肪分に応じて、お客さまの需要に合う商品を製造していくことが必要になってまいります。

生乳の用途を決定するタイムリミットは24時間以内

イアン：これからするお話は、実際にその乳牛から生乳が生産されて、お店に並ぶまでのお話になります。

実際にまず一番最初の問題ですが、その生乳がどこから来るのか。どの乳牛で、乳脂肪分はどれだけ含まれているのかです。

次の問題は、実際にその必要な場所に、必要な時間軸の中で、どこに運んでいくのかという点になります。

必要なところに生乳を持っていった時の大事な問題は、「そこで何を製造するのか」になってきます。そして、この決断はすべて24時間以内に行う必要があります。もし24時間以内に決めることができなければ、生乳は無駄になってしまって、本当にそれを廃棄しなければいけません。

そして最後の問題ですが、その作られた製品をどこで販売するのかです。ですから、牛乳・チーズ・バターなどのそれぞれの商品は本当に簡単に思えますが、こうした複雑な過程を経て製造されて運ばれていくんですね。



この製造、そしてサプライチェーン、経済的な観点からも、非常に複雑なものが絡んでいることがご理解いただけるかと思います。

実際に乳製品を製造する側として、何を考慮しなければいけないのかをこちらに挙げています。何の製品を作るのか。実際にその製品にあった乳脂肪分が含まれている生乳があるのか。製品によって生産コストも違ってきます。市場の需要、誰がどこで、いつ欲しいのか。

そして生産能力ですね。実際にパイプなどのその他の機器に関しても5時間ごとに清掃する必要があります。これらすべてが最終的な利益率に関係していきます。

数理最適化で乳製品の計画プロセスを予測

イアン：そういった中でGurobiが果たす役割とはどのようなものでしょうか。

私たちが行うことは、この制約の中において、あらゆる変数や変動するような要因を含めたかたちでサプライデマンドに対応することです。多くの生産ラインをマネージします。

この市場の需要や生産の能力に応じて、拡張性を柔軟に対応していきます。もしこうなったらどうなるかという、いろいろなシナリオに関してフレキシブルに対応します。

もしも最初に想定していたものと生乳の状態や乳脂肪分が違った場合に、どういう対応を行うかまで考慮していきます。実際にこういうことを考慮することによって、乳製品の生産業者は、実際に入ってくる製品、市場の需要に対応することが可能になっていきます。



乳製品の業界は、入ってくる商品の乳脂肪分をコントロールすることはできません。入ってくる生乳でどういう製品構成にするのかを事前に決めておくこともできない状況です。



ただ、Gurobiの製品を使うことによって、次に何を行うかを予測すること、対応することが可能になります。そこで迅速に決断できるので、すばやく対応できることになります。この意思決定を簡便に、簡潔に行うことが可能になるわけです。その結果が最適化されていきます。



実際の計画のプロセスに変換させていきます。そうすることによって、生産の効率を上げて、コストを下げる。生産能力をアップします。以上です。どうもありがとうございました。