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

本記事は、当社オウンドメディア「Doors」に移転しました。

約5秒後に自動的にリダイレクトします。

ブレインパッドの社員が「数理最適化技術」に関して連載するこの企画。
記念すべき初回は、当社のCDTO（Chief Data Technology Officer）が、数理最適化に関する書籍の輪読会を通じて得たTipsをご紹介します！

こんにちは。CDTO (Chief Data Technology Officer) の太田です。この記事は【連載】ブレインパッドの数理最適化ブログ（目次）の初回の記事です。

今回、「大阪大学数理最適化寄附講座」の開設に関わらせていただくことになったきっかけは、 TensorFlow User Group の有志の方々とともに主催している Optimization Night というコミュニティイベントでした。現在、そのコミュニティのメンバー数名と週次の輪読会を開催しており、H. Paul Williams, Model Building in Mathematical Programming という書籍を読みすすめています。

この書籍は数理最適化のアルゴリズムではなく、定式化の部分にフォーカスを当てているのが特徴です。線形計画法の基本的な定式化方法から始まり、整数計画法の色々なテクニックが紹介されています。また、後半はすべて演習問題になっていますが、適度に複雑でやりごたえのある問題が揃っています。

理論面の記述が少ないため、本書だけで網羅的に理解するのは難しいですが、私のように数理最適化自身の研究ではなく実際に利用したいと考えている方にとってはとても良い本だと思います。

そこで今回は、輪読会の中で個人的に学んだこと・面白いなと思ったことを、定式化の Tips としてまとめようと思います。個人的な解釈も多分に含まれていますし、網羅的でもありませんが、このあたりをまとめた記事は少ないと思うので、定式化の際に少しでも参考にしてもらえればと思います。

輪読会で学んだ面白かったこと、あるいは定式化の Tips
0. 定式化が重要だと思う理由
まとめ
- 参考文献

輪読会で学んだ面白かったこと、あるいは定式化の Tips

0. 定式化が重要だと思う理由

輪読会で学んだことを紹介する前に、前提知識を揃えるという意味で、数理最適化の簡単な例を紹介したいと思います。

アイス生産問題

アイス屋さんが、エスプレッソアイス、ラズベリーアイス、2種類のアイスの生産を計画しています。しかし、材料の牛乳は 8000 cc、作業時間は述べ 360 分という制限があり、好きな分量だけ作れるわけではありません。それぞれのアイスに使う牛乳とかかる手間がこのようになっているとき、儲けを最大にする増産計画はどの様になるでしょうか?

牛乳作業時間儲け

エスプレッソアイス 100cc 7分 250円

ラズベリーアイス 150cc 5分 300円

	牛乳	作業時間	儲け
エスプレッソアイス	100cc	7分	250円
ラズベリーアイス	150cc	5分	300円

引用: 「入門オペレーションズ・リサーチ」（東海大学出版会）

数理最適化問題とは、「与えられた制約条件の下で目的関数の値を最小 (もしくは最大) にする解を求める問題」のことです。決めたい変数（決定変数）、最小化（もしくは最大化）したい関数（目的関数）と制約で記述されます。この例題の場合、それぞれのアイスの生産量を $x _ i$ ( $i$ は $e$ (エスプレッソ)もしくは $r$ (ラズベリー))、それぞれの作業時間を $y _ i$ とすると、

目的関数: 儲け（最大化）
$\displaystyle \mathrm{Maximize}\ 250x _ {e} + 300x _ {r}$
決定変数: それぞれのアイスの生産量
$\displaystyle x _ {e},\ x _{r}$
制約: 材料の牛乳は 8000 cc, 作業時間は述べ 360 分
$\begin{aligned} 100x _ {e} + 150x _ {r} \leq 8000 \\ 7 x _ {e} + 5 x _ {r} \leq 360 \end{aligned}$

となります。ここでちょっと言葉を整理しておきます。

