数千の制約を持つ整数または混合整数プログラムがあるとします。
このIP / MIPが実行可能かどうかをどうやって判断できますか？
回答：
回答№1の場合は3数千の制約を持つ整数または混合整数計画問題があるとします。
ザ 制約数 実行不可能性に合わせて拡大縮小する必要はありません。通常、制約によって列挙する必要がある可能性の量が制限されます。別の関連問題は ランダム たとえば、3-SATでは、最も困難な問題は、制約の数が変数の数と比較して約4倍になる問題です。
どうやってこの問題を実現できるのでしょうか。
良い（混合）整数計画法があります ソルバー 妥当な時間内にいくつかの（難しい）問題を解決することができます。それにもかかわらず、一般的な整数計画問題は次のようになることが知られています。 NP困難。これは見つけることがほとんどないことを意味しますこれらの問題を一般的に妥当な時間で解決するアルゴリズム。時には私達はラッキーで、整数計画問題は解を効率的に見つけるために利用できる何らかの構造を持っていますが、言われたように：一般的にそれは難しい問題です。
ソルバーは通常、 分枝限定 どこでリラクゼーションを通してのドメイン安定状態に達するまで、変数は制限されます。次に、ソルバーは変数の1つに対して値を選択します（どの変数と最初にどの値が解決策を見つけることに大きな影響を与えるため、これらの変数と最初にどのような値が研究されるか）それから、その値で解決策が存在しないことが証明されるか、またはシステムが新しい値を割り当てる必要があるまで、問題はさらに緩和されます。モデルが、与えられた一連の割り当てられた変数で満足できないことが証明された場合、システムは バックトラック割り当てられた変数を元に戻します。これらに値を再割り当てして検索を続行します。最終的に解決策が見つかるでしょう（しかしそれは非常に長い時間がかかる場合があります）、またはソルバーは問題が充足不可能であることを証明できる（解決策が存在しない）。解決策が見つかった場合、まだ完了していません。 最適な いくつかの最適化に関する解決策関数。その場合、私たちは今から、これまでに設立されたものより良い解決策を探すという制約を加えます。新しい解決策がなくなるまでこれを続けます。その場合、最適性が証明されます。
（難しい制約に関して）正しい解を見つけるのは簡単ですが、最良の解を得るのが難しい場合は、次のようにします。 メタヒューリスティクス に 近似 最善の解決策。ここで「解空間"厳しい制約を満たす解の 有効な解を取り、それを別の解に変える多くの「突然変異関数」を構築することによって、解を反復的に操作することによって最良の解を探すアルゴリズムを生成することができます。時間がなくなった場合は、これまでのところ最良の解決策を返します。我々は我々が持っているという保証はありませんが 最適な 解決策、通常はメタヒューリスティックは非常にうまく機能し、 最適に近い 溶液。のようなメタヒューリスティック 焼き鈍し法 解の質に関して統計的な保証をすることができます。
回答№2の場合は3
確かに言えることの1つは、問題の線形緩和がすでに実行不可能である場合、整数計画問題もそうであるということです。