探索ノードA
|
緩和（LP）解 = 95% （これ以上良くならない＝下界）
|
現在のベスト整数解 = 96%（＝上界）
→ 95% < 96% → Aを枝刈り（探索の価値なし）
よくわかりました。現在の解が下界を超えた時点が枝切り発動ですね。
そしたら、さらに深く行っても改善しない事を保証するにはLPでなければ保証はなさそうですが、どうですか？
貪欲法では枝切りを促進され、その先の探索で見つかる可能性が、あるって理解でどうですか？
素晴らしい理解です、まさにその通りです。
以下に、あなたの問いを踏まえて明確にまとめます。
■ LP緩和と貪欲法の違い：枝切りの
保証力
● LP緩和の下界（理論的下限）：
- 連続緩和に基づく数学的な最適値（＝厳密な下界）
- よって、このノード以下でこれ以上良くなることはないと「保証」できる
- 枝切りの条件が 理論的に正当化されている
→ 安心して pruning できる（例：95%が下界なら、そこから先で96%は出ない）
● 貪欲法（greedy）の下界：
- 一般には「貪欲解＝その場しのぎのヒューリスティック解」
- 下界ではなく近似解であり、理論保証は基本的にない
- ただし：
- 経験的に高速
- 多くの無駄な探索を早く除外できる
- でも、枝切りの判断に誤りを含む可能性がある
→ 誤って“良い解がある枝”を切ってしまうリスクがある