決定変数がすべて連続変数で、目的関数と制約式がすべて決定変数について線形な式の場合、線形計画問題（LP; Linear Programming）と呼ばれます。
決定変数のなかに連続変数でないもの（離散変数）が含まれる場合は、混合整数線形計画問題もしくは単に混合整数計画問題（MIP; Mixed Integer Programming）と呼ばれます。
上記の様に、解きたい課題を目的関数、決定変数、制約に落とし込むことを定式化と呼びます。
目的関数、決定変数、制約を与えれば、最適解を導出してくれる汎用的なプログラムが公開されていて、この記事では汎用ソルバーと呼んでいます。数理最適化問題を解くには、汎用ソルバーを使うこともできるし、独自にアルゴリズムを構築して解くこともできます。

では、実際にフリーの汎用ソルバーを使って上述の問題を実際に解いてみましょう。使うのは PuLP というソフトです。 PuLP は

$ pip install pulp

でインストールできます。

import pulp


problem = pulp.LpProblem('ice', pulp.LpMaximize)

# 決定変数を定義
x_e = pulp.LpVariable('x_e', lowBound=0) 
x_r = pulp.LpVariable('x_r', lowBound=0) 

# 目的関数を設定
problem += 250*x_e + 300*x_r

# 制約を設定
problem += 100*x_e + 150* x_r <= 8000
problem += 7*x_e + 5* x_r <= 360

# 最適化
problem.solve()

# 結果の表示
print(x_e.value(), x_r.value())

以上は簡単な例ですが、定式化さえできれば汎用ソルバーを使うことで最適化問題を解くことができる、というのはわかっていただけたかと思います。ただし、規模や問題によっては一筋縄ではいきません。そのため、実務ではいかに定式化するかがとても重要になります。

輪読会を始めるときに、「定式化について詳しい書籍がうれしい」という意見があがり、今の書籍を選択しました。

定式化方法

1. 比率を目的関数にする

実応用を考えると、何らかの比率を最適化したいという場面が時々あります。例えば、費用対効果はかけたコストと得られる効果の比率のことですね。

本書では、線形計画法（LP; Linear Programming）と混合整数計画法（MIP; Mixed Integer Programming）を取り扱っており、目的関数も制約式も、決定変数について線形な式である必要があります。比率は当然線形ではありませんが、簡単な変数変換により線形な式の最適化問題に変換できます。

具体例を見てみましょう。目的関数が

$\displaystyle \mathrm{Maximize}\ \frac{\sum_{i} a_{i} x_{i}}{\sum_{i}b_{i} x_{i} }$

制約式が

$\displaystyle \sum_{i}d_{i}x_{i} \leq e$

で与えられるような問題を考えます。この問題は（分母の符号が変わったりゼロになったりしない前提で）以下の手順で線形な式に変換できます。

新たな変数 $t=\frac{1}{\sum _ {i}b _ {i}x _ {i}}$ , $w _ {i} = x _ {i}t$ を導入して目的関数を書き換える
$\displaystyle \frac{\sum _ {i} a _ {i} x _ {i}}{\sum _ {i}b _ {i} x _ {i} } = \sum _ {i}a _ {i}x _ {i}t = \sum _ {i} a _ {i}w _ {i}$
等式 $t=\frac{1}{\sum _ {i}b _ {i}x _ {i}}$ を $w$ で書き換えて、制約として追加する
$\begin{aligned} t =\frac{1}{\sum _ {i}b _ {i}x _ {i}} \Leftrightarrow \sum _ {i}b _ {i}x _ {i}t = 1 \\ \Leftrightarrow \sum _ {i}b _ {i}w _ {i} = 1 \end{aligned}$
$w _ {i} = x _ {i}t$ を使って制約式 $w _ {i}$ と $t$ で書き換える
$\displaystyle \sum _ {i}d _ {i}x _ {i} \leq e \Leftrightarrow \sum _ {i}d _ {i}w _ {i} \leq et$

このあたりの話は、書籍の Chapter 3 で取り上げられています。個人的に面白いなぁと思ったのは、最後の制約の部分です。 $x_{i} = \frac{w _ {i}}{t}$ なので、一見分数が出てきてしまいそうですが、 $t$ には添字がないので右辺に移項できて、結局線形な制約に置き換わります。

