はじめに

データサイエンティストの高橋です。

エムシーデジタルでは、現実世界の課題を数理最適化問題として定式化し、それを汎用のソルバーを用いて解くことをよく行なっています。

数理最適化問題を定式化する際、余分な要素を削ぎ落とし、問題をより単純な形で表現することは、ソルバーの計算時間の短縮に繋がるため重要です。

今回はそのような、ソルバーが解きやすい定式化を行うための工夫について、筆者がプロジェクトで遭遇した問題を題材に、典型的なものから、組合せ論の定理を使った発展的なものまでいくつか紹介したいと思います。

なお本記事は、数理最適化の定義や基本的な用語を理解していることを前提とします。数理最適化の基本的な知識については、当テックブログの別記事 や、入門的な書籍 ¹ を参照してください。

導入

現実世界の課題を最適化問題として解決する場合、大きく以下の三つのアプローチが考えられます。

• 問題を数理最適化問題として定式化し、Gurobi や SCIP などの汎用ソルバーを用いて解く
• 擬似焼きなまし法やビームサーチなどを用いたメタヒューリスティクスアルゴリズムを作成する
• 問題を何かしらの有名問題（巡回セールスマン問題など）に帰着できる場合、その問題の専用ソルバーを用いて解く

本記事で扱うのは、一つ目の汎用ソルバーを用いるアプローチです。²

汎用ソルバーを使って最適化を行う際、高速な実行ができると以下のような点で嬉しいです。

• 最適化プログラムは実装が複雑化しやすい上、ソルバーの内部がブラックボックスであることから保守やデバッグが難しく ³、実行時間を短縮しフィードバックを高速に受けられるようにすることで開発の負担を減らせる
• Gurobi などの商用のソルバーを従量課金で使用する場合、直接のコスト削減に繋がる
• 汎用ソルバーは、その汎用性のために問題固有の特徴を柔軟に使って高速化することが難しいため、他のアプローチと比べ実行時間が大きく増えることがある

プログラムの実行時間を短くするためには、一般に強力なマシンを使用したり並列・分散計算を行うこと（これらはソルバーのオプションとして調節できることも多いです）が効果的です。加えて数理最適化の文脈では、定式化を工夫しソルバーが解きやすい形で問題を表現することが重要になってきます。

実課題を題材にした例

ここでは、筆者がプロジェクトで遭遇した問題を題材に、ソルバーが解きやすい定式化を行うための工夫をいくつか紹介します。

なお以下で挙げる問題設定は、元の問題を大きく簡略化し、説明に必要な部分だけを抽出しています。そのため、ここに挙げている定式化のみで問題を考えると、不自然であったり遠回りにも思える工夫も含まれていることをご容赦ください。

問題設定

生産計画を念頭にした以下の最適化問題を考えます。

$N$ 種類の製品と $M$ 個の生産工場がある。種類 $i$ の製品を一つ生産すると利益 $c_i$ が得られる。製品はそれぞれ生産可能な工場が決まっており、種類 $i$ の製品は集合 $S_i \subseteq \{1, \ldots, M\}$ に含まれる工場でのみ生産できる。また各工場はその最大生産量が決まっており、工場 $i$ では最大 $d_i$ 個の製品を生産できる。以上の条件下で、各製品の生産量を適切に決定することで、得られる利益を最大化したい。

この問題を、ナイーブに混合整数計画問題（MIP）として定式化すると、以下のようになると思います。

$$ \begin{align} \text{maximize} \quad & \sum_{i=1}^N \sum_{j=1}^M c_i x_{ij} \notag \\\
\text{subject to} \quad & \sum_{i=1}^N x_{ij} \le d_j \quad (j = 1, \dots, M), \notag \\\
& x_{ij} \geq 0 \quad \text{for all } i, j, \notag \\\
& x_{ij} = 0 \quad \text{for all } i, j \text{ such that } j \notin S_i. \notag \end{align} $$

ここで $x_{ij}$ は、製品 $i$ の工場 $j$ での生産量を表す整数変数とします。制約の一行目は、各工場での生産量がその工場の最大生産量を超えないこと、また制約の三行目は、種類 $i$ の製品は集合 $S_i$ に含まれる工場でのみ生産できることを表現しています。

また、上述の問題定義には含まれていませんが、ユーザーへのヒアリングや実データの分析を通して、以下の観察が得られていることを仮定します。

• 製品の生産量は多く、一種類あたり $1000$ から $10000$ のオーダーである
• 製品はいくつかのカテゴリに分類でき、同じカテゴリに属する製品は得られる利益や生産可能な工場が等しい
• 工場の数は少なく、$1$ から $5$ 箇所ほどである

以降では、これらの観察を活かし、先述のナイーブな定式化に手を加えていくことで、よりソルバーが解きやすい形に問題を変形できることを見ていきます。

生産量を連続変数にする

ナイーブな定式化では、製品の工場あたりの生産量 $x_{ij}$ を整数変数にしていました。しかし今回のような大量生産のケースでは、製品の生産量が僅かに変化しても大きな影響はないと考えられます。

