分枝限定法｜数理最適化

← 数理最適化一覧

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：整数計画とは・LP緩和　|　関連：切除平面法

要点（BLUF）

分枝限定法は 「分割して、限界で刈り込む」 整数計画の厳密解法。全探索を賢く間引く。
分枝：分数解の変数を $x_j \le \lfloor v \rfloor$ と $x_j \ge \lceil v \rceil$ の2子問題に分ける。
限定（バウンド）：各子問題の LP 緩和の上界が、既知の最良整数解（暫定解）を超えなければ 枝刈り。

概念 ── 全探索を間引く

整数変数 $n$ 個を総当たりすると指数通り。分枝限定は、LP 緩和の上界（整数計画とは・LP緩和）を使って「この枝は探っても無駄」と早期に切り捨て、探索木を小さく保つ。

3つの操作

分枝（branch）：LP 緩和の解で分数だった変数 $x_j = v$ を選び、2つの子問題を作る： $x_j \le \lfloor v \rfloor \quad \text{または} \quad x_j \ge \lceil v \rceil$ 分数値 $v$ は両方の子で禁止されるので、整数解は失わない。
限定（bound）：各子問題を LP 緩和で解き、上界を得る。
枝刈り（prune）：次のいずれかで枝を捨てる。
- 限定による枝刈り：上界 ≤ 暫定解の値（これ以上良くならない）。
- 実行不能による枝刈り：子問題の LP 緩和が実行不能。
- 整数性による枝刈り：LP 緩和解が整数（その枝は解けた、暫定解を更新）。

graph TD
  R["根: LP緩和 上界=21, x=3, y=1.5 (分数)"] --> A["y<=1"]
  R --> B["y>=2"]
  A --> A1["LP緩和 -> 整数解 x=4,y=0 値20 (暫定解)"]
  B --> B1["LP緩和 上界<20 -> 枝刈り"]
  A1 --> DONE["上界=暫定解 -> 最適 20 を証明"]

バウンドが最適性を保証する理由

各ノードの LP 緩和上界は「この部分問題で達成可能な最良値の天井」。暫定解（これまでに見つけた最良整数解）の値が、あるノードの上界以上なら、そのノードを深掘りしても暫定解を超える整数解は 存在し得ないので捨ててよい。探索が終わったとき、暫定解の値＝残った全ノードの上界の最大、となれば「これ以上良い整数解は無い」と 証明付きで最適が確定する。LP 緩和の上界という「証明書」が、全探索なしに最適性を保証する鍵。

Pythonで分枝の起点を見る

例： $\max 5x+4y$ s.t. $6x+4y\le24,\ x+2y\le6,\ x,y\ge0$ 整数。LP 緩和は分数解、整数最適は別の点。

import pulp

def solve(integer):
    p = pulp.LpProblem("p", pulp.LpMaximize)
    cat = "Integer" if integer else "Continuous"
    x = pulp.LpVariable("x", lowBound=0, cat=cat)
    y = pulp.LpVariable("y", lowBound=0, cat=cat)
    p += 5*x + 4*y
    p += 6*x + 4*y <= 24
    p += x + 2*y <= 6
    p.solve(pulp.PULP_CBC_CMD(msg=0))
    return pulp.value(p.objective), x.value(), y.value()

lp = solve(integer=False)   # LP緩和（根ノード）
ip = solve(integer=True)    # 整数最適（分枝限定の最終結果）
print(f"LP緩和(根): 上界={lp[0]:.2f}, x={lp[1]:.2f}, y={lp[2]:.2f}")
print(f"整数最適  : 値={ip[0]:.0f}, x={ip[1]:.0f}, y={ip[2]:.0f}")

実行結果：

LP緩和(根): 上界=21.00, x=3.00, y=1.50
整数最適  : 値=20, x=4, y=0

根ノードの LP 緩和は $y=1.5$ と分数なので、 $y \le 1$ と $y \ge 2$ で分枝する。 $y\le1$ 側を辿ると整数解 $x=4,y=0$ （値 20）が見つかり暫定解になる。 $y\ge2$ 側は上界が 20 を超えないため枝刈りされ、上界 ≤ 暫定解 20 が確定して最適性が証明される。緩和上界 21 と整数最適 20 のギャップ1を、分枝が埋めていく。

探索戦略

どの変数で分枝するか：最も分数性が強い変数、擬似コスト分枝など。良い順序が探索木を劇的に縮める。
どのノードを先に探るか：深さ優先（メモリ節約・早く暫定解）、最良優先（上界の高いノード）。
現代の MILP ソルバー（CBC・Gurobi・CPLEX）は分枝限定に 切除平面（切除平面法）・ヒューリスティック・前処理を融合した 分枝カット（branch-and-cut）。

数式の直観的意味

分枝限定は「分割統治＋限界による剪定」。分割（分枝）だけなら全探索と変わらないが、各部分問題に 緩和という安い上界計算を挿むことで、見込みのない枝を丸ごと捨てられる。これは「上界 ≤ 既知の下界なら探索不要」という単純な不等式の繰り返し。緩和が締まっている（整数ギャップが小さい、整数計画とは・LP緩和）ほど上界が低くなり、枝刈りが強く効く ── だから切除平面で緩和を締めること（切除平面法）が高速化に直結する。

⚠️ よくある誤解・落とし穴

分枝限定は厳密解法（近似ではない）。ただし最悪は指数時間。打ち切れば近似解＋ギャップ保証になる。
暫定解（incumbent）を早く良くするほど枝刈りが効く。初期ヒューリスティックが効く理由。
分枝する変数の選び方で速度が桁違い。「分数だった変数で分枝」が基本だが、選択規則が性能を決める。
LP 緩和を毎ノードで解き直すので、温かいスタート（再最適化）が効くシンプレックス（シンプレックス法）と相性が良い。