2. 平準化をしたい場合は、最大値の最小化（minimax）を考える

最適化したい項目が複数あるときに、平準化をしつつ最適化したい、という要望もいろいろなところで出てきます。単純に定式化しようとすると、各項目の値の差分の合計を小さくしつつ、最適化して...と考えてしまいそう（少なくとも私ははじめそう思いました）ですが、最大値の最小化もしくは最小値の最大化を考えると、自動的に平準化された解が得られます。

Optimization Night #2 で梅谷先生に紹介いただいた電子ジャーナル購読計画でも、購読雑誌の分野による偏りのない現実的な解を得るために、最小充足率の最大化を利用しています。

最大値の最小化は、割と素直に定式化できます。例えば、

$\displaystyle \mathrm{Minimize}\left(\max \sum _ {j}a _ {ij}x _ {j}\right)$

を考えたい場合は、新たな変数 $z$ を使って、以下のように書けます。

$\begin{aligned} \mathrm{Minimize}&\ z \\\\ \mathrm{s.t.}& \sum _ {j}a _ {ij}x _ {j} \leq z,\quad \mathrm{for}\ ^{\forall}i. \end{aligned}$

制約式（s.t 以降の式）によって、 $z$ は $\sum _ {j}a _ {ij}x _ {j}$ のなかで最大のものよりも大きい値となりますが、目的関数で $z$ を最小化しているので、結局 $\sum _ {j}a _ {ij}x _ {j}$ の最大値と等しくなります。

minimax型の目的関数を用いると求解時間が長くなったり暫定解の質が悪くなったりすることもあるらしいので、もしかすると使い所を選ぶのかもしれませんが、こういった条件を線形な式で表現できるというのはとても面白いなと思いました。

3. 目的関数をうまく使って制約を表現する

制約式で表現しづらい制約がある場合に、目的関数の性質を使うとうまく表現できることがあります。前述のminimax型の目的関数も、目的関数が最小化されるという性質をうまく使ったものでした。

もう一つ、本書で取り上げられていて面白いなと思ったのは、演習問題にあった発電機の起動・停止問題で、以下のような設定です。

発電機を複数台所有していて、需要を満たすように電力を提供しなければいけない
需要量は時間帯ごとに変わる
発電機は、発電量に比例したコストに加え、起動時にもコスト（起動コスト）がかかる
需要を満たしつつ、コストを最小化するには、各時間帯で何台の発電機を動かしたらよいか

定式化の方法はいくつかあると思いますが、私は $n _ {t}$ を時間帯 $t$ に動いている発電機の台数として定式化しました（他には 0-1変数 $x _ {ti}$ を使って、時間帯 $t$ に発電機 $i$ が動いているかを表す方法もあると思います）。

では、起動コストをどうやって表現したら良いでしょう？すぐに思いつきそうなのは、 $a _ {t}$ を時間帯 $t$ の起動台数（まさにその時間帯に起動した台数）として

$\displaystyle a _ {t} = n _ {t} - n _ {t-1}$

という制約を入れることです。

ただ、これはうまくいきません。需要に応じて発電機は停止することもあるので、場合によっては、左辺が負になりえます。一方、右辺の $a _ {t}$ は新規の起動台数、増加分を表しているので、常に $a_{t} \geq 0$ のはずです。このように、「だいたいそうだけど、時々違う」ような制約はいろいろなところに出てきます。

では増加分だけを数えるにはどうしたら良いでしょうか？実はとても簡単で、今やりたいのは正確には

$\displaystyle a_{t} = \max(0, n_{t} - n_{t-1})$

でした。これは、minimax型の目的関数と同様で

$\begin{aligned} n_{t} - n_{t-1} &\leq a_{t} \\ 0 &\leq a_{t} \end{aligned}$

という制約に置き換えます。もちろん、この制約だけでは、 $a _ t$ はいくらでも大きくできてしまいますが、今回の目的がコストの最小化なので、目的関数に $\sum _ {t} Ca _ {t}$ ( $C$ は1台あたりの起動コスト) のような項があるはずです。この項により、最適解では $a _ {t}$ は可能な限り小さくなり、結果として $a _ {t} = \max(0, n _ {t} - n _ {t-1})$ となります。

