MIPソルバを用いた開発におけるデバッグのテクニック
はじめに
はじめまして、データサイエンティストの的場です。
現実世界の課題を解決するにあたって、問題を線形計画問題(Linear Programming, LP)・混合整数計画問題(Mixed Integer Programming, MIP)に定式化し、汎用ソルバーを使って解くというアプローチがしばしば取られます。汎用ソルバーを用いることで問題を高速に解けるなどのメリットが得られますが、一方でソルバーを用いた開発には特有の難しさがあり、デバッグに苦慮することが多いです。
この記事では、MIPとして定式化した問題をソルバーで実装する際の難しさ、および対処法について説明します。 なお、MIPの定義や定式化の方法などの説明は行わないので、そちらについては当テックブログの別記事(線形計画問題・混合整数計画問題をソルバーで解く)をご参照ください。
MIPのデバッグの難しさ
MIPソルバーを用いる際のデバッグが難しい理由として、ソルバーの挙動を直感的に把握しづらいことが挙げられます。ソルバーの挙動は（ユーザー視点では）ブラックボックスに近く、かつソルバーから与えられる情報は限定的です。そのため、想定と異なる解が出てきたときに、何が原因なのかを特定することが難しい傾向があります。例えば、想定に反して実行可能解がなかったときは、
- 入力データが間違っている
- 制約のどれかが間違っている
- 制約式自体が間違っている
- 制約は正しいが、実装が間違っている
- データも制約も正しく、解に関する自分の認識が間違っている
など、色々な可能性があり得ますが、これらのどれに当てはまるか検証するのは中々難しいです。さらに原因を絞り込んで制約に間違いがあるとわかったとしても、どの制約に原因があるかが直感的にわかることは少なく、全く想定していなかった制約が原因であったと判明することも珍しくありません。
デバッグに使えるテクニック・心構え
小さなモデルでデバッグする
新規開発の場合
制約を追加していく途中でもこまめに最適化を実行し、実行可能解が存在しなくなっていないかを確認しながら進めると良いです。実装を始める際には一通り定式化が終わっていることが多いので、一気に実装してしまいたくなりがちなのですが、それは危険です。制約式を多数追加した後に実行可能解がないことに気づくと、どの制約式に原因があるのかを確認するのがかなり手間になってしまいます。
制約を新たに追加する度にこまめに最適化を実行し、実行可能解が存在することをチェックしながら実装を進めると、どこにミスがあるかを特定する手間が減るうえ、定式化自体が間違っていたという場合にも気づきやすくなります。
既存の大きなモデルを扱う場合
プロジェクトに途中から参加し、既に動いているある程度大きなモデルを変更・修正するような場合を想定します。前項のような対処は難しいですが、簡単な設定の問題インスタンスを持っておくことで、ある程度の対処は可能です。
自分の参加しているプロジェクトでは、最適化モデルに新たな機能を追加する際に、簡単な問題設定と期待する結果の組からなるテストを書くというルールで開発を行っています。これにより、例えば新しく機能を追加した時に何らかのテストが落ちた場合、そのテストで扱っている領域に関連する部分に問題がありそうだと当たりをつけることができます。
LPファイルを出力し、変数・制約・目的関数を確認する
問題を正しく定式化できているかを確認する際に使える手段です。
LPやMIPの問題を表現する共通のフォーマットとしてLPファイルというものがあり、大体のソルバーやモデラーで出力方法が用意されています（例: PuLPだとwriteLP(), OR-ToolsだとExportModelAsLpFormat() など）。LPファイルの詳細については宮代 隆平 の web ページ（整数計画法メモ）などを参照してください。
ただし、モデルのサイズが大きくなってくると、目視での確認用途として使うのは難しくなります。
予想に反して実行可能解がないときの対策
制約を一部除去して試す
もし原因が単一の制約にあると予想できるなら、「制約の一部を除去してみて実行可能になるか確かめる」という作業を繰り返せば、問題のある制約を発見できる可能性が高いです。制約の半分をコメントアウトし、実行可能解があればその範囲を、なければコメントアウトしなかった範囲を探索する、ということを二分探索的に繰り返すのも良いでしょう。 ただし、原因が単一の制約でなく、いくつかの制約が合わさると実行不可能になる、という可能性も理論上あり得るので注意が必要です。
また、そもそもこれらの作業がやりやすくなるように、制約を意味のあるまとまりに分けて実装しておくことが重要です。開発一般に言えることではありますが、なるべく凝集度を高く、結合度を低く保つことにより最適化モデルのデバッグも行いやすくなります。
Irreducible Inconsistent Subsystem (IIS) を出力する機能を使う
前項の項目をある程度自動的に行う方法として、Irreducible Inconsistent Subsystem(IIS, Irreducible Infeasible Set とも)を出力する機能が使えます。
Irreducible Inconsistent Subsystem(IIS) とは、制約の集合であり、以下の2条件
- 実行不可能
- どの制約を取り除いても実行可能となる
を満たすものを指します。なお、IISは複数存在し得ます。例えば以下の制約がある場合、$\{1, 2, 3 \}, \{1, 2, 5\}, \{2, 4\}$がIISとなります。
$$
\begin{align}
x_1 - x_2 &\leq 0 \tag{1} \\\
x_2 &\leq 1 \tag{2} \\\
-x_1 - x_2 &\leq -2 \tag{3} \\\
-x_2 &\leq -2 \tag{4} \\\
-2x_1 - x_2 &\leq -4 \tag{5}
\end{align}
$$
Gurobi や CPLEX 等の商用ソルバには、IISを検出する機能が備わっています。 （参考: https://www.gurobi.com/documentation/current/refman/py_model_computeiis.html ）
スラック変数の利用
実行不可能となる原因の制約にはあたりがついている状態で、実行可能解からどのくらい「離れて」いるか（どのくらい違反を許せば実行可能解が得られるか）を調べるのに役立つ方法です。
以下のような最適化問題を考えます（簡単のため、制約が1つだけの例とします）。
$$
\begin{align*}
\min_{x} \quad &f(x) \\\
\text{subject to} \quad &g(x) \leq b
\end{align*}
$$
この問題に実行可能解が存在しないときに、スラック変数 $s \geq 0$を導入し、以下のように書き換えます（$c \geq 0$ は定数）。
$$
\begin{align*}
\min_{x, s} \quad &f(x) + c s \\\
\text{subject to} \quad &g(x) - s \leq b
\end{align*}
$$
$c$ の値を $f(x)$ のスケールに比べて十分大きく(※)とっておけば、上記の問題は
- $s = 0$ とできるなら、そうする。元の問題と同じ最適解が得られる。
- $s = 0$ とできないなら、可能な限り $s$ を小さくするという前提で、元の目的関数 $f(x)$ を最小化する。
という設定になり、$s$ の値を見ることで制約違反の程度を知ることができます。 （※）定式化に不必要に巨大な数を用いるとソルバーの実行速度に悪影響があるため、ペナルティの大きさには注意が必要です。
なお、等式制約$g(x)=b$の場合は、以下のようにスラック変数を2つ導入するか、
$$
\begin{align*}
g(x) + s_{+} - s_{-} = b
\end{align*}
$$
以下のように不等式2つで表現することができます。
$$
\begin{align*}
g(x) - b &\leq s \\\
b - g(x) &\leq s
\end{align*}
$$
予想と異なる最適解が出力されたときの対策
本当に最適解か確認する
MIPソルバーでは通常、事前に設定された制限時間になっても最適解が見つかっていない場合は、その時点で得られている最良の解を返します。これをうっかり最適解と誤認してしまうことが稀にあるので、最適化ステータスをログに流す等してきちんと確認しましょう。最適解ではなかった場合は、制限時間を増やしてやり直してみると良いです。
変数を固定して再実行する
ソルバーが出力した最適解(A)がどうも最適解とは思えない、というときに使える方法です。自分の思う最適解(B)を制約として追加した状態で最適化を行い、結果を観察します。 これにより実行不可能となった場合、前章の方法を使って原因を調べていくことができます。解が出た場合は、目的関数の値を比較するなどして、「モデルがなぜ(A)を(B)より高く評価したか」を深掘りすることができます。
こちらについても制約と同様に、目的関数への様々な項目の寄与を意味のあるまとまりに分けて実装しておくことで、原因の特定がより簡単になります。
おわりに
MIPソルバーを使ったモデルのデバックには特有の難しさがあり、原因の特定や修正に時間がかかることがあります。本記事ではそのような状況で役立つテクニックを紹介しました。 紹介したテクニックの多くは「怪しい範囲をなるべく小さく絞り込んでいく」という普遍的な結論に集約されるかと思います。不具合の原因が中々見つからないと焦ってしまいがちですが、そんな時こそ基本に立ち返り、落ち着いて問題の切り分けを行うことが大事なのかもしれません。
この記事が読者のMIPソルバを使った開発の一助となれば幸いです。
エムシーデジタルでは、技術力向上のためのイベントや勉強会なども定期的に実施しています。 もしエムシーデジタルで働くことに興味を持っていただいた方がいらっしゃいましたら、カジュアル面談も受け付けておりますので、お気軽にお声掛けください！
採用情報や面談申込みはこちらから
