この記事について

前回は分枝限定法を説明しました。今回は整数計画問題のもう一つの重要な厳密解法、切除平面法（Cutting Plane Method） を説明します。

分枝限定法が「問題を小さく分割して解く」アプローチだとすれば、切除平面法は「LP の実行可能領域に制約を追加して整数解に近づける」アプローチです。正直、分枝限定法より少し難しい概念ですが、実際のソルバーが内部でよく使われる重要な技術なので、雰囲気だけでも掴んでもらえると幸いです。

切除平面法のアイデア

凸包という考え方

整数計画問題の実行可能解（整数格子点）をすべて含む**最小の凸包（Convex Hull）**は、凸多面体になります。これは線形計画問題で表現できます。

もし凸包の不等式表現を事前に知っていれば、LP を解くだけで整数最適解が直接求まります。しかし現実には凸包を事前に求めることは困難ですし、その不等式の数も膨大となります。

切除平面（Cutting Plane）

そこで切除平面法では、以下の手順を繰り返します。

① LP 緩和を解く
② LP 最適解 $\bar{x}$ が整数解でない場合、$\bar{x}$ を除去する制約条件（カット）を追加する
③ ただし、整数計画問題の実行可能解（整数格子点）はカットしない
④ LP を再度解く → ①に戻る

カットを追加するたびに LP の実行可能領域が削られ、最適解が整数格子点に向かって動いていくイメージです。図は後の具体例（$2x_1+3x_2 \leq 6$, $-2x_1+x_2 \leq 0$）と同じ問題で、LP 最適解 $(3/4, 3/2)$ をカット $x_2 \leq 1$ で除去すると、新しい最適解が整数解 $(1, 1)$ になる様子を示しています。

妥当不等式とカット

切除平面法で使う制約条件を整理します。

妥当不等式（Valid Inequality）：すべての整数実行可能解が満たす不等式。

切除平面（カット）：妥当不等式であり、かつ現在の LP 最適解（非整数）を除去する不等式。

	性質	意味
妥当不等式	整数実行可能解を切除しない	MIPの最適解候補を失わない
切除平面	現在の LP 最適解を切除する	LP の実行可能領域を縮小して下界を改善

Gomory の切除平面法

最もシンプルなカット生成法が Gomory の切除平面法 です。LP の最適基底解から自動的にカットを導出できます。

カットの導出手順

LP 緩和の最適辞書（シンプレックス法の基底表現）において、ある基底変数 $x_i$ の行が：

$$x_i = \beta_i - (\alpha_{m+1} x_{m+1} + \alpha_{m+2} x_{m+2} + \cdots + \alpha_n x_n)$$

と書けるとします。$\beta_i$ が整数でなければ（整数条件を満たさない）、以下の Gomory カットが得られます。

手順1： 各係数を切り下げ（床関数 $\lfloor \cdot \rfloor$）します。

$$\lfloor \alpha_{m+1} \rfloor x_{m+1} + \lfloor \alpha_{m+2} \rfloor x_{m+2} + \cdots + \lfloor \alpha_n \rfloor x_n \leq \lfloor \beta_i \rfloor$$

手順2： 左辺は整数値なので、右辺も整数に切り下げてよい（これが妥当不等式であることの根拠）。

このカットは現在の LP 最適解を切除しつつ、整数実行可能解はすべて満たします。

具体例：手計算で Gomory カットを導出

以下の整数計画問題を使います。

\text{maximize} \quad x_2

\text{subject to} \quad 2x_1 + 3x_2 \leq 6, \quad -2x_1 + x_2 \leq 0, \quad x_1, x_2 \in \mathbb{Z}_+

ステップ1：LP 緩和を解く

スラック変数 $x_3, x_4$ を導入して標準形にします。

$$2x_1 + 3x_2 + x_3 = 6, \quad -2x_1 + x_2 + x_4 = 0$$

シンプレックス法で解くと、最適辞書は以下のようになります。

$$z = -\frac{3}{2} + \frac{1}{4}x_3 + \frac{1}{4}x_4 \quad (1)$$

$$x_1 = \frac{3}{4} - \frac{1}{8}x_3 + \frac{3}{8}x_4 \quad (2)$$

$$x_2 = \frac{3}{2} - \frac{1}{4}x_3 - \frac{1}{4}x_4 \quad (3)$$

LP 最適解：$\bar{x}_1 = 3/4,\ \bar{x}_2 = 3/2$、最適値 $\bar{z} = 3/2$

$x_2 = 3/2$ は整数でないので、式(3)を使って Gomory カットを導出します。

ステップ2：Gomory カットを生成

式(3)を書き直します：

