「数理最適化」とは――4つの応用事例、実問題適用への手順、機械学習との違い、使い分け方：リクルート事例で分かる数理最適化入門（1）

リクルートにおける数理最適化の応用事例の紹介を通じて、数理最適化とは何か、どのようにビジネスに応用できるのかを紹介する連載。初回は、数理最適化の概要、リクルートにおける4つの応用事例、実問題適用への手順、機械学習との違い、使い分け方などについて。

[須藤遼介，リクルート]

　近年多くの企業で、ビジネスでのデータ活用が当たり前になっています。中でも機械学習を用いた成功事例については、耳にしている読者の方も多いと思います。一方で、同じくデータ活用の技術である「数理最適化」は、さまざまな領域で成果を上げているにもかかわらず、その実態について知っている人はあまり多くないようです。

　本連載ではリクルートにおける数理最適化の応用事例の紹介を通じて、数理最適化とは何か、どのようにビジネスに応用できるのかを紹介します。読者の皆さんがデータ活用の手法の一つとして数理最適化を利用できるようになるきっかけになれば幸いです。

数理最適化とは

　数理最適化とは「現実の問題を数式（数理モデル）として定義し、制約条件を満たしつつ、コストの最小化や利益が最大化されるような変数の値を求める手法」のことです。ここでいう、「最小化or最大化したい対象であるコストや利益などの数値を数式で表したもの」を、数理最適化では「目的関数」といいます。

　数理最適化を現実の問題に適用するには、まず最適化したい現実の問題に関して「目的関数」と「制約条件」を数理モデルとして定式化します。その後、その数理モデルを解くのに適した最適化アルゴリズムを選択し、目的関数を最大化or最小化する変数の値を算出します。

　数理最適化では、一度定式化すれば、新たなデータが与えられるたびにアルゴリズムによって最適な変数の値を自動で算出できます。そのため、人間が毎回データを見てからしていた意思決定を自動化、支援する手法として、ビジネスや社会で幅広く利用されています。

数理最適化のフロー

リクルートでの数理最適化応用事例4選

　数理最適化のビジネスへの応用について具体的なイメージを持てるように、ここからはリクルートで数理最適化を利用した事例の一部を紹介します。なお事例の詳細は後の連載でまた紹介するので、本稿では概要までとします。

ユーザーへのレコメンドメールの最適化

　リクルートでは、各サービスのユーザーに対してお薦めの商品やイベントをお知らせするメールコンテンツを配信しています。

　コンテンツに関しては、各ユーザーの最も関心の高いメールを配信したい一方で、各サービスが持つ「最大配信可能メール数」「一定期間優先して配信したいコンテンツ」といった事業制約を守る必要があります。そのため、単純にユーザーごとに最も関心が高そうなコンテンツをメールで配信する手法を採ることができません。そこで、事業制約を満たした上で最適なメールの配信内容を算出するのに数理最適化が利用されました。

• やりたいことの例：さまざまな事業制約（最大配信数、優先配信期間など）を満たしつつ、ユーザーに最適なメールを配信する
• 変数の例：各ユーザーへの配信メールの種類、配信時間
• 目的関数の例：ユーザーのメール開封率の最大化、コンテンツへの送客数最大化
• 制約条件の例：特定のコンテンツの最大メール配信数、一定期間集中配信したい優先コンテンツ

フリーペーパーの配車スケジュール最適化

　リクルートではフリーペーパーを配るラックを各地域に配置しています。複数のトラックで多くのラックを巡る必要があるので、効率的に巡回するルートを決めることが重要な問題です。従来は人手によってトラックの配車スケジュールを決めていましたが、この問題を解くためのヒューリスティックソルバーを開発しています。

• やりたいこと：ラックへの最適なトラックの割り当てと配送経路を決定する
• 変数の例：トラックのラック割り当て、配送経路
• 目的関数の例：トラックの燃料、合計配送距離、合計配送時間
• 制約条件：訪問可能時間、トラックごとの稼働可能時間、トラックの荷物重量制限など

キッチンの最適調理順レコメンド

　飲食店のキッチン業務の課題の一つとして、料理の提供遅れが存在します。この料理の提供遅れを削減するために、数理最適化問題を用いて、提供遅れを削減できるような調理順をレコメンドする機能を、「Airレジ オーダー キッチンモニター」（飲食店のホール＆キッチン向けの注文／調理管理ができるリクルートのプロダクト）上で提供しています。また、この機能を用いて提供遅れが削減可能であることを実証実験で検証しました。

• やりたいこと：ユーザーに好ましい最適な調理順をiPad上でレコメンドする
• 変数の例：調理をする順番、商品の種類、調理時間
• 目的関数の例：調理遅れ時間の最小化、調理遅れ件数の最小化
• 制約条件の例：同時調理可能数、提供順番の制約、ファーストオーダー優先

TVのCMにおける配置の最適化

　リクルートでは広告媒体の一つとしてTVのCMを利用しています。限られたCM枠のどの場所にどのCM素材を流すかは、広告効果に大きな影響を与える一方でその意思決定は非常に難しい問題です。そこで、数理最適化を用いて「局から提示されたCM枠にどの種類のCMをどの枠に割り当てれば広告効果が最大になるか」を算出し、高い広告効果が得られることを実験で検証しました。

• やりたいこと：限られたTVのCM枠の中で効果を最大化するCM素材の割り当ての決定
• 変数の例：CMをどの枠に放送するのかの割り当て
• 目的関数の例：認知視聴者数の最大化
• 制約条件の例：時間枠に放送できるCMの数、素材に割り当てる最低GRP（Gross Rating Point：のべ視聴率）

