ユーザーが既知の許容解を持っている問題に対して、Infeasibleの判定がされた場合、最初のステップとしてはその解がモデル上で許容かどうかを調査します。例えば変数の値を既知の解に固定したモデルを作成し、最適化を実行してみます。固定したモデルは変数の上下限値を固定したい値に設定することで作成可能です。
もし固定したモデルが infeasible の場合、オリジナルのモデル上に問題がある可能性があります
- 変数にマイナスの値をとらせたい場合。 このような時には変数の下限値が適切な負の値に設定されているかを確認してください。下限値のデフォルトの値は0に設定されています。
- 固定したモデル上でのIISがどうなっているかを確認する。モデルに対してIIS(Irreducible Infeasible Subsystem) を計算することで、問題となっている可能性のある部分を抜き出すことができます。詳細は How do I use 'compute IIS' to find a subset of constraints that are causing model infeasibility? を参考にしてください。
Numerical issues もこのような不整合を引き起こす可能性があります
-
Numerical issues についてはこちらを参考にしてください。
- まずはGurobiのログに、変数や制約が実現可能性の許容範囲に違反していることを示す警告が表示されていないか確認してみてください。
- IntFeasTol = 1e-09 や FeasibilityTol = 1e-09のような非常にタイトなトレランスで最適化を実行している 。 非常にタイトなトレランス下で最適化を実行するとNumerical issues の問題へつながることがあります。例えば"ほとんど1"に近い値をとるバイナリ変数がそのような厳しいトレランスを満たさない場合、0となってしまう場合があります。その結果、誤った値に変数が固定され、予期せぬ結果を生じることがあります。
- Big-Mとして必要以上に大きな値を利用している。 Big-M 制約における大きすぎるBig-Mの値は in a "Trickle Flows" と呼ばれる問題を引き起こすことがあります。例えば y <= 1000000 * x,（x はバイナリ変数、 y >=0）のような制約を考えます。デフォルトのIntFeasTol (1e-5)のもとで、 x = 0.0000099999, y = 9.9999 という解は整数条件を満たします。これは、 x≒0のもとでyが非負の値をとれることを意味しています。このようなふるまいによって、予期せぬ解が導かれることもあります。よってBig-Mの値は可能な範囲で小さくすることが推奨されます。Dealing with big-M constraints を参照してください。
- 非線形関数を利用している。FuncPieces, FuncPieceLength, FuncPieceError などのパラメータで、非線形関数の区分線形近似の粒度を調整してみてください。また、変数には可能な範囲でタイトな上下限値を設定することをお勧めします。
- その他関連するパラメータ:
- NumericFocus パラメータを大きめの値に設定する。
- Aggregate パラメータを0に設定する。
- Presolve を無効にするとNumerical issuesの解決につながることがある。
- ただし、Numerical issuesの解決に対して最も推奨される方法は定式化の修正やスケーリングです。guidelines for numerical issues を参考にしてください。
コメント
0件のコメント
記事コメントは受け付けていません。