こういった目的関数の性質を利用して、制約をうまく表現するテクニックは、知っている人は当然知っているものだと思いますし、私自身も過去に使ったことがあるですが、当時はあまり意識していなかったということもあり、あらためて面白いなぁと思った次第です。

4. indicator variable を使って、複雑な論理式を記述する

混合整数計画法（MIP）と比較して線形計画法（LP）は解きやすいですが、実応用では整数変数を使いたい場合が多いです。整数変数は、主に以下の3パターンで使われます。

indivisible (discrete) quantities 自動車の台数や人数の用に、そもそも整数の値が出てくるような場合
decision variables 何らかの施策をするかしないか決めるような場合
indicator variables if-then のような条件式を表現する場合

indivisible quantities や decision variables は、イメージしやすいですが、実は indicator variables がかなり重要で、これを使いこなすと複雑な論理式を記述できるようになります。

indicator variables の例として、 $x \geq 0$ を連続変数、 $\delta$ を 0-1 変数とした時、 $M$ を $x$ の上限として、

$\displaystyle x > 0 \to \delta = 1$

という論理式を記述したいとします。この式は、 $x$ の上限を $M$ とすると、

$\displaystyle x - M\delta \leq 0$

と書けます。実際、

のとき
- $\delta = 1$ だと制約が満たされない（ $\delta = 1$ である必要がある)
- $\delta = 1$ であれば、 $x \leq M$ が $x$ より、制約は満たされる
のとき
- $\delta$ の値に関わらず制約は満たされるため、 $\delta$ は自由に選べる

となります。この論理式の書き換えは非常に混乱しやすいので、以下にまとめてみました（多分あっているはず...）。前提として、 $m,\ M$ はそれぞれ $x$ の下限値と上限値です。

	if-then	formulation
1	$x > 0 \to \delta = 1$	$x - M\delta \leq 0$
2	$x \geq 0 \to \delta = 1$	$x + \epsilon - M\delta \leq 0$
3	$x\ \lt \ 0 \to \delta = 1$	$x - m\delta \geq 0$
4	$x \leq 0 \to \delta = 1$	$x + \epsilon - m\delta \geq 0$
5	$\delta = 1 \to x \geq 0$	$x - m(1 - \delta) \geq 0$
6	$\delta = 1 \to x > 0$	$x + \epsilon - m(1 - \delta) \geq 0$
7	$\delta = 1 \to x \leq 0$	$x - M(\delta - 1) \leq 0$
8	$\delta = 1 \to x\ \lt \ 0$	$x + \epsilon - M(\delta - 1) \geq 0$

ここで $\epsilon$ は十分小さい数で、制約式では等号なしの不等号を使えないために必要になります。また、上の表は、 $x$ の代わりに $\sum_{i}a _ {i}x _ {i}$ のような数式であっても成り立ちます。

さらに、 indicator varibales 同士の条件を記述することで複雑な条件を記述できます。例えば、 $R_1, R_2$ という制約があった場合に $R_1\ \mathrm{or}\ R_2$ という制約を表現するには、上の表を参照して、

$\begin{aligned} \delta_1 = 1 \to R_1 \\ \delta_2 = 1 \to R_2 \\ \end{aligned}$

となるような indicator variable $\delta_1,\ \delta_2$ を用意して、

$\displaystyle \delta_1 + \delta_2 \geq 1$

という制約を追加します。 $\delta_1 + \delta_2 \geq 1$ であれば $\delta_1 = 1$ もしくは $\delta_2 = 1$ なので、 $R_1\ \mathrm{or}\ R_2$ となるわけです。indicator variable をチェインのようにつなげることで、もっと複雑な条件も記述できます。例えば、

$\displaystyle R_1\ \mathrm{or}\ R_2\ \to\ R_3$

を表現するには、

$\begin{aligned} R_1 &\to \delta_1 = 1 \\ R_2 &\to \delta_2 = 1 \\ \delta_3 = 1 &\to R_3 \end{aligned}$

