数理最適化セミナーのご案内

2.9 実行不可能性要因検出機能（iisDetect）の出力

　デフォルトの指定では，実行不可能性を検出するiisDetectと呼ばれる仕組みが自動的に起動され，実行不可能性の原因の探索を行い，その結果を解ファイルの出力に反映させます（制約充足問題ソルバ/資源制約付きスケジューリング問題ソルバ使用時以外）．ここでは，iisDetect機能が起動した場合の出力結果を説明します．

　以下のモデル記述（モデルファイル名lp.smpとします）に書かれた線形計画問題は，実行不可能（制約を満たす解なし）です．

Variable x, y, z;
Objective f(type = minimize);
f = x + y + z;
x >= 2 * y;       // IIS
1 + 2 * z >= x;   // IIS
y >= 2 + z;       // IIS
x >= z;
y >= 0;
z >= 0;

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

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

　この問題を解かせたとき，[Result]で始まるセクションに以下のような出力がなされます．

ERROR_TYPE                             (NUOPT 11) infeasible.
DETECTED_IIS_SIZE                                           3
(#IIS_RELATED_VAR)                                          3
INFEASIBILITY_OF_IIS                                      1.5

　それぞれの出力の意味は，以下のようになります．

タイトル 解説 備考
DETECTED_IIS_SIZE 検出されたIISに含まれる行の数 成功時のみ
(#IIS_RELATED_VAR) IISに含まれている行に含まれる変数の数 成功時のみ
INFEASIBILITY_OF_IIS IIS全体での実行不可能性 成功時のみ
NO_IIS_FOUND_BY IIS検出失敗の原因 失敗時のみ
(#NONLINEAR_CONSTR.) IIS検出失敗の原因の可能性がある非線形制約の数 失敗時のみ

　

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

Variable x, y, z;
Objective f(type = minimize);
f = x + y + z;

x * x >= 2 * y * y;
1 + z >= x;
y >= 2 + z;
x + y + z >= 0;

　出力

ERROR_TYPE                             (NUOPT 11) infeasible.
NO_IIS_FOUND_BY                                NON_LINEARLITY
(#NONLINEAR_CONSTR.)                                        1
2.8.2 納期遅れ最小化
2.10 最適化計算結果標準出力内容

 

 

上に戻る