3.7. 実行不可能性要因検出機能

デフォルトでは,実行不可能性を検出する iisDetect と呼ばれる仕組みが自動的に起動され, 実行不可能性の原因の探索を行います(制約充足問題ソルバ使用時以外). ここでは,iisDetect 機能が起動した場合の結果を説明します.

以下のモデル記述に書かれた線形計画問題は,実行不可能(制約を満たす解なし)です.:

x = Variable(lb=0)
y = Variable(lb=0)
z = Variable()
problem = Problem()
problem += x + y + z
problem += x >= 2 * y    , 'cons1'  # IIS
problem += 1 + 2 * z >= x, 'cons2'  # IIS
problem += y >= 2 + z    , 'cons3'  # IIS
problem += x >= z,         'cons4'
problem.solve()
assert problem.status == NuoptStatus.INFEASIBLE

よく見るとモデルで IIS のマークが付いた制約式群のどの一つを除去しても実行不可能性は解消しますが, すべてを満たす x, y, z は存在しません. また,マークされていない最後の制約式は実行不可能性とは無関係で,除去する,しないにかかわらず, 問題は実行不可能であることもわかります.

iisDetect 機能はこのように,実行不可能性の原因となっている行の組(Irreducible Infeasible Set: IIS) を特定して出力します. 一般に実行不可能な問題について IIS は複数存在しますが,このアルゴリズムは可能な限り小さなもの (含まれている行が少ない)ものを求めるようなヒューリスティクスが導入されています.

IIS オブジェクトは result.iis 属性で取得することができます.:

problem.solve(silent=True)
print(problem.result.iis)

この出力は次のようになります.:

0: cons3: violation=1.5
    y-z>=2
1: cons2
    2*z-x>=-1
2: cons1
    x-2*y>=0

cons1, cons2, cons3, cons4 の制約のうち,cons1, cons2, cons3 が互いに矛盾する制約式の最小の組(のひとつ) であることが分かりました. また,実行不可能ではあるものの,変数には何らかの値が設定されており,実際に制約違反を起こしている制約は cons3 で,違反量は 1.5 であることも分かります.

更に problem.result.iis[0] として詳細情報にアクセスすることもできます. 詳細な属性は IIS をご確認ください.

モデルに非線形の式が含まれていた場合,IIS の正確な検出はできません. その場合には,ヘッダー部には IIS の検出が非線形性のために失敗したというメッセージが現れ, 非線形な制約がいくつあるかを示します.

3.7.1. solfile オプション

solfile オプションは IIS を含めた解ファイルの出力を制御します.解ファイルはデフォルトでは出力されません. 解ファイルは Problem オブジェクト生成時,または solve メソッド呼び出し時に solfile オプションで 制御することができます.:

problem.solve(solfile=True)  # {problem.name}.sol が出力される

ファイル名を指定することもできます.:

problem.solve(solfile='myproblem')  # myproblem.sol が出力される

解ファイルの実行不可能性要因出力部は次のような出力になります.:

%%
%%    IIS
%%
-----------------------------------------------------------------------------
#1      cons1         :   1*x-2*y
                                                    >=          0   (         0)
-----------------------------------------------------------------------------
#2      cons2         :   -1*x+2*z
                                                    >=         -1   (        -1)
-----------------------------------------------------------------------------
#3      cons3    INFS :   1*y-1*z
                                                    >=          2   (       0.5)
-----------------------------------------------------------------------------

iis オプションで iisDetect 機能をオフにしている場合は実行不可能性要因出力部は出力されません.

解ファイルの見方については 解ファイル を ご確認ください.

3.7.2. iis オプション

iis オプションは iisDetect 機能のオン/オフを制御します.iisDetect 機能はデフォルトではオンになっています.:

problem.solve(silent=True)
print(problem.result.iis)

この出力は次のようになります.:

0: cons3: violation=1.5
    y-z>=2
1: cons2
    2*z-x>=-1
2: cons1
    x-2*y>=0

実行可能な場合や iisDetect 機能をオフにした場合など IIS が取得できない場合は空の IIS オブジェクトが設定されます.:

problem.solve(silent=True, iis=False)  # iisDetect 機能をオフにする
print(problem.result.iis)  # no IIS

iisDetect 機能をオフにすると実行不可能性要因検出が行われなくなるため,実行不可能時の高速化が期待されます.