optimization - 分枝限定法-何を保存するか

Question

分枝限定アルゴリズムを実装する場合、ツリー全体を保存する必要はなく、アクティブノード（私が理解しているのはリーフノード）のリストだけを保存する必要があることを複数の本（Wolseyを含む）で読んだことがあります。

問題は、すべての祖先の境界がないと、分岐した後に新しい境界を計算する方法を理解できなかったということです。

それについてのいくつかの説明をいただければ幸いです。

Answer 1

OK、例を考えてみましょう。LP緩和を解くことによって2進整数計画法を解こうとする、かなり単純な整数計画法ソルバーを実装しているとしましょう。積分解が得られない場合は、ある変数で分岐します。最大化の問題があるとしましょう。

ちょうど1つのブランチの後に何が起こるかを考えてみましょう。ルートサブ問題を解き、目的値10の分数解が得られたとします。次に変数を分岐して、最適目的値9の左サブ問題と最適目的値8の右サブ問題を与えます。

ルートサブ問題からグローバルバウンド10を取得しました。また、すべての積分解が左サブ問題または右サブ問題のいずれかにあること、および左サブ問題に9より良い解がなく、右サブ問題に8より良いサブ問題がないこともわかっています。9より良い解はありません。ルートLP緩和はそれを私たちに伝えるのに十分ではありませんでしたが、ルートサブ問題に。

一般に、最適なグローバル境界は、アクティブなサブ問題の最悪の境界です。Fathomedのサブ問題は、既存のサブ問題よりも客観的な価値のある実行可能なソリューションを含めることができないため、関係ありません。分岐したサブ問題は、その境界が子の境界の最も弱いものによって支配される必要があるため、無関係です。