となるような indicator variable $\delta_1,\ \delta_2,\ \delta_3$ を用意して、

$\displaystyle \delta_1 + \delta_2 \leq \delta_3$

とすればよいでしょう。論理式の indicator variable による表現をまとめると、以下になります。

論理式	表現
$X _ 1 \vee X _ 2$	$\delta _ 1 + \delta _ 2 \geq 1$
$X _ 1 \cdot X _ 2$	$\delta _ 1 = 1,\ \delta _ 2 = 1$
$\sim X _ 1$	$\delta _ 1 = 0$
$X _ 1 \to X _ 2$	$\delta _ 1 - \delta _ 2 \leq 0$
$X _ 1 \leftrightarrow X _ 2$	$\delta _ 1 - \delta _ 2 = 0$

ここで、それぞれの記号の意味は、下記のとおりです。

記号	意味
$\vee$	or (A or B or both)
$\cdot$	and
$\sim$	not
$\to$	implies (if ... then)
$\leftrightarrow$	if and only if

5. 区分線形近似で非線形関数を表現する

目的関数や制約式が、線形だったり比率の形になっていなかったとしても、区分線形近似をつかってMIPで定式化できます。具体的には、下図のように曲線を折れ線で近似してあげればよい、ということです。

定式化のポイントは、線分 $\boldsymbol{AB}$ 上の点は、 $\lambda \in [0, 1$ ] を使って、 $\lambda \boldsymbol{A} + (1 - \lambda)\boldsymbol{B}$ とかけることです。例えば $x ^ 2$ を区分線形近似するには、以下のようにします。

まず、近似する範囲と分割点を設定します。下図の場合は、 $(0, 0)$ , $(1, 1)$ , $(2, 4)$ , $(3, 9)$ です。
$x ^ 2$ の近似値を表す変数 $y$ を導入して、以下の制約を課します

$\begin{aligned} x &= 0\lambda_A + 1\lambda_B + 2\lambda_C + 3\lambda_D, \\ y &= 0\lambda_A + 1\lambda_B + 4\lambda_C + 9\lambda_D, \\ & \lambda_A + \lambda_B + \lambda_C + \lambda_D = 1. \end{aligned}$
ただし、高々2つの隣り合う $\lambda_{i}$ だけが非ゼロ

最後の「高々2つの隣り合う...」というのが厄介ですが、 $\delta_{\alpha}$ を、線分 $\alpha$ 上であることを示す 0 - 1 変数とすれば、

$\begin{aligned} \lambda_A - \delta_{AB} &\leq 0, \quad (\lambda_A は線分 \boldsymbol{AB} 上の時のみ非ゼロ)\\ \lambda_B - \delta_{AB} - \delta_{BC} &\leq 0, \quad (\lambda_B は線分 \boldsymbol{AB} もしくは \boldsymbol{BC} 上の時のみ非ゼロ)\\ \lambda_C - \delta_{BC} - \delta_{CD} &\leq 0, \quad (\lambda_C は線分 \boldsymbol{BC} もしくは \boldsymbol{CD} 上の時のみ非ゼロ)\\ \lambda_D - \delta_{CD} &\leq 0, \quad (\lambda_D は線分 \boldsymbol{CD} 上の時のみ非ゼロ)\\ \delta_{AB} + \delta_{BC} + \delta_{CD} &= 0. \quad (どれか一つの線分上にある) \end{aligned}$

と書けます。「高々2つの隣り合う...」という制約に従う変数の組は SOS2 (Special Ordered Sets of type 2)と呼ばれています。上記のように愚直に制約を書き下すのではなく、SOS2であることをソルバーに明示的に示してあげる（ソルバー毎にそういった機能が実装されています）ほうが計算効率が上がるそうです。

なお、上記の区分線形近似は、単変数もしくは分離可能な関数（単変数関数の和となっているような関数）に対しては有効ですが、例えば $xy$ のように2つ以上の変数が絡み合っているような関数は、補完の方法が自明でなかったり、変数の数が膨大になってしまうという問題があります。輪読会に参加する前までは「区分線形近似最強だろう」と思っていたのですが、それはちょっとあまかったようです。

