BranchingTreeが膨大になると現実的な時間内にUBを得ることができません。そこで、仮想的なUBを設定してBranchingTreeを強制枝刈りする方法について調べました。
実際には、仮想UBを上回ったらDFS分枝生成をそこで止めればよいだけです。仮想UBを下回るUBが見つからない状態で、分枝生成がStopしたら、設定した仮想UBを少し上げて枝生成を再開します。そうすることで、BranchingTreeを小さく保ったままBestUBを見つけやすくなります。
あります。しかも、古典的な手法から最新ソルバーが実装している高度なものまで、**「仮想的なUB（上界）を意図的に設定して枝刈りを強化する」**という発想は、MIPの世界でしっかり体系化されています。
あなたのバックグラウンド（高度なMIP実装経験）を踏まえて、実務的に役立つ観点で整理します。
🌲 MIPのB&Bで「仮想UB」を使って枝刈りを強化する代表的な技法
1. Objective cutoff（目的関数カットオフ）
最も直接的な方法で、
UB を意図的に小さく設定して探索空間を強制的に削る
というものです。
典型的な使い方
- 既知の実行可能解の目的値 UB があるとき
→ UB − ε をカットオフとして設定 - あるいは、ユーザが「この品質以下の解は不要」と決める
→ その値をカットオフとして設定
効果
- B&B木の大部分が「cutoff bound exceeded」で即枝刈りされる
- 特に大規模MIPで効果が大きい
ソルバーでの名称
- CPLEX: cutoff パラメータ
- Gurobi: Cutoff
- COPT: Cutoff
- SCIP: limits/objective
2. Objective tightening / Lagrangian bounding
ラグランジュ緩和やヒューリスティックで得た
強い上界（UB）を意図的に使って探索を制限する
という方法。
例
- ラグランジュ緩和で得た UB が実際よりかなり低い
- その UB をそのまま B&B の cutoff に使う
- 実際には最適解がその UB より悪い可能性があるが、
探索空間を大幅に削れる
注意点
- 最適性は保証されない（ただし近似解探索には非常に有効）
3. Early stopping / Optimality gap cutoff
実務ではよく使われる「仮想UB」の一種。
例
- MIPGap ≤ 5% になったら探索を止める
- つまり「最適解 UB は LB の 1.05 倍以内で十分」と宣言する
これは UB を LB × 1.05 に設定する のと同じ意味で、
探索木の成長を強制的に止める技法です。
4. Feasibility pump や diving で得た解を強制UBにする
あなたがよく使っているヒューリスティック（FP, diving）で得た解を
積極的に UB として設定し、cutoff を強化する
という方法。
ポイント
- FP や RINS で得た解はしばしば「そこそこ良い」
- それを UB として早期に設定すると
→ B&B の枝刈りが一気に加速する - 特に early-phase の探索木爆発を抑えるのに有効
5. User-defined incumbent acceptance criteria
SCIP や CPLEX では、
「この品質の解は受け付けない」
という設定が可能。
これは逆に言えば、
受け付ける解の UB をユーザが定義する
ということ。
例
- 目的値が 1000 以下の解だけ受け付ける
- それ以外は incumbent として採用しない
- 結果として探索木が大幅に縮小する
6. Weighted or surrogate objective bounding
目的関数を変形して「仮想UB」を作る方法。
例
- 目的関数を ( c^T x + \lambda \cdot \text{penalty}(x) ) に変更
- これに対して UB を設定
- 実質的に探索空間を制限する
これは surrogate bounding と呼ばれる古典的手法。
🔥 結論：
はい、仮想的なUBを設定して枝刈りを強化する技法は多数存在します。
特に実務では以下の3つが最も効果的です：
✔ Objective cutoff
✔ 強いヒューリスティック解を早期にUBとして設定
✔ Optimality gap cutoff（実質的な仮想UB）
もしよければ…
- あなたの問題の構造（サイズ、制約、目的関数）
- 使用ソルバー（COPT / Gurobi / SCIP / CPLEX など）
- 現状の探索木の爆発状況（ノード数、gap、時間）
を教えてくれれば、
最適な「仮想UB戦略」を具体的に提案できます。
あなたの solver integration の経験を踏まえて、
かなり踏み込んだチューニングもできますよ。
0 件のコメント:
コメントを投稿