そこで $x_{ij}$ を整数ではなく連続変数として取ることを考えます。一般に（混合整数計画）ソルバーは整数変数より連続変数のほうが扱いやすいため、これにより実行時間の短縮を期待できます。

後にちゃんと整数値の生産量がほしくなった場合は、最適化で得られた連続量を適当な方向に丸めることにします。このとき、できるだけ制約に違反しない方向（今回は負の方向）に丸めると、より安全かもしれません。⁴

カテゴリごとに変数をまとめる

今回の例では、製品にカテゴリというものが存在しており、同一カテゴリの製品では、最適化を考える上での特徴が等しいものとしました。

そこで、同一カテゴリの製品をまとめて一つの仮想的な製品とみなし、それらを改めて製品集合とすることで問題を再定義する、ということを考えます。これにより、例えば製品の総数は $1000$ だがカテゴリは $100$ しか存在しない、というような場合、問題の $N$ のサイズを $\frac{1}{10}$ にすることができます。

最適化の後でカテゴリ内の製品の生産量を決めたくなった場合は、最適化で決定したカテゴリ全体での生産量を、各製品の需要などに比例して分配するようにします。

ホールの定理を使い、工場ごとの生産量の決定を不要にする

ここまでの定式化では、各製品の工場ごとの生産量 $x_{ij}$ を変数に取っていました。しかし本来目的関数の考慮で必要なのは、あくまで各製品の「工場全体」での生産量 $x_i := \sum_{i=1}^M x_{ij}$ です。

変数として $x_{ij}$ を取っていたのは、各工場の最大生産量の制約を考慮するには、工場ごとの具体的な生産量を値として持っておく必要があると思われたからです。

もし $x_i$ に対して何らかの制約を設けることで、工場の最大生産量に違反しない $x_{ij}$ の存在を（$x_{ij}$ を陽に持つことなく）保証できれば、$N \times M$ 個ある $x_{ij}$ の代わりに $N$ 個の $x_i$ を変数に取ることで、変数の数を削減できます。

これを可能にする定理として ホールの定理 が存在します。

詳細は省略しますが、ホールの定理を使うことで、工場の最大生産量に違反しない $x_{ij}$ が（全ての $(i, j)$ について）存在するためには、$x_i$ が全体として以下の条件を満たしていることが必要十分であることが証明できます。

任意の工場の部分集合 $F \subseteq \{1, \ldots, M\}$ について、$S_i$ が $F$ に内包されている、つまり $F$ に含まれない工場では生産できないような製品の合計生産量を $X$ としたとき、$X \leq \sum_{i \in F} d_i$ である。

$X$ 個の製品は $F$ に含まれる工場のどれかで生産するしかないので、その必要性は明らかです。ホールの定理により、これが十分条件でもあることが言えます。

サイズ $M$ の集合の部分集合は $2^M$ 個存在するため、この条件を表現するためには $2^M$ 個の不等式制約が必要です。もし $M$ が大きい場合、この $2^M$ は莫大な大きさになってしまいますが、今回のケースでは $M$ が十分に小さいことを仮定しており、最大の $M = 5$ の場合でも $2^5 = 32$ 個の制約で表現できるため、十分に実現可能です。

最適化で決定した生産量を元に実際の生産を行うとなった場合、$x_i$ から、工場の最大生産量に違反しない $x_{ij}$ を実際に求めたくなるかもしれません。その場合、再び詳細は省略しますが、最大フロー問題 を解くアルゴリズムを使うことで、そのような $x_{ij}$ を高速に計算できることが知られています。

注意点

ここまでの議論では、簡単のための仮定として、変数や制約の数を減らし、問題サイズを小さくすることが必ず高速化に繋がるかのように考えていました。しかし、ソルバーのアルゴリズムは複雑であり、問題のサイズが小さくなっていたり、あるいは人が見てシンプルだからといって、必ずしもソルバーが高速に解けるとは限りません。机上で定式化の良し悪しを判断するのではなく、実際にソルバーを実行して時間を計測することが重要です。

また、一般的な高速化の例に漏れず、必要に迫られていない段階での高速化は行わないほうがよいです。例として、本記事の生産計画の例では「工場はあまり多くない」などの前提が成り立つものとして、定式化の改善を行っていました。これらの前提が後に要件の変更で覆った場合、プログラムの修正が必要となり、汎用ソルバーを使うことの利点である柔軟性が損なわれてしまいます。

おわりに

本記事では、ソルバーが解きやすい定式化を行うための工夫について、筆者がプロジェクトで遭遇した問題を題材にいくつか紹介しました。

本記事で取り上げた工夫は、多少強引に抽象化すると「最適化に大きく影響しない部分を近似や捨象し、本質的な情報のみをソルバーに渡すようにする」と言えるかもしれません。ただしそのような工夫は、問題に対して本来は不要な前提を置いてしまい、プログラムの保守性や拡張性を損なうことがあるので注意が必要です。

エムシーデジタルでは、数理最適化関連のイベントや勉強会なども定期的に実施しています。 もしエムシーデジタルで働くことに興味を持っていただいた方がいらっしゃいましたら、カジュアル面談も受け付けておりますので、以下よりご応募ください！
採用情報や面談申込みはこちらから

脚注