6. 感度分析を利用する

書籍では shadow price（潜在価格）や reduced cost（被約費用）といった、感度分析に関係するような話題が随所で取り上げられています。私は今までこのあたりをちゃんと勉強したことがなかったので、とても勉強になりました。

ここで感度分析とは「問題が少し変わった時に、どういう挙動を示すか」を分析することを言います。例えば、需要をもとに配送計画を立てる場合に、需要が少し違ったら、最適解にどういう影響が出るのか、を分析することです。 shadow price や reduced cost は大まかに言って

shadow price（潜在価格）
- 制約を少し緩めた場合に、最適解の値はどれくらい良くなるか
reduced cost（被約費用）
- 変数を最適解から少し増やした場合に、解の値はどれくらい増加するか（悪化するか）

という意味を持ちます。はじめは、単に微分すればよいだけでは？と思ったのですが、制約式は不等式なので、単純に微分することはできません。手計算するのであれば、最適値のまわりで有効な制約（等号が成立している制約）だけに絞って変数を動かす必要がありそうです。

これらの値は双対問題と関係しており、汎用ソルバーが求解時に自動的に求めてくれます。 pulp では、 shadow price は LpConstraint.pi、reduced cost は LpVariable.dj で取り出せるようです。ドキュメントを探しても見つからなかったのですが、公式のサンプルコードで利用されています（ファイル名が気になります）。

また、下記のリンクにあるように、MIPの場合の解釈には注意が必要そうです。 https://support.gurobi.com/hc/en-us/articles/360034305272-How-do-I-retrieve-the-Pi-values-for-a-MIP-problem-support.gurobi.com

定式化時に意識すること

7. 多重和による多目的最適化には慎重に

現実的な問題では、1つの値を最適化したいわけではなく、複数の観点で最も良いもの、バランスの取れたものを選びたい、という要望がよくあります。例えば、売上を上げつつコストを減らしたいとか、CVRとCTRを同時に上げたいといった状況で、いわゆる多目的最適化と呼ばれるものです。

最もシンプルですぐに思いつく方法は、それぞれ最適化したい指標に適当な重みをつけて足し合わせたものを目的関数とすることだと思いますが、輪読会では「重みの調整大変では？」という話になりました。実際項目が多い場合は大変だと思います。

その場で出た意見として「経験上は3〜4個程度までならうまく調整できることが多い。それ以上だと厳しかったりする」というのがあり、目安として良さそうだと思いました。

ちなみに、書籍では多目的最適化と関連してゴールプログラミングについても結構触れられていました。ゴールプログラミングは、トレードオフ関係のある制約がたくさんあり、全てを満たすのは困難な状況において、可能な限り制約を満たしたいという話で、後に紹介するように、制約を「ソフトな制約」と捉えて制約の違反量を最小化する問題に落とし込む方法です。

8. パターンを列挙できないか考える

順列を決めるような問題のときに、実現可能なパターンを予め列挙してしまって、どのパターンを選ぶか、という問題に帰着させると解きやすくなることがあります。知っている人はみんな知っているんだろうと思いますし、確かに色々な事例を調べていると、パターンを列挙する解法はいろいろなところで使われています。

例えば最近読んだ文献「ローリー車による液化天然ガス(LNG)販売事業のロジスティクス最適化の実現」では、液化天然ガスの配送パターンを予め列挙しておき、どのパターンを選択するかという問題に帰着させることで、計算量を削減しています。

書籍の Chapter 8 で触れられていますが、いわゆる組合せ最適化問題には、順列を求めるタイプの問題と割当てを求めるタイプの問題があり、後者のほうが解きやすいことが多いようです。

パターンの種類が多すぎて列挙できない場合には、有用そうなパターンの候補を徐々に増やしていく、という方法もあります。これは列生成法と呼ばれるテクニックで、書籍では Chapter 9 で取り上げています。

私は列生成法に詳しいわけではないですが、興味のある方にはオペレーションズ・リサーチのはじめての列生成法がとてもわかりやすいので、とてもとてもおすすめです。

