私は C++ で CPLEX を使用して、ハブの場所の問題である MIP を解決しています。最近、問題が確かに実行可能であるにもかかわらず、CPLEX が実行不可能と考える非常に正確な入力セット (つまり、CPXMIP_INFEASIBLE) を見つけました。この問題は、MIP Presolve 中に CPLEX で発散するように見えます。通常、その時点で問題はヌル問題に縮小されますが、実行不可能な入力セットには含まれません。
入力データをわずかに調整すると、CPLEX のソリューションを見つける機能が切り替わる可能性があることがわかりました。たとえば、250.242566 を 250.242567 に変更するか、各入力値を最も近い整数に丸めるだけでも、完全に有効なソリューションが得られます。
私が持っている 2 つのスラック制約を緩和することも解決策を可能にしますが、これらの制約は入力データを考慮して破られるべきではありません。解決後のこれらの制約変数の値は、約 0 ですが、わずかに負の値 (-0.7e-10 など) です。(値が 0 より大きいはずなので、これは疑わしいです。)
何が起こっている？私は無知です。精度に関連するいくつかの CPLEX 変数 (つまり、CPX_PARAM_NUMERICALEMPHASIS、CPX_PARAM_EPOPT、CPX_PARAM_EPMRK、CPX_PARAM_EPRHS) を調整しようとしましたが、何も役に立ちませんでした。入力データ自体はあまり精度を必要としません。入力の最小値は 1.412 で、最大値は 1520.984907 です。
アドバイスや提案をいただければ幸いです。
アップデート：
MIP の Presolve 中に、実行不可能な問題が実行可能な問題から分岐していることに気付きました。
両方の問題について CPXgetprestat をチェックすると、2 つの問題の間に見られる顕著な違いの 1 つは、pcstat ベクトルにあり、実行不可能なセットで 1 つの変数を集約できないことです (つまり、実行不可能な問題では値が 0 であるのに対し、実行可能な問題では -4 です)。 .
また、CPXgetprestat の ocstat および orstat ベクトルは、実行不可能な問題にゼロ以外の値をそれぞれ 1 つずつ持っています (実行可能な問題は、ヌル問題に縮小されているため、値はありません)。orstat[0] == 7 かつ ocstat[0] == 1 の場合、Presolve 前の問題の 7 行目と 1 番目の変数に何か注目すべき点があるということですか? これを確認するにはどうすればよいですか？
両方の問題で CPXwriteprob の出力を比較しましたが、問題を実行不可能にするために 0.0001 だけ変更した入力値以外に違いはありません。