最適化モデルを解くとき、定義された制約をすべて満たすことができず、実行不可能(Infeasible)となるようなシナリオ(入力)が発生することがあります。このような状況は、モデルを定式化していくとき、データの更新、制約の修正、新しい制約の導入の際にも起こり得ます。Infeasibleとなった場合、実行不可能性の根本的な原因を特定して修正するか、あるいは、実行可能なモデルにするために緩和してもよい制約のサブセットを特定する必要があります。この記事では、実行不可能性をどのように特定し、診断し、対処するかを議論し、いくつかのヒントとベストプラクティスを紹介します。
モデルが実行不能であることを判断するには？
求解後のGurobiモデルのステータスは、Optimization Status Code を参照するか、ログファイルを確認することで判断できます。モデルが実行不可能であることが証明された場合、ステータスコードは "INFEASIBLE "となり、ログファイルのメッセージは "Infeasible model "となります。モデルが実行不可能であるか、または非有界であることが証明された場合、ステータスコードはINF_OR_UNBDとなり、ログファイルのメッセージは "Model is infeasible or unbounded "となります。このステータスの詳細については、How do I resolve the error "Model is infeasible or unbounded"? を参照してください。
実行不可能性の判断とその対処
実行不可能の原因となる制約のサブセットを決定するために、ソルバーから確認できる2つの情報があります：
- モデルを実行不可能にしている制約のサブセットは何か？
- モデルを実行可能にするために、モデルにどのような変更を加える必要があるか？
一つ目の情報を得るために、GurobiではIrreducible Infeasible Subsystem (IIS)を計算することができます。これは、制約と変数上下限値の部分集合からなる極小の制約集合で、その制約集合単体で実行不可能です。しかし、このサブシステム(部分集合)から1つでも制約や上下限値を取り除くと、そのサブシステムは実行可能となります。Pythonでは、Model.computeIIS() メソッドを使用してIISを計算することができます。
*実行不能なモデルは複数のIISを持つ可能性があります。また、Gurobiが返すIISは必ずしも最小のサイズとなるIISとは限りません。
二つ目の情報を得るために、Gurobiはモデルが実行可能となるために変化させる必要がある(ある指定された指標に対する)最小の摂動量を計算することが可能です。Pythonでは Model.feasRelax() と Model.feasRelaxS()メソッドでこれを行うことができます。後者は簡略化されたバージョンで、それを表す "S "という接尾辞がついています。
これら2つの機能の使用方法と例については、以下を参照してください。
- compute IISについて： How do I use 'compute IIS' to find a subset of constraints that are causing model infeasibility?
- feasibility relaxationについて： How do I change variable and/or constraint bounds to make an infeasible model feasible using feasRelax?
さらなる詳細についてはマニュアルの Diagnose and cope with infeasibility を参照してください。
Tipsとベストプラクティス
問題を引き起こしている可能性の高い制約と上下限値の事前スクリーニング
問題サイズを小さくし、結果の解釈可能性を向上させるため、compute IISまたはfeasibility relaxationのいずれかを実行する前に、潜在的に問題を引き起こしうる制約と上下限値のリストを定義することは有用です。このようなリストを拡張していく際に、考慮すべきいくつかの基準があります。
- データの変更によって影響される制約や上下限値
- ユーザーの入力によって定義される制約や上下限値
- モデル開発の中で最近修正された制約や上下限値
問題を引き起こす可能性のある制約や上下限値のリストは次のように利用できます。
- compute IISについて：IISConstrForce, IISLBForce, IISUBForce, IISSOSForce, IISQConstrForce, IISGenConstrForce 属性を使ってリストにある制約/上下限値のみを使ってIISを計算することができます。
- feasibility relaxationについて： Model.feasRelax()を使う場合、vars 引数と constrs 引数を与えることで、リストにある制約/上下限値のみに緩和を有効にできます。これらの引数は違反を許す制約と上下限値の緩和を許す変数を制御します。また、IISの結果をfeasibility relaxationを行う制約や変数のリストとして考えることも可能です。
Compute IISは、大規模なモデルでは計算コストが高くなる可能性があることに注意
計算量の観点では、線形計画法（LP）ではIISの計算は比較的コストが低いと言えますが、混合整数計画法（MIP）の問題では計算コストが高くなります。さらに、計算した結果として得られるIISが大きくなり、解釈が難しくなる可能性があります。
大規模なモデル、特にMIPモデルの場合は、違反数を最小化することを目的としたfeasibility relaxationを使用することをお勧めします。 これを行うには、Model.feasRelaxS() や Model.feasRelax() の第一引数をrelaxobjtype=2 に設定する必要があります。 これは計算量が少なく、これらの計算を行う目的によっては、compute IISの代替とみなすことができます。
変数の下限値が意図したものであるか確認する
変数を定義する際、Gurobiはデフォルトで下限値に0を設定します。変数に負の値をとることを想定している場合、これによりInfeasibleになる場合があります。
その他の資料