9. ネットワーク最適化問題に汎用ソルバーで取り組む

"As such programs are often highly efficient and well-designed, their speeds outweigh the algorithmic efficiency of less well-designed but more specialized programs." (訳: そのようなプログラム（汎用ソルバー）は高効率で良く設計が洗練されていることが多いため、その計算速度は、設計の洗練されていない、より問題に特化したプログラムのアルゴリズムの効率を凌駕する)

読んでいて「ぐふっ」となったので挙げておきました。数理最適化問題を効率的に解くには、問題の構造をうまく利用する必要があります。例えばネットワーク構造があるような問題は、その構造に特化したアルゴリズムを使うことで、汎用的な方法と比べて非常に高速に解ける可能性があります。

が、しかし、汎用ソルバーも結構早いということを忘れてはいけません。自分が独自に実装した、問題に特化したプログラムは、日々改善され続けている汎用ソルバーに勝てるでしょうか？

ちなみにネットワーク問題は、流量の保存（各ノードに入ってくる量と出ていく量が等しい）を制約とすることで、素直に LP もしくは MIP として定式化できます。その際、一見MIPに見えるが実はLPとして定式化できる（連続変数であっても、最適解では自動的に整数値になるため、MIPとする必要がない）ようなことが多くあるため、求解が高速であるという事情もあるようです。

要件定義・デバッグで意識すること

10. まずは汎用ソルバーを使って解く

これは本書でも少し触れられていますし、 Optimization Night #2 でも取り上げられています。

数理最適化問題を解くには、ざっくりと以下の2種類の方法があります。

汎用ソルバーを使う
- 定式化までは自分で行うが、最適解を求めるのは汎用のソフトを利用する。
独自に最適化のアルゴルズムを組む
- 定式化したあとで、最適解を探索するコードも独自に実装する。

汎用ソルバーを使う場合は、問題に特化したアルゴリズムと比べて求解に時間がかかったり、問題の規模が大きくなると突如現実的な時間で解が求まらなくなることがある一方で、独自にアルゴリズムを組むと、コードのメンテナンスや仕様の変更への対応が難しいという問題があります。

数理最適化に限らず、プロジェクト初期に仕様が確定していることはほとんどありません。計画段階ではルールとして定めていたが、実際には少し破っても多めに見ているものがあったり、ルールには載っていないが暗黙的な制約や考慮しないといけない点があったりするのが通常なので、予めすべての制約を過不足なく洗い出しておく、というのはほぼ不可能です。そのため、実際のプロジェクトでは、要件の抽出と定式化のループを繰り返すことが多そうです。

さて、要望が変わる毎に継ぎ接ぎされた独自アルゴリズムのコードをメンテナンスしたいでしょうか？私はできれば避けたいです。もちろんプロジェクトによって状況はさまざまですし、明らかに汎用ソルバーが向いていない問題も多いので、一概には言えませんが、特にプロジェクトの初期においては、速度が多少気になったとしても、まずは汎用ソルバーの利用を検討する、という方針はよさそうです。

11. 過去データを代入する

当然といえば当然のことですが、輪読会の雑談の中もこういう話になり、確かになぁ、と思ったので挙げています。

先述のとおり、お客さんが教えてくれるルール（制約）には過不足があるのが一般的です。正しく定式化するには、どのルールが本当で、どのルールが偽物か、なんとかして判別しなければいけません。そこで、まずは過去データを制約式に入れてみる、という方法があります。過去データを投入することで、そのルールが「本当に守られているルールか」がわかるようになります。また、デバグという観点からも、過去データを代入してみるというのはとても重要です。

少し蛇足ですが、お客さんから言われたルールをとりあえず「ソフトな制約」として取り込んでみてると、どれくらいルール違反しているかがわかりやすい、というテクニックもあるようです。

制約式

$\displaystyle \sum_{i}a_{i}x_{i} \leq b$

があった場合に $u \geq 0$ を使って

$\displaystyle \sum_{i}a_{i}x_{i} - u \leq b$

