社内講演会レポ―ト～組合せ最適化による問題解決の実践的なアプローチ～

数理最適化技術は、「データ活用の促進を通じて持続可能な未来をつくる」を企業ミッションとするブレインパッドにとって、必須の注力技術の1つです。 2021年4月15日（木）には、数理最適化技術の研究で大変著名な大阪大学の梅谷俊治先生による社内向け講演会を開催しました。本ブログでは、当社のデータサイエンティストが講演の模様をレポートします！

こんにちは、アナリティクス本部の日吉です。先日、当社では数理最適化に関する社内向け講演会を行いました。当日は、データサイエンティスト以外の社員も多数参加しとても有意義な会となりました。本ブログでは、講演会の内容をレポートします！

講演会の概要

ブレインパッドは、数理最適化を今後の必須技術の1つと位置づけ、社内の技術力向上に努めており、以前発表したプレスリリースの通り、大阪大学数理最適化寄附講座を開設しました。そしてその一環として、寄附講座教授の梅谷俊治先生による社内向け講演会「組合せ最適化による問題解決の実践的なアプローチ」が2021年4月15日（木）に開催されました。

梅谷先生は数理最適化ソルバー開発等の理論研究でもよく知られていますが、研究の原点は数理最適化のビジネスへの適用にあるように見受けられます。実際、学会では多数の産学連携の研究を発表されています。本講演でも、数理最適化を起業の問題解決へ適用させるイメージを伝えるために、多数の産学連携事例をご紹介いただきました。

当日は、社内講演会の第1回目として、数理最適化およびそのビジネス実装の概要がテーマとなりました。

数理最適化の役割

講演は、数理最適化の役割の説明から始まりました。いわゆるビッグデータが整備され、機械学習などのデータ分析技術を用いてビジネスメカニズムのモデル化ができた先に、問題解決の出口、すなわち意思決定や計画策定を出力することになります。数理最適化は、最後に挙げられたタスクである、意思決定や計画策定に用いられる技術です。

数理最適化問題は、制約条件を満たす解の中で目的関数を最小（最大）にする解を求める問題です。講演で梅谷先生は、栄養素が指定量以上含まれるという制約のもとで、野菜の配合をどのようにすればコストを最小にすることができるかという野菜ジュースの配合決定問題を例として、数理最適化問題を説明されました。

数理最適化問題の分類と解法の選択

数理最適化問題と一口に言っても、決定変数、制約条件、目的関数の与え方によってさまざまなクラス（平たく言えば種類）があります。

よく知られているのが線形最適化問題です。線形最適化問題では、決定変数が連続的な値をとり、制約条件や目的関数が決定変数の1次式で表現されます。線形計画問題は連続最適化問題の一種です。連続最適化問題とは決定変数が連続的な値をとる数理最適化問題です。

対して、決定変数が離散的な値をとる数理最適化問題は離散最適化問題、あるいは組合せ最適化問題と呼ばれます。離散最適化問題にもさまざまなクラスがありますが、最短路問題や巡回セールスマン問題は有名でしょう。

数理最適化の研究は長く、問題ごとに効率のよいアルゴリズム（解法）が開発・整備されてきました。一方、混合整数計画ソルバーのように、汎用的なアルゴリズムが実装されたソフトウェアが開発されています。このように、解法には専用解法と汎用解法があります。専用解法は、問題の特徴を利用できるので高性能であることが期待されます。一方汎用解法は、定式化の記述法さえ憶えてしまえばさまざまな問題に対処することができます。

また、問題によってはそもそも最適解を求めることが難しいことがあります。このようなとき、制約条件を満たした解（実行可能解）で、目的関数の値が「よい」と期待されるような解を一定時間内に求めることでよしとせざるを得ないことも多いです。

以上のようなことを考慮にいれながら最適化モデルを構築し、解法を選択することになります。

問題解決の出口を見つけるために

ここまでの説明にある通り、まず現実問題を定式化することにより最適化モデルを構築し、ついでアルゴリズムを開発するということは、大学の授業でも学習します。しかしながら、現実問題を扱うときには、そもそも問題の「正体」が不明であることが多いです。当社の経験でも、最初から妥当な最適化モデルが得られていることはほぼありません。要件が曖昧であるということは、通常のソフトウェア開発と共通するところでしょう。

梅谷先生は、クライアントからのフィードバックを受け、最適化モデルに修正を加えるというループを効率よく回していくことが重要であるということを強調されていました。筆者はアジャイル開発という言葉を連想しました。