リクルートの数理最適化をもっと知りたい方は

　このようにリクルートでは、レコメンドからTVのCMにおける配置の最適化まで幅広い領域で数理最適化を利用しています。このことから数理最適化の応用可能範囲の広さが分かると思います。

　リクルートの数理最適化の取り組みをより知りたい方は、リクルートの西村による数理最適化技術活用の取り組み紹介のスライドもあるので、そちらも参考にしてください。

数理最適化の実問題適用への手順

　ここからは数理最適化をビジネスの課題に適用をする手順を説明します。大きく分けて「1.ビジネス課題の理解」「2.数理モデルの構築」「3.アルゴリズムによる求解」の3段階に分かれます。

1.ビジネス課題の理解

　最初は、「取り組みたいビジネス課題の、何の値を最適化したいか」を考えることです。数理最適化は最適な状態の定義を決定してくれる手法ではないので、ここは人間が考える必要があります。ここで最適化対象としたい値は、それが改善されればビジネス目標が達成されるという値を決定することが望ましいです。

　これはある種ビジネス上のKPI/KGI（重要業績評価指標／重要目標達成指標）を定義するのに近いことです。当然、深いドメイン知識が必要で、この段階で「どんな制約条件の下で最適化したいのか」についても整理する必要があります。

2.数理モデルの構築

　次に、事前に検討した制約条件および最適化したい対象を数式で表すこと（＝数理モデリング）を考えます。どのような形でも定式化できればいいのではなく、基本的には後のアルゴリズムで解きやすいような形式で定式化する必要があるので、一定程度の数理モデリングの知識が必要となります。

3.アルゴリズムによる求解

　続いて、事前に定義した数理モデルを解くアルゴリズムを実装し、最適解を算出します。事前に定義した数理モデルによっては「汎用ソルバー」（数理モデルを与えることで自動的に最適解を算出してくれる汎用《はんよう》的なソルバー）を使うことによって、独自アルゴリズムを新たに実装しなくても最適解を算出可能です。

　性能の良い独自アルゴリズムの実装は高い最適化の専門知識および工数がかかります。そのため、数理モデルの構築の時点で、汎用ソルバーで解きやすい形式に定式化することがビジネス応用上のテクニックの一つといえます。

スーパー人材はいないが……

　このように数理最適化には、ビジネス課題の理解に始まり、アルゴリズムの実装まで幅広い知識が求められます。しかし、これら全てを持つスーパー人材はほとんど存在しません。そこでリクルートではビジネスドメインの知識に強い担当者と数理最適化に詳しいデータサイエンティストの組み合わせのように複数人体制で取り組む案件が多いです。

　そもそも案件化するには、数理最適化を用いることで大きいビジネスインパクトが得られるドメインを見つける必要があるので、ビジネスドメインの知識と数理最適化の双方の知識を一定程度持つようなジェネラリスト的存在も必要とされています。

ビジネス課題への数理最適化の適用の手順と求められる知識

機械学習との違い、使い分け方

　よくある話題として、「機械学習と数理最適化の違いとは何か？」というものがあります。

　お互いに広い意味を持ち、似ている点や併用しているケースもあるので厳密な比較は難しいですが、施策利用の観点でこの2つを比較するには、次のような違いがあるといえます。

• 機械学習
  モデルが未知で、データからそのパターンを学習（そしてそれを用いた予測）するところに関心がある手法（特に「教師あり学習」）
• 数理最適化
  モデルが既知（or定義可能）で、与えられたデータを基に最適な選択を出力するところに関心がある手法

　こういう特徴を踏まえると、モデル化が困難な分野では機械学習を用いて、モデル化が可能な領域では数理最適化を用いるといったすみ分けが可能です。しかし、多くのビジネス課題においては、一部はモデリング可能だが、一部はモデリングできないというケースも多いです。そのため、リクルートで用いる案件では数理最適化の一部に機械学習を用いるような案件が多数存在します。

　例えば前述したレコメンドメールの配信最適化などでは、数理モデルのパラメーターとして、各ユーザーのメールの開封率などが必要です。しかし、その値は直接は取得できないので、機械学習によってその値を予測した上で最適化問題のパラメーターとして利用したりします。

　機械学習と数理最適化はお互いを補完し合うように利用できます。ぜひ「機械学習はばりばり使っているけど数理最適化はそれほど……」という方も、その逆の方も双方の技術について学んでみてはいかがでしょうか。

終わりに

　連載初回の本稿では、数理最適化についての概要およびリクルートでの応用事例についてざっくりとした概要を紹介しました。次回以降は具体的な施策内容を紹介するので、「これじゃ物足りないよ！」という方はぜひ次回以降も読んでもらえるとうれしいです。

参考文献

• 『しっかり学ぶ数理最適化　モデルからアルゴリズムまで（KS情報科学専門書）』（梅谷俊治 著、講談社、2020年10月）
• 『Pythonではじめる数理最適化―ケーススタディでモデリングのスキルを身につけよう』（岩永二郎、石原響太、西村直樹、田中一樹 著、オーム社、2021年9月）

筆者紹介

須藤遼介

株式会社リクルート データエンジニアリングユニット データエンジニアリング部 旅行・飲食・ビューティー・ＳａａＳデータエンジニアリンググループ所属

自動車メーカーで自動運転のソフトウェア開発に携わった後、2019年にリクルートに中途入社。以後、機械学習エンジニアとして、販促やSaaS領域のデータ活用全般を担当。