第5回：なぜデータサイエンティストが数理最適化を行うのか【ブレインパッドの数理最適化ブログ】

デートで考える数理最適化

ここだけの話、もともと考えていたタイトルは、「チートスキル数理最適化で異世界無双」でした。しかし、異世界転生しなくても数理最適化が役に立つという話をしなければ！と考え直したので、今のタイトルに落ち着きました。今回は、現実世界で最も切実な問題と言っても過言ではない「デート」を題材に、数理最適化とはなに（What）で、なぜ（Why）、どのように（How）行うのか、というようなことをお伝えしたいと思います。

まず皆さんにお伺いしたいのですが、「デート」に誰かを誘ったことはありますでしょうか？私はというと、大変小心者で、相手の方にがっかりされたらどうしようと、そればかり考えて肝心の内容がおろそかになりがちでした。数理最適化を知っていたらこんなことにはならなかったのに…

そうです。数理最適化を知っていたら、デートは大成功間違いなし！と言いたいところですが、そのためにはある条件が必要となります。それは後で述べたいと思います。

ただし、少なくとも数理最適化の考え方はすぐにでも役に立つと思います。

数理最適化とは何か、なぜするのか

さて、人はなぜデートをするのでしょう。とても哲学的に聞こえますね。（ついつい入れたくなるチャチャは置いておいて）ちょっと考えてみてください。

…

大変難しい問いだと思った人も、わかり切ったことを聞くなと思った人もいることでしょう。私自身は…恥ずかしながらよく分かっていませんでした。たぶん若いころは、そこにデートをしたい人がいるからだ、くらいにしか思っていなかったと思います。デート自体が目的、浅はかでしたね…

でも前段で、私は書きました。「相手の方にがっかりされたらどうしよう」と。そうですね、相手の方に喜んでもらいたいとは思っていたに違いありません。付き合う前、あるいは付き合ってすぐだったら、相手の満足度を上げようということが最終的なゴールとなりそうです。このように、「満足度」なるものが数量化できたとして、これをできるだけ高く、できればMAXにしたいわけです。数理最適化の言葉でいえば、「満足度」が目的関数となるわけです。

さて、「満足度」は何によって決まるでしょうか？そうです、デートで何をするかです。それでは計画を立てましょう！待ち合わせはいつどこで、服は何を着て、最初はどこに行って、ランチはどこで食べて、メインイベントは何で、いつまで一緒に過ごすのか、このようなことを事前に決定するわけです。数理最適化の言葉でいえば、プランニングが決定変数です。

さてさて、現実は厳しく、ヘリコプターで上空から夜景を眺めたり、クルーザーで豪華なディナーをしたり、ということができる人はごく少数でしょう。そうです、デート費用（コスト）には限りがあります。また、プレゼントを用意しようとしたときに、デートの日に間に合わなければ意味がありません。そうです、納期です（苦しい…）。数理最適化の言葉でいえば、プランニングには制約があるのです。

今までは、満足度（品質）を目的関数としてデートを捉えました。この場合、目的関数を最大化したいわけです。一方デートのベテランになってくると、満足度が一定以上あればよく、デート費用（コスト）を抑えたいということもあるでしょう。この場合、コストが目的関数、満足度が制約になり、目的関数を最小化することになります。

まとめると、制約を満たす中で、目的関数を最大化・最小化するような決定変数を求めること、これすなわち数理最適化です。

ちょっと強引に品質、コスト、納期、すなわちQCDに結びつけました。言わずもがなですが、各産業にも数理最適化の枠組みに収まりそうな問題がたくさんあるということをお伝えしたい、そんな下心が出てしまいました。

いずれにしても、目的関数が何で、決定変数は何で、制約は何か、そしてこれらを数理的に （例えば数式で）表すこと（この作業をモデリングといいます）ができれば、あとは解くだけですね！


ここまで、数理最適化の「What」のお話をしてきました。Whatが分かれば、Whyもおわかりですね。いつまでも「相手の方にがっかりされたらどうしよう」などとくよくよしている訳には行きません！プランを立てましょう！そうです。意思決定のために数理最適化をするのです。

数理最適化が使えるための条件

ここまで読んでこられた皆様の多くは、「なぁんだ、結局数理最適化なんてデートには役に立たないじゃないか」と感じられたかと思います。なぜか？それはデートを数式で表すことはできないからですね…

いやいや待ってください。それは本当でしょうか？先ほどモデリングという言葉が出てきました。うまくモデリングできれば、数理最適化が使えるのです！

モデリングとは、モデル（模型）を作るという意味です。そしてモデルというのは、考察対象から枝葉末節を取り除き、本質的な部分を残したものであるという意味合いがあります。

