「compute IIS」を使って実行不能の原因となる制約の部分集合を見つけるには？ – Gurobi ヘルプセンター

Gurobiの「compute IIS」機能は、「モデルを実行不能にしている制約の部分集合は何か？」という疑問に対応するために設計されています。この記事では、この機能の使い方を紹介します。関連する記事モデルが実行不能(Infeasible)な理由を調べるには？では、実行不能性解析ツールについてさらに詳しく解説しています。

「compute IIS」機能は、モデル内の矛盾する制約と変数の上下限指定の既約な集合を特定します。実行不能なモデルの原因を特定するために、すべての制約と変数の上下限を分析することは非常に困難です。Gurobiの「compute IIS」ツールは、問題をはるかに小さい矛盾する制約と上下限の部分集合に絞り込むことができ、理解および解析を容易にします。

既約実行不能部分系 (Irreducible Infeasible Subsystem: IIS) とは、システム内の実行不能な特定の制約と変数の上下限の部分集合を指します。この部分集合は下記の2つの重要な条件を満たします：

それ自体が実行不能であり、
部分集合から任意のひとつの制約または上下限を取り除くと、実行可能な部分系になる。

特に、IISは必ずしも（要素数に関して）最小の実行不能な部分集合ではない場合があります。より具体的には、実行不能なモデルには複数のIISが存在する可能性があり、Gurobiが返すものが必ずしも最も少ない制約や上下限を含むものとは限りません。ただし、Gurobiのアルゴリズムは一般的により小さいIISの検出を優先します。

「compute IIS」の結果は人間のユーザーが検査・解析することを想定しており、モデルの問題となっている制約を理解するための出発点を提供します。IISが小さいほど、モデル内の特定の問題をより効果的に特定できます。

計算の複雑さの観点では、IISの計算は線形計画法（LP）問題に対しては比較的安価ですが、混合整数計画法（MIP）問題に対してはより計算コストが高くなります。

実践的な使用ガイド

Pythonでは、Model.computeIIS() メソッドを使ってIISを計算できます。これにより疑わしい制約のリストを絞り込むことが可能です。モデルを構築して解いた後、次のようにしてIISを計算できます：

import gurobipy as gp
from gurobipy import GRB

# Build the model
[...]

# Optimize
model.optimize()

# do IIS if the model is infeasible
if model.Status == GRB.INFEASIBLE:
    model.computeIIS()

IISの結果を得るために次のようにしてILPファイルを保存できます：

model.write('iismodel.ilp')

または、各制約や変数のIIS属性をIISConstr、IISLB、IISUB、IISSOS、IISQConstr、IISGenConstrを使って照会することもできます。これらは対応するモデル要素が計算されたIISのメンバーかどうかを示します。次はIISに含まれる変数の上下限値と線形制約を出力する例です：

# Print out the IIS constraints and variables
print('\nThe following constraints and variables are in the IIS:')
for c in model.getConstrs():
    if c.IISConstr: print(f'\t{c.constrname}: {model.getRow(c)} {c.Sense} {c.RHS}')

for v in model.getVars():
    if v.IISLB: print(f'\t{v.varname} ≥ {v.LB}')
    if v.IISUB: print(f'\t{v.varname} ≤ {v.UB}')

このメソッドを使用する際、IISConstrForce、IISLBForce、IISUBForce、IISSOSForce、IISQConstrForce、IISGenConstrForce属性を使って、要素をIISに強制的に含めたり無視したりするようにカスタマイズできます。

使用例

workforce1（C、C++、C#、Java、MATLAB、Python、R、VB）のサンプルプログラムでCompute IISの例を確認できます。ILPファイルを保存すると、次のIISが返されます。

\ Model assignment_copy
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize

Subject To
  Thu4: x[Cathy,Thu4] + x[Ed,Thu4] = 4
Bounds
  -infinity <= x[Cathy,Thu4] <= 1
  -infinity <= x[Ed,Thu4] <= 1
End

これは、x[Cathy,Thu4]とx[Ed,Thu4]の2つの変数の上限1が矛盾しており、その和が4に制約されていることを示しています。これら2つの変数の和は最大でも2であるため、これら3つの制約は矛盾しています。つまり、ここで挙がった上限または制約のいずれかを削除すればモデルは実行可能になります。

注意： Matlabでは、IISの計算とILPファイルの作成は1つのステップで行う必要があります：

>> params.resultfile = 'iismodel.ilp'
>> iis = gurobi_iis(model, params)

実践的な使用ガイド

使用例

その他の資料

関連記事