この記事について

前回の記事では「LP緩和と上界・下界で MIP の最適値を挟み込む」考え方を説明しました。今回はそれを具体的に実行する 分枝限定法（Branch and Bound） を、ナップサック問題の手計算例で体感してみます。

「ソルバーが内部で何をしているのか」が少しクリアになれば幸いです。

分枝限定法の概要

分枝限定法は整数計画問題に対する汎用的な厳密解法です。2つの操作を繰り返します。

操作	やること	目的
分枝（Branch）	実行可能領域を2つに分割して部分問題を生成	整数条件を少しずつ固める
限定（Bound）	各部分問題の下界値を計算し、見込みのない枝を省く	無駄な探索をカット

分枝操作の具体的な手順は以下のとおりです。

① LP 緩和問題を解く
② LP 最適解の中で 緩和解が実数値を取る変数 $x_t$ を1つ選ぶ
③ $x_t \leq \lfloor \bar{x}_t \rfloor$ に制限した問題と $x_t \geq \lceil \bar{x}_t \rceil$ に制限した問題の2つの部分問題を生成する（ $\bar{x}$：緩和解、つまり、$x_t$ が緩和解以下の整数値と緩和解以上の整数値となる部分問題を生成する。）

分枝の例：LP最適解で x₂ = 2/3（小数）が出た場合

        現在の問題
        /         \
   x₂ ≤ 0      x₂ ≥ 1
  （部分問題1） （部分問題2）

限定操作では、

LP 緩和が実行不能 → 部分問題も解なし（枝刈り）
LP 緩和の最適値が暫定値を改善できない → この枝から改善は望めない（枝刈り）
LP 最適解が整数解 → 暫定値を更新して探索終了

ナップサック問題で体感する

例題を使って手計算してみましょう。

問題設定

容量 4 のナップサックに荷物1〜4を詰め込む最大化問題です。

\text{maximize} \quad 3x_1 + 4x_2 + x_3 + 2x_4

\text{subject to} \quad 2x_1 + 3x_2 + x_3 + 3x_4 \leq 4, \quad x_i \in \{0, 1\}

各荷物のデータ：

荷物	重さ $w_i$	価値 $p_i$	価値/重さ $p_i/w_i$
1	2	3	1.5
2	3	4	1.33
3	1	1	1.0
4	3	2	0.67

探索の流れ

(1) 根ノード P₀：LP 緩和を解く

整数条件を外した LP 緩和の最適解は、価値/重さの降順に詰め込んでいきます。

荷物1（重さ2）を全部詰める → 残り容量 2。
荷物2（重さ3）は 2/3 だけ詰める → 容量満杯。

$$\bar{x} = \left(1,\ \frac{2}{3},\ 0,\ 0\right),\quad \bar{z} = 3 + 4 \cdot \frac{2}{3} = \frac{17}{3} \approx 5.67$$

$x_2 = 2/3$ が小数 → $x_2$ で分枝

現在の暫定値：$z^* = -\infty$（まだ整数解なし）

         P₀  z̄=17/3
        /    \
    x₂=0    x₂=1
     P₁       P₂

(2) P₁（x₂=0）：LP 緩和を解く

$x_2 = 0$ に固定。残りの変数でLP緩和を解く。

荷物1（重さ2）→ 荷物3（重さ1）→ 荷物4（重さ3 のうち 1/3）

$$\bar{x} = \left(1,\ 0,\ 1,\ \frac{1}{3}\right),\quad \bar{z} = 3 + 1 + \frac{2}{3} = \frac{14}{3} \approx 4.67$$

$x_4 = 1/3$ が小数 → $x_4$ で分枝

         P₀  z̄=17/3
        /    \
    x₂=0    x₂=1
     P₁       P₂
   z̄=14/3
   /    \
 x₄=0  x₄=1
  P₃    P₄

(3) P₃（x₂=0, x₄=0）：LP 緩和を解く

$x_2=0, x_4=0$ に固定。残りは荷物1と荷物3のみ。

$$\bar{x} = \left(1,\ 0,\ 1,\ 0\right),\quad \bar{z} = 3 + 1 = 4$$

$\bar{x}$ が整数解 → 暫定値を更新：$z^* = 4$

         P₀  z̄=17/3
        /    \
    x₂=0    x₂=1
     P₁       P₂
   z̄=14/3
   /    \
 x₄=0  x₄=1
  P₃    P₄
 z*=4

(4) P₄（x₂=0, x₄=1）：LP 緩和を解く

$x_2=0, x_4=1$ に固定。容量3のうち荷物4で3消費。残り1。

$$\bar{x} = \left(\frac{1}{2},\ 0,\ 0,\ 1\right),\quad \bar{z} = \frac{3}{2} + 2 = \frac{7}{2} = 3.5$$

$\bar{z} = 3.5 \leq z^* = 4$ → 枝刈り（この後より深くしてもこれ以上改善できない→「LP緩和が暫定値を改善できない」）

         P₀  z̄=17/3
        /    \
    x₂=0    x₂=1
     P₁       P₂
   z̄=14/3
   /    \
 x₄=0  x₄=1
  P₃    P₄
 z*=4  枝刈り

(5) P₂（x₂=1）：LP 緩和を解く

$x_2=1$ に固定。容量1が余る。荷物1を 1/2 詰める。

$$\bar{x} = \left(\frac{1}{2},\ 1,\ 0,\ 0\right),\quad \bar{z} = \frac{3}{2} + 4 = \frac{11}{2} = 5.5$$

