整数計画とは・LP緩和

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

📎 前提：線形計画の標準形と幾何・最適化問題の分類　|　関連：分枝限定法

要点（BLUF）

整数計画（IP）は決定変数が整数（特に 0/1）に限られる最適化。離散ゆえ一般に難しい。
LP 緩和＝整数制約を外して連続 LP として解く近似。最大化なら上界を与える。
緩和解と整数解の差を 整数ギャップという。このギャップが分枝限定（分枝限定法）の枝刈りに効く。

概念 ── 整数制約が難しさを生む

整数計画は LP に「変数は整数」という条件を加えただけ：

\max\ c^\top x \quad \text{s.t.}\quad Ax \le b,\ x \ge 0,\ x \in \mathbb{Z}^n

0/1 変数だけなら 0-1 整数計画、整数と連続が混じれば 混合整数計画（MILP）。条件が増えただけなのに、LP（多項式時間）から一気に NP 困難（計算複雑性とNP困難の地図）へ跳ね上がる。理由は、整数点が 格子状にとびとびで、LP のような「頂点に最適がある・凸だから局所＝大域」という便利な構造が崩れるから。

LP 緩和 ── 整数条件を一旦外す

整数制約 $x \in \mathbb{Z}^n$ を $x \in \mathbb{R}^n$ に緩めたものが LP 緩和：

\max\ c^\top x \quad \text{s.t.}\quad Ax \le b,\ x \ge 0

整数の実行可能解は LP 緩和の実行可能領域に 含まれる（部分集合）。だから：

z_{\text{LP}}^\star \ \ge\ z_{\text{IP}}^\star \quad (\text{最大化のとき})

LP 緩和の最適値は、整数最適値の上界になる。緩和は「制約を緩めた」から、達成できる目的値はより良く（大きく）なる。この上界が、最適解探索の「ここより良くはならない」という天井になる。

graph TD
  A["整数計画 IP (とびとびの格子点)"] --> B["整数制約を外す"]
  B --> C["LP緩和 (連続・凸多面体)"]
  C --> D["LP最適 = IP最適の上界"]
  D --> E{"LP解が整数か"}
  E -->|"はい"| F["それが整数最適 (運が良い)"]
  E -->|"いいえ"| G["分枝限定/切除平面で詰める"]

整数ギャップ ── 緩和はどれだけ甘いか

$z_{\text{LP}}^\star - z_{\text{IP}}^\star$ を 整数ギャップという。ギャップが小さいほど LP 緩和は良い近似で、探索が速い。全ユニモジュラな係数行列（割当・最短路・最大流など、ネットワーク最適化章目次）では、LP 緩和の頂点が自動的に整数になり ギャップ0（緩和を解くだけで整数最適）。これがネットワーク問題が「整数なのに楽に解ける」理由。

Pythonで緩和と整数解を比べる

0/1 ナップサック：価値 $[60,100,120]$ 、重さ $[10,20,30]$ 、容量 50。LP 緩和は荷物を分割して詰められるが、0/1 では入れるか入れないか。

import pulp

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

def knapsack(integer):
    prob = pulp.LpProblem("knap", pulp.LpMaximize)
    cat = "Binary" if integer else "Continuous"   # 0/1 か 連続[0,1] か
    x = [pulp.LpVariable(f"x{i}", lowBound=0, upBound=1, cat=cat) for i in range(3)]
    prob += pulp.lpSum(values[i]*x[i] for i in range(3))            # 価値最大化
    prob += pulp.lpSum(weights[i]*x[i] for i in range(3)) <= capacity  # 容量制約
    prob.solve(pulp.PULP_CBC_CMD(msg=0))
    return pulp.value(prob.objective), [round(x[i].value(), 3) for i in range(3)]

lp_obj, lp_x = knapsack(integer=False)
ip_obj, ip_x = knapsack(integer=True)
print(f"LP緩和  最適値={lp_obj:.1f}, x={lp_x}")
print(f"0/1整数 最適値={ip_obj:.1f}, x={ip_x}")
print(f"整数ギャップ = {lp_obj - ip_obj:.1f}")

実行結果：

LP緩和  最適値=240.0, x=[1.0, 1.0, 0.667]
0/1整数 最適値=220.0, x=[0.0, 1.0, 1.0]
整数ギャップ = 20.0

LP 緩和は3番目の荷物を $0.667$ 個だけ詰めて価値 240 を達成 ── だが現実には荷物を $2/3$ にはできない。0/1 では荷物2と3を入れて価値 220、重さちょうど 50。緩和の 240 は「これ以上は無理」という上界で、整数最適 220 との差 20 が整数ギャップ。緩和解が分数 $x_3=0.667$ になった変数 $x_3$ で「分枝」するのが次のステップ（分枝限定法）。

数式の直観的意味

LP 緩和が上界を与えるのは「実行可能領域を広げれば最適値は良くなる（悪くならない）」という単調性の帰結。整数点の集合 $\subseteq$ 凸多面体だから、より広い集合での最大は元の最大以上。重要なのは、この上界が 探索の証明書になること：もし現在見つけた整数解の値が LP 緩和の上界に等しければ、それ以上良い整数解は存在しないと証明できる。逆に LP 緩和解がたまたま整数なら、それがそのまま整数最適。緩和は「楽な問題で難しい問題を挟み込む」という最適化の基本戦術で、ラグランジュ緩和や凸緩和（凸最適化問題と双対理論）にも通じる。

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

LP 緩和解を四捨五入しても最適とは限らない（実行不能になることすらある）。 $x_3=0.667$ を $1$ に丸めると容量超過。
緩和は上界（最大化）／下界（最小化）。向きを取り違えない。
ギャップ0の特殊構造を知っておく：全ユニモジュラ（ネットワーク）なら緩和＝整数最適。
0/1 変数が増えると、緩和は速くても整数解探索は指数的に膨らみ得る（計算複雑性とNP困難の地図）。