Branch and Bound(ブランチ・アンド・バウンド法)
- 提唱者
- Ailsa Land & Alison Doig
- 年
- 1960
- 種類
- Exact combinatorial optimization algorithm
- 系統
- Mathematical programming
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
Branch and Bound(ブランチ・アンド・バウンド法)は、1960年にAilsa LandとAlison Doigによって導入された、組み合わせ最適化問題および整数最適化問題のための系統的かつ厳密なアルゴリズムである。これは、探索空間を部分問題の木として組織化し、緩和問題から導出される上界を用いて、既知の最良解を改善できない枝を刈り込み、大域的最適整数解を見つけることを保証する。これは、オペレーションズ・リサーチ、ロジスティクス、スケジューリング、工学設計で使用される現代の混合整数計画法のソルバーの基盤となっている。
手法の背後にある直感
広大な迷路の部屋に隠された最高価値のアイテムを探していると想像してほしい。すべての部屋を調べる代わりに、各通路に入る前に、そこから到達可能な最大価値を推定する。その上限が、すでに持っている最良のアイテムよりも低い場合、その通路全体を中を見ずにスキップする。Branch and Boundも同様に機能する。問題をより小さな部分に分割し、各部分の楽観的な上界を計算し、現在の最良解を明らかに改善できない部分は即座に破棄する。
歴史学
LandとDoigは1960年にEconometrica誌に基礎的なBranch and Bound論文を発表し、それを離散計画法のための自動化された方法として位置づけた。Littleら(1963)は巡回セールスマン問題にこの手法を適用し、組み合わせ最適化におけるその役割を確固たるものにした。Dakin(1965)は、今日最も一般的に使用されている形式であるLP緩和分岐を導入した。その後の数十年で、カットプレーン(ブランチ・アンド・カット)と列生成(ブランチ・アンド・プライス)の統合が見られ、Branch and Boundはすべての主要な商用整数計画ソルバーのエンジンとなった。
使うべき場面
混合整数線形計画法または純粋整数線形計画法に対して、証明可能な最適解を見つける必要があり、近似解を受け入れられない場合にBranch and Boundを使用する。これは、有用なバウンドを提供する線形(または凸)緩和で定式化できる問題を想定している。探索木の列挙が爆発する非常に大きなインスタンス、タイトな緩和がない非線形整数計画法、または計算時間が厳密に制限されているリアルタイム設定には、あまり適していない。そのような場合、ヒューリスティクスまたはメタヒューリスティクスが好まれる場合がある。
限界と注意点
- 最悪ケースの複雑さは指数関数的である。構造が悪いインスタンスでは、ツリーが法外に大きくなる可能性がある。
- パフォーマンスは、分岐変数とノード選択戦略の選択に大きく依存する。
- 意味のある上界を提供する、扱いやすい緩和が必要である。弱いバウンドは最小限の剪定につながる。
- 多くの開いているノードを同時に格納する必要がある場合、メモリ要件が大きくなる可能性がある。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 整数および組み合わせ問題に対する大域的最適性を保証する。
- バウンドベースの剪定により探索を劇的に削減する — しばしば、完全な列挙木のほんの一部しか探索されない。
- 柔軟性:さらなる効率のために、カットプレーン(ブランチ・アンド・カット)やヒューリスティックバウンド(ブランチ・アンド・プライス)を組み込むことができる。
- 広く成熟した商用ソルバー(CPLEX、Gurobi)およびオープンソースツール(GLPK、CBC)に実装されている。
応用
- オペレーションズ・リサーチにおける航空乗務員スケジューリングとフリート割り当て。
- サプライチェーンネットワーク設計と施設配置問題。
- コンピュータ工学におけるVLSI回路レイアウトとレジスタ割り当て。
- 計算生物学におけるタンパク質構造予測とゲノムアセンブリ。
- カーディナリティ制約付き金融ポートフォリオ最適化。
使い方
使い方
アルゴリズムは、まず問題の緩和されたバージョン(通常はLP緩和)を解くことから始まる。これは、整数制約を無視する。この緩和は、実行可能なすべての整数解が緩和でも実行可能であるため、真の最適値に対する上界をもたらす。緩和された解が整数値である場合、問題は直ちに解決される。
数式
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}緩和された解に分数変数がある場合、アルゴリズムは、変数をその床または天井のいずれかに強制する相補的な制約を追加することによって、実行可能領域を分割する。各分割は、探索木内に新しい子ノードを作成し、効果的に1つの部分問題を、よりタイトなドメインを持つ2つのより小さな部分問題に分割する。
数式
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilアクティブな各ノードは、独自のLP緩和バウンドを受け取る。そのバウンドが、これまでに見つかった最良の整数解(インカレントと呼ばれる)を超えないノードは、より良い解を含み得ないため、剪定される。タイトなバウンドが重要である。バウンドがタイトであるほど、探索する必要のあるノードは少なくなる。
数式
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}ノードは、次の3つの条件のいずれかでファソム(永久に閉じられる):緩和が実行不可能である、バウンドがインカレントよりも良くない、または緩和された解がすでに整数実行可能である。最後のケースでは、新しい解がインカレントを改善する場合、インカレントが更新される。すべてのノードがファソムされた時点でアルゴリズムは終了し、その時点でインカレントが大域的最適解となる。
数式
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)よくある落とし穴
- 分岐変数の選択を誤ると(例:常に最初の分数変数で分岐する)、深い不均衡なツリーと遅い収束につながることが多い。
- 有効な不等式(カットプレーン)を無視することは、緩和バウンドを大幅にタイトにする機会を逃すことを意味する。
- 最適性ギャップが報告されないまま早期終了すると、実践者がほぼ最適解を正確なものと誤解する可能性がある。
- 専門的な凸化なしに非線形または非凸緩和にBranch and Boundを適用すると、無効なバウンドと不正確な結果が生じる可能性がある。
よくある質問
Branch and Boundは網羅的列挙とどう違うのか?
網羅的列挙は、すべての実行可能な整数解を明示的に評価するが、これは大規模問題では計算上不可能である。Branch and Boundは、探索木の各ノードで緩和ベースの上界を計算し、バウンドが既に見つかった最良解を超えることができない場合はいつでもサブツリー全体を剪定することにより、これを回避する。実際には、ツリーのごく一部しか検査されない。
Branch and BoundにおけるLP緩和の役割は何か?
LP緩和は整数制約をドロップし、問題がシンプレックス法または内点法によって多項式時間で解けるようにする。その最適値は、対応する整数部分問題の上界として機能する。このバウンドがタイト(真の整数最適値に近い)場合、探索する必要のあるブランチは少なくなる。多くの場合、有効な不等式を追加することによって達成されるタイトな緩和は、アルゴリズム全体の速度を劇的に向上させる。
Branch and Boundと遺伝的アルゴリズムのようなメタヒューリスティクスをいつ使い分けるべきか?
最適性の証明が必要で、計算時間を許容できる場合はBranch and Boundを選択する。これは、構造化されたLP緩和を持つ中規模問題に理想的である。問題が非常に大きい、有用な緩和がない、またはほぼ最適解で許容できるタイトな時間予算内で解決する必要がある場合は、メタヒューリスティクスが好ましい。多くの実践者は両方を組み合わせている。早期終了ギャップ許容誤差でBranch and Boundを使用する。
関連する手法
参考文献
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
DOI 文献を開くコピーしました。