$\bar{z} = 5.5 > z^* = 4$ → まだ改善の余地あり → $x_1$ で分枝

              P₀  z̄=17/3
             /    \
         x₂=0   x₂=1
          P₁      P₂ z̄=5.5
        /    \   /    \
    x₄=0  x₄=1 x₁=0  x₁=1
     P₃    P₄   P₅    P₆
   z*=4  枝刈り

(6) P₅（x₂=1, x₁=0）：LP 緩和を解く

$x_1=0, x_2=1$ に固定。容量1が余る → 荷物3を詰められる。

$$\bar{x} = \left(0,\ 1,\ 1,\ 0\right),\quad \bar{z} = 4 + 1 = 5$$

整数解！ → 暫定値を更新：$z^* = 5$

              P₀  z̄=17/3
             /    \
         x₂=0   x₂=1
          P₁      P₂ z̄=5.5
        /    \   /    \
    x₄=0  x₄=1 x₁=0  x₁=1
     P₃    P₄   P₅    P₆
   z*=4  枝刈り z*=5

(7) P₆（x₂=1, x₁=1）：LP 緩和を解く

$x_1=1, x_2=1$ に固定。必要容量 $2+3=5 > 4$ → 実行不能 → 枝刈り

              P₀  z̄=17/3
             /    \
         x₂=0   x₂=1
          P₁      P₂ z̄=5.5
        /    \   /    \
    x₄=0  x₄=1 x₁=0  x₁=1
     P₃    P₄   P₅    P₆
   z*=4  枝刈り z*=5  枝刈り
                      (実行不能)

終了

すべてのノードが処理されました。

最適解：$x^* = (0,1,1,0)$、最適値 $z^* = 5$

ノード	下界	処理結果
P₀	5.67	x₂で分枝
P₁	4.67	x₄で分枝
P₃	4	整数解→ z*=4
P₄	3.5	枝刈り（≤z*）
P₂	5.5	x₁で分枝
P₅	5	整数解→ z*=5
P₆	-	実行不能→枝刈り

Pythonで確認する

LP 緩和を PuLP で解いて、各ノードの下界値を確認してみましょう。

import pulp

def solve_node(x1_fix=None, x2_fix=None, x3_fix=None, x4_fix=None):
    """変数を固定してナップサック LP 緩和を解く"""
    prob = pulp.LpProblem("knapsack", pulp.LpMaximize)

    def make_var(name, fix):
        if fix is not None:
            return pulp.LpVariable(name, lowBound=fix, upBound=fix)
        return pulp.LpVariable(name, lowBound=0, upBound=1)

    x1 = make_var("x1", x1_fix)
    x2 = make_var("x2", x2_fix)
    x3 = make_var("x3", x3_fix)
    x4 = make_var("x4", x4_fix)

    prob += 3*x1 + 4*x2 + x3 + 2*x4
    prob += 2*x1 + 3*x2 + x3 + 3*x4 <= 4

    status = prob.solve(pulp.PULP_CBC_CMD(msg=0))
    if pulp.LpStatus[prob.status] == 'Optimal':
        vals = [pulp.value(v) for v in [x1, x2, x3, x4]]
        return vals, pulp.value(prob.objective)
    return None, None

nodes = [
    ("P0（制約なし）",          {}),
    ("P1（x2=0）",              {"x2_fix": 0}),
    ("P3（x2=0, x4=0）",       {"x2_fix": 0, "x4_fix": 0}),
    ("P4（x2=0, x4=1）",       {"x2_fix": 0, "x4_fix": 1}),
    ("P2（x2=1）",              {"x2_fix": 1}),
    ("P5（x2=1, x1=0）",       {"x1_fix": 0, "x2_fix": 1}),
    ("P6（x2=1, x1=1）",       {"x1_fix": 1, "x2_fix": 1}),
]

for name, kwargs in nodes:
    sol, obj = solve_node(**kwargs)
    if sol is None:
        print(f"{name}: 実行不能")
    else:
        vals = [f"{v:.3f}" for v in sol]
        print(f"{name}: x={vals}, z={obj:.3f}")

P0（制約なし）:      x=['1.000', '0.667', '0.000', '0.000'], z=5.667
P1（x2=0）:          x=['1.000', '0.000', '1.000', '0.333'], z=4.667
P3（x2=0, x4=0）:   x=['1.000', '0.000', '1.000', '0.000'], z=4.000
P4（x2=0, x4=1）:   x=['0.500', '0.000', '0.000', '1.000'], z=3.500
P2（x2=1）:          x=['0.500', '1.000', '0.000', '0.000'], z=5.500
P5（x2=1, x1=0）:   x=['0.000', '1.000', '1.000', '0.000'], z=5.000
P6（x2=1, x1=1）:   実行不能

手計算の結果と一致しています。

探索順序の選択

理屈上は、分枝限定法では探索順序を選べます。

戦略	やること	特徴
深さ優先探索（DFS）	葉ノードまで一気に潜る	整数解が早く見つかりやすい。メモリ効率が良い
最良優先探索	下界値が最も良いノードを優先	枝刈りの効率が良い。メモリを多く使う
幅優先探索（BFS）	同じ深さのノードを順に処理	実用上使いにくい

実際のソルバー（Gurobi・CPLEX）は深さ優先と最良優先を組み合わせたハイブリッド戦略を使っているらしいです。

まとめ

分枝限定法は「分枝（問題を2分割）」と「限定（無駄な枝を刈る）」の繰り返し
分枝は「非整数の変数を選んで上下に丸める」という操作
限定は「LP 緩和が暫定値を改善できないなら枝刈り」「LP 実行不能なら枝刈り」「LP 解が整数なら暫定値更新」