$$x_2 + \frac{1}{4}x_3 + \frac{1}{4}x_4 = \frac{3}{2} \quad (3)'$$

各係数を切り下げ：

$$x_2 + \lfloor \frac{1}{4} \rfloor x_3 + \lfloor \frac{1}{4} \rfloor x_4 \leq \lfloor \frac{3}{2} \rfloor$$

$$\Rightarrow \quad x_2 + 0 \cdot x_3 + 0 \cdot x_4 \leq 1$$

$$\Rightarrow \quad \boxed{x_2 \leq 1} \quad (4)$$

これが Gomory カットです。現在の LP 最適解 $x_2 = 3/2$ はこのカットを満たさない（除去される）一方で、整数解（$x_2 = 0$ や $x_2 = 1$）はすべて満たします。

ステップ3：カットを追加して LP を再解

$x_2 \leq 1$ を追加した LP の上界値は $x_2 = 1$ になります。
整数実行可能解として $(x_1, x_2) = (1, 1)$ が存在し、$x_2 = 1$ を達成します。
LP 上界値（1）＝整数解の値（1）なので、最適解が確定します。

$$\text{最適解：} x_1 = 1,\ x_2 = 1,\ \text{最適値} = 1$$

Python で確認する

PuLP を使って LP 緩和 → Gomory カット追加 → 再求解の流れを確認します。

import pulp

# ① LP 緩和（整数条件なし）
lp = pulp.LpProblem("LP", pulp.LpMaximize)
x1 = pulp.LpVariable("x1", lowBound=0)
x2 = pulp.LpVariable("x2", lowBound=0)
lp += x2
lp += 2*x1 + 3*x2 <= 6
lp += -2*x1 + x2 <= 0
lp.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"LP最適解: x1={pulp.value(x1):.3f}, x2={pulp.value(x2):.3f}")
print(f"LP最適値（上界）: {pulp.value(lp.objective):.3f}")
print()

# ② Gomory カット x2 ≤ 1 を追加
lp2 = pulp.LpProblem("LP_with_cut", pulp.LpMaximize)
x1b = pulp.LpVariable("x1", lowBound=0)
x2b = pulp.LpVariable("x2", lowBound=0)
lp2 += x2b
lp2 += 2*x1b + 3*x2b <= 6
lp2 += -2*x1b + x2b <= 0
lp2 += x2b <= 1        # Gomory カット
lp2.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"カット後LP最適値（上界）: {pulp.value(lp2.objective):.3f}")
print()

# ③ MIP（整数条件あり）で検証
ip = pulp.LpProblem("IP", pulp.LpMaximize)
x1c = pulp.LpVariable("x1", lowBound=0, cat='Integer')
x2c = pulp.LpVariable("x2", lowBound=0, cat='Integer')
ip += x2c
ip += 2*x1c + 3*x2c <= 6
ip += -2*x1c + x2c <= 0
ip.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"MIP最適解: x1={pulp.value(x1c):.0f}, x2={pulp.value(x2c):.0f}")
print(f"MIP最適値: {pulp.value(ip.objective):.0f}")

LP最適解: x1=0.750, x2=1.500
LP最適値（上界）: 1.500

カット後LP最適値（上界）: 1.000

MIP最適解: x1=1, x2=1
MIP最適値: 1

LP 上界値が 1.5 → 1.0 に改善され、MIP 最適値と一致しました。

Gomory の切除平面法の性質

有限終了性

任意の整数計画問題に対して、Gomory カットを繰り返し適用すると有限回で整数最適解に到達することが証明されています（Gomory, 1958）。ただし実際には収束が遅くなることもあり、単独では実用的ではないことが多いです。

カットの強さ

Gomory カットは理論的に正しいカットですが、問題構造を活用した強いカット（例：Clique カット、Cover カット、Lift-and-Project カット）の方が実際には効果的なことが多いです。実際のソルバーは複数のカット生成戦略を組み合わせて使っています。

まとめ

切除平面法 は LP 実行可能領域に 妥当不等式（カット） を追加して整数解に近づける手法
Gomory カットはシンプレックス法の最適辞書から自動的に生成できる汎用的なカット
カットを追加するたびに LP 上界値が改善され、整数最適値に収束する
単体では収束が遅いことがあるため、実際のソルバーでは分枝限定法と組み合わせた分枝カット法が使われる

参考にした記事や本、論文等

R. E. Gomory, "Outline of an Algorithm for Integer Solutions to Linear Programs," Bulletin of the American Mathematical Society, vol. 64, pp. 275-278, 1958.
L. A. Wolsey, Integer Programming, John Wiley & Sons, 1998.