例えば、デートの時間は13時から17時の4時間、その間に何をするかを決めたいとしましょう。そして、候補はあらかじめ見繕っておきます。例えば、散歩、パンケーキ、カラオケ、ボーリングなどです。それぞれどれくらいの時間がかかるかというのはだいたいわかります。難しいのは、相手の満足度がそれぞれどれくらいなのかです。そこは事前にリサーチ！また、デートの満足度が個別企画の満足度の総和になるとは限りませんが、割り切って総和で表せるとします。そうすると、この問題は「ナップサック問題」という問題になります。ちなみに、ナップサック問題に関しては、数理最適化ブログシリーズの第2回でとり上げています。

第2回：ナップサック問題を色々な方法で解いてみた【ブレインパッドの数理最適化ブログ】 – Platinum Data Blog by BrainPad

デートの総時間をナップサックの耐久度と考えることにします。各企画にかかる時間を重量とみなします。企画をデート中に実施するということをナップサックに荷物を加えることと見なします。そして、規格の総重量がナップサックの耐久度を超えるような企画たちをデートで実行することはできないと考えます。この制約のもとで、各企画の満足度の総和を最大化する問題、これすなわちナップサック問題です。

もちろん、ナップサック問題によるモデリングでは足りないこともあります。例えば映画だったら上映時間が決まっていることでしょう。映画館が遠ければ移動時間も考えた方がいいですね。相手の疲れも考えなくては。もちろん費用も… ただし、これらは制約条件を工夫すれば片づけられそうです。

以上までをまとめると、数理最適化が使えるための条件は以下の通りとなります。

+ モデル化できること
+ パラメータが既知であること


ここで、パラメータとは、上でいう企画の消費時間や満足度のことです。先ほどは「事前にリサーチ！」で済ませましたが、パラメータを決めるのも簡単なことではありません。さらに現実をいうと、上記2条件が揃ったとしても、最適解を実用的な時間内に求めることが困難なこともあります。そのようなとき、計算時間を決めて、その時間内に探索した解のうち目的関数値が最もよい解を使うことが多いです。デートをしないよりはした方がいいですからね。

データサイエンティストと数理最適化

以上、イタいのは承知で、デートを題材に数理最適化を説明してきました。また、ところどころで下心が見えていましたが、数理最適化の産業応用のポテンシャルをこっそり示してきました。

さらにしつこくデートを例にとりますが、相手のことが好きなあまり、なぜ一緒の時間を過ごすのかに考えが及ばなかった、そんなことはないでしょうか。産業応用でも同様に、問題の重要さのあまり、どこから手を付けてよいのかわからないことがあると思います。そんなとき、まず、問題を小分割することを考えます。人・物・金・情報という視点から見ると整理できると思いますし、戦略・戦術・作戦レベルといった時間的空間的な粒度で見てもよいかもしれません。経営学的な思考が大変役に立つと思います。

そうすると、問題意識が具体化します。具体化した問題のうち、いくつかは数理最適化向きの問題もあることと思います。典型的な例を挙げれば、限られたリソースを用いて、最大の売上を得る（生産計画問題）などです。こう書くと簡単そうですが、現実的な問題を数理的に記述する（モデル化）という段階を行うにはそれなりのスキル・センスが必要です。このあたりに関しては、

第4回：在庫問題と配送問題をドッキング！大規模最適化時代で何が変わる！？【ブレインパッドの数理最適化ブログ】 – Platinum Data Blog by BrainPad

も併せてご覧ください。


さてもう一方の条件、パラメータが既知であることに関してです。近年、DX（デジタル・トランスフォーメーション）推進が叫ばれています。実際弊社でも、製造工程最適化や物流最適化といった、大量データに基づく意思決定案件が増えています。DXが企業に浸透するにつれ、パラメータを求めるのは一見容易になるように見えます。もちろんデータがそもそもなければ始まらないのは事実ですが、データが大量にあることによる困難があります。そこでデータサイエンティストの出番です。

以上の2点に関して、もう少し詳しく書きましょう。例えば、ある小売チェーンにおける在庫管理を考えます。このチェーンは、自前で物流システムを持っていて、小売店からの日々の発注に応えるように仕入れを行い、在庫を持っているとします。このとき在庫の上限は、倉庫の大きさで決まります。したがって、売れない商品をいつまでも在庫として持っていると、売れる商品の在庫量を圧迫してしまいます。そこで、どの商品がどれだけの需要があるかという需要予測がとても重要です。

需要予測に関しては、過去の需要の履歴が蓄積されていれば、とても役に立ちます。ある種の商品は気象条件に左右されることが分かっており、気象データも需要予測に使うことになりそうです。個別の商品だけでも需要に影響を与える要因はたくさんあります。更に複数の商品を組み合わせて考えると、より複雑になります。

例えば果物で考えてみましょう。人によって特定の果物を食べたいという好みは必ずありますが、多くの場合、複数ある選択肢から1つ2つ選ぶのが消費者というものでしょう。この観察のもとでは、個別の果物の需要だけを見ていると、在庫にムダが生じかねません。果物全体の需要を考え、その中で個別の果物をどれだけ売れるように在庫を持つか、というように考えることになるでしょう。このように、対象となるドメイン知識が、よりデータを「活かす」ことにつながります。

次には、需要予測を踏まえて在庫量を決定することになります。ある種の意思決定ですから、数理最適化の出番です。ですが、得られた最適化問題のパラメータは確率的変動を伴います。そこで、データサイエンティスト的な素養が必要となります。

最終的には、複数のデータソースを加工して流していくシステムを構築することになります。この場合、日々の小売店のオペレーションを考慮することになります。いつデータが入力されるのか、いつまでに加工済みのデータが利用可能にならなければならないのか、などですね。DX時代、日々の意思決定を的確に行うというダイレクトなミッションだけでなく、システムとしての可用性が大前提として求められています。

以上のように、数理最適化を産業応用する際には、業務を捉えるビジネス力、問題をモデル化するサイエンス力、オペレーションに合わせたシステムを構築するエンジニア力が求められます。まさしく、データサイエンティストに求められているスキルセットと同じです。


私たちブレインパッドでは、企業の問題解決をデータの側面からトータルにご支援しています。本ブログシリーズでも執筆していますが、数理最適化に強みを持つデータサイエンティストも多数在籍しています。ご相談などお待ちしております。

数理最適化の勉強をしたいあなたに

残るは、数理最適化のHowの話です。

数理最適化で扱う問題の多くには、名前が付けられています。先ほど挙げたナップサック問題以外にも最短路問題、巡回セールスマン問題、線形最適化問題 (線形計画問題) などが有名ですね。

一方、解法にも名前が付けられています。かの有名なシンプレックス法は線形計画問題の解法です。ダイクストラ法は最短路問題の解法です。

上でモデル化という作業を挙げました。モデル化は、例えば混合整数最適化問題として定式化するなどをして行いますが、よく知られている問題に関する知識がここでは非常に役に立ちます。

本ブログシリーズは、

第1回：最近学んだ数理最適化の定式化のチップスたち 【ブレインパッドの数理最適化ブログ】 – Platinum Data Blog by BrainPad

では混合整数最適化問題としての定式化の話を、

第2回：ナップサック問題を色々な方法で解いてみた【ブレインパッドの数理最適化ブログ】 – Platinum Data Blog by BrainPad

ではナップサック問題を題材とした一般的な解法の話を、

第3回：はじめての配送計画の列生成法【ブレインパッドの数理最適化ブログ】 – Platinum Data Blog by BrainPad

では配送計画問題を題材とした列生成法という解法の話を、

第4回：在庫問題と配送問題をドッキング！大規模最適化時代で何が変わる！？【ブレインパッドの数理最適化ブログ】 – Platinum Data Blog by BrainPad

では在庫問題・配送計画問題をトータルな視点での解説を、それぞれしています。


本ブログシリーズを通して、もちろん企業のお客様に弊社のことを知っていただきたいという意図もありますが、若い世代へ向けての数理最適化の普及という意図もあります。少しでもお役に立てたら幸いです。

日本では、日本オペレーションズ・リサーチ学会という学会が、数理最適化を含む日本のオペレーションズ・リサーチに関する研究をけん引しています。日本オペレーションズ・リサーチ学会の学会誌は、その名もずばり「オペレーションズ・リサーチ」と言います。

http://www.orsj.or.jp/e-library/elcorsj.html

なんと、「オペレーションズ・リサーチ」の記事は、上記リンクをたどっていただければ分かりますが、学会員でなくても無料で閲覧することができます。社会貢献を重視している学会です。

「オペレーションズ・リサーチ」では、高校生に向けた特集が定期的に組まれます。最近は間があいていますが、最近ですと第60巻第9号（2015）の特集「高校生に向けたOR」があります。高校生だけでなく、大学生や大学院生、社会人にも楽しめる内容かと思います。また、第64巻第1号（2019）の「OR教育の系譜と現在」という特集では、各大学のOR教育のカリキュラムや研究活動が紹介されており、高校生の進路選択の参考になるかと思います。

ちなみに、オペレーションズ・リサーチというのは数理最適化を含むより広い研究分野です。オペレーションズ・リサーチは、待ち行列理論やゲーム理論など、数理的な基礎に立った意思決定法を含みます。筆者の知る限り最も早くオペレーションズ・リサーチについて書かれた書籍 [1] によれば、以下の定義が書かれています。

Operations Research is a scientific method of providing executive departments with a quantitative basis for decisions regarding the operations under their control.

直訳すれば、「オペレーションズ・リサーチとは、管轄下のオペレーションに関する決定を行うための定量的な基礎を管理部門へ提供する科学的な方法である。」となるでしょうか。まさに意思決定そのものを扱う学問です。

2020年は新型コロナウイルスの問題で、教育界も大変混乱しました。一方で、授業内容を動画におさめ、YouTubeなどの動画配信サービスで公開し始めた先生方もいらっしゃいます。ここでは具体的には挙げませんが、興味のある方はぜひ探してみてください。

[1] P.M. Morse and G.E. Kimball, Methods of Operations Research, National Defense Research Committee, 1946.