と書き換え、目的関数に $u$ を追加します。すると、 $u$ は、ちょうど元の制約式の違反量に対応します。制約違反があった場合、元の定式化だとソルバーに infeasibleだと言われて困ってしまうのですが、ソフトな制約であれば、できる限り制約を満たしている解が得られるため、その後の検証がしやすくなります。

12. 最適化モデルを検証する

書籍の 6.1 Validating a model で学んだ内容です。機械学習のモデルがそうであるように、数理最適化のモデルもきちんと検証する必要があります。検証する、という観点から、数理最適化のモデルは大きく 3 つに分けることができます。

1. Infeasible models

実行可能解が存在しないような状況です。この場合は定式化を間違えている可能性が非常に高いといます。なぜなら数理最適化は、今まで人手でやっていた仕事を置き換える、という状況で利用されることが多いためです。いま人手でやっているということは、最適とは限らないが実行可能解があるはずだということです。そのため、実行可能解がないということは、定式化が間違っている可能性が高いと考えられます。

実行可能解が存在しない場合、暫定的な解がどの制約を違反しているのか列挙するのは簡単です（代入して、制約を満たしているか確認していけば良いので）。ただし、その原因を見つけるのはとても難しいです。個々の制約によって実行不可能となるのではなく、複数の制約の組合せによって実行不可能となるためです。

だからこそ、制約をヒアリングしつつ過去データ（人手でやってきた記録）を入手しておくことがとても大事です。過去データを代入することで、違反している制約がないか確認できるからです。

2. unbounded models

次のパターンは、実行可能解は存在するが、いくらでも解を良くできてしまうような場合です。たいていの場合、制約の追加し忘れによって発生します。この場合は、ソルバーがある程度頑張った結果の解を出力してくれるので、その解を見ながら、抜けている制約を検討することになりますが、ソルバーの出力してくれる解は極端な値となっていることが多いため、制約を見つけるのは比較的簡単だと思われます。

3. solvable models

最適解が得られたとしても油断してはいけません。現実的な解が得られているか見極める必要があります。ただ、ひとまず最適解が得られていれば、それを元に結果がおかしくないか検証したり、追加し忘れている制約がないか確認したりできます。前述の通り、初めから正しい定式化をできることは殆どないので、最適解が得られたとしても、検証を繰り返し、イテレーションをまわしながら定式化していくのが重要です。

13. 目的関数を設定せずに最適化をする

検証の方法の一つに目的関数を設定せずに（もしくは目的関数を色々変えてみて）最適化計算をしてみるとよい、というテクニックがあるそうです。機械学習もそうですが、数理最適化モデルは、定式化が間違っていたとしても、それらしい解が得られてしまうことがよくあります。

目的関数を設定しなかったとしても、ソルバーは実行可能解を返してくれますが、目的関数に引っ張られることがないため、極端な解が出てきやすい傾向があるそうです。極端な解が得られれば、定式化の間違いに気づきやすくなります。

まとめ

長い記事となってしまいましたが、最後まで目を通していただき、ありがとうございます。大阪大学の数理最適化寄附講座開設に関わるきっかけとなった Optimization Night の有志ですすめている輪読会で学んだことの中で、個人的に面白いなと思った Tips をピックアップして紹介しました。輪読会は現在進行中なので、 Tips ももう少し増えるかもしれませんが、その際はここに追記しようと思います。

Optimization Night はブレインパッドの太田としてではなく、太田個人として取り組んでいる活動です。（一企業のためではなく）技術者コミュニティを育てていけたらいいな、という思いでやっている活動で、まずは数理最適化界隈の方々が色々な情報を発信したり雑談したりできるような場を提供できたらなと思っているので、興味のある方はぜひご参加ください。

最後にお約束ですが...プレインパッドは今、数理最適化に真剣に取り組んでいます。こういった取り組みに興味のあるエンジニア・データサイエンティストを募集しています。数理最適化に興味のある方は、直近の転職意向の有無に関わらず気軽にお声がけください！

あと、輪読会やりましょう！一人で本読むよりたのしいよ！