切除平面法｜数理最適化

🎓 レベル：発展　|　重要度：B（標準）

📎 前提：整数計画とは・LP緩和・分枝限定法　|　関連：代表的な組合せ問題

要点（BLUF）

切除平面法は 有効不等式（カット） を追加して LP 緩和を締め、分数解を削っていく。
カットは 整数解は1つも切らず、分数の LP 最適だけを切る超平面。
Gomory カット・カバー不等式などがあり、現代ソルバーは分枝と融合した 分枝カットで使う。

概念 ── 緩和を「削って」整数解に近づける

LP 緩和の最適は分数になりがち（整数計画とは・LP緩和）。分枝限定（分枝限定法）が「分割」で攻めるのに対し、切除平面法は 緩和の領域そのものを削る。狙いは、整数点をすべて含んだまま、分数の LP 最適頂点を実行可能領域から追い出すこと。理想的には、整数点の凸包（整数多面体）まで削り切れれば、LP を解くだけで整数最適が出る。

graph LR
  A["LP緩和の凸多面体 (分数頂点を含む)"] --> B["有効不等式(カット)を追加"]
  B --> C["分数頂点だけ削れる / 整数点は全て残る"]
  C --> D["LP緩和が締まり 上界が下がる"]
  D --> E["整数多面体に近づく"]

有効不等式（valid inequality）とは

すべての整数実行可能解 $x$ が満たすが、現在の分数 LP 最適 $x^\star$ は破る不等式 $\alpha^\top x \le \beta$ を カットという。条件は2つ：

妥当性：全整数解で $\alpha^\top x \le \beta$ （整数解を1つも切らない）。
分離性： $\alpha^\top x^\star > \beta$ （今の分数解を切り落とす）。

これを追加して LP を解き直すと、上界が下がる。整数解は無傷なので最適性は保たれる。

Gomory 分数カット

連続変数の純整数計画に対し、シンプレックスの最終辞書（基底解）から 機械的にカットを生成できるのが Gomory カット。基底変数の行 $x_B = \bar b - \sum \bar a_j x_j$ で $\bar b$ が分数のとき、小数部 $f_0 = \bar b - \lfloor \bar b \rfloor$ を使って

\sum_j f_j \, x_j \ \ge\ f_0, \qquad f_j = \bar a_j - \lfloor \bar a_j \rfloor

が全整数解で成り立つ（妥当）が、現在の分数解（非基底 $x_j=0$ ）では $0 \ge f_0 > 0$ となり破られる（分離）。Gomory は有限回で整数最適に到達することが理論的に示されているが、単独では収束が遅く、実務は分枝と併用する。

カバー不等式（ナップサックの例）

0/1 ナップサックでは構造を使った強いカットが作れる。重さの合計が容量を超える品目集合 $C$ （カバー）について、全部は入らないので

\sum_{i \in C} x_i \ \le\ |C| - 1

が全整数解で成立する。冒頭のナップサック（重さ $[10,20,30]$ 、容量 50）では $C=\{1,2,3\}$ の合計が $60>50$ なので、 $x_1+x_2+x_3 \le 2$ が有効不等式。

Pythonでカットが緩和を締めるのを見る

LP 緩和にカバー不等式を1本足すだけで、上界が整数最適まで一気に締まる。

import pulp
values = [60, 100, 120]; weights = [10, 20, 30]; capacity = 50

def knap_lp(extra_cut=False):
    p = pulp.LpProblem("k", pulp.LpMaximize)
    x = [pulp.LpVariable(f"x{i}", lowBound=0, upBound=1, cat="Continuous") for i in range(3)]
    p += pulp.lpSum(values[i]*x[i] for i in range(3))               # 価値最大化
    p += pulp.lpSum(weights[i]*x[i] for i in range(3)) <= capacity  # 容量
    if extra_cut:
        # カバー不等式: {1,2,3}は重さ合計60>50 -> どれか1つは入らない
        p += pulp.lpSum(x) <= 2
    p.solve(pulp.PULP_CBC_CMD(msg=0))
    return pulp.value(p.objective), [round(x[i].value(), 3) for i in range(3)]

o0, x0 = knap_lp(extra_cut=False)
o1, x1 = knap_lp(extra_cut=True)
print(f"カット前 LP緩和: 値={o0:.1f}, x={x0}")
print(f"カット後 LP緩和: 値={o1:.1f}, x={x1}")

実行結果：

カット前 LP緩和: 値=240.0, x=[1.0, 1.0, 0.667]
カット後 LP緩和: 値=220.0, x=[0.0, 1.0, 1.0]

カット前は分数解で上界 240。カバー不等式 $x_1+x_2+x_3\le2$ を1本足すと、LP 緩和の最適が 整数解 $[0,1,1]$ になり、値も整数最適 220 まで締まった。たった1本の良いカットが、整数ギャップ（整数計画とは・LP緩和）を丸ごと閉じることすらある。これが切除平面の威力。

数式の直観的意味

カットは「整数点の凸包（整数多面体）の面（facet）」を1枚ずつ復元していく作業。LP 緩和の多面体は整数多面体を覆う緩い容れ物で、その余分な角（分数頂点）をカットで削る。理想は整数多面体そのものまで削ること ── そうなれば LP を解くだけで整数最適。だが整数多面体の面の数は一般に指数的なので、全部を最初から書けない。そこで「今の分数解を切る面だけ」をその都度生成する（分離問題を解く）。分枝限定（領域を分割）と切除平面（領域を削る）は相補的で、両者を組み合わせた分枝カットが現代 MILP の標準。

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

カットは整数解を1つも切ってはいけない（妥当性）。妥当でない不等式を足すと最適解を失う。
Gomory カット単独は収束が遅い。数値誤差にも弱い。実務は強い構造的カット（カバー・クリーク等）＋分枝。
カットを足しすぎると LP が重くなる。「効くカットを選んで足す」管理が要る。
カバー不等式は 0/1 ナップサック型の構造があるとき有効。一般問題には別系統のカットが要る。