この記事について
この記事では、整数計画問題を解くための土台となる考え方、つまり「LP緩和と上界・下界で最適値を挟み込む」仕組みを説明します。続く記事で説明する分枝限定法・切除平面法はどちらもこの考え方がベースなので、まずここを押さえておくと後の記事が読みやすくなるかと思います。
線形計画（LP）と整数計画（MIP）の違い
まず2つの問題を整理します。
線形計画問題（LP: Linear Program）
線形の制約条件のもとで線形の目的関数を最小化（最大化）する問題。変数は連続値を取れます。
整数計画問題（MIP: Mixed Integer Program）
変数に整数条件が付いた最適化問題。変数が整数格子点に限定されるため、解が難しくなります。
同じ問題に整数条件を付けるかどうかで結果が変わります。
\text{minimize} \quad 5x + 4y
\text{subject to} \quad 6x + 4y \geq 24, \quad x + 2y \geq 6, \quad x, y \geq 0
import pulp
# LP（連続変数）
lp = pulp.LpProblem("LP", pulp.LpMinimize)
x_lp = pulp.LpVariable("x", lowBound=0)
y_lp = pulp.LpVariable("y", lowBound=0)
lp += 5*x_lp + 4*y_lp
lp += 6*x_lp + 4*y_lp >= 24
lp += x_lp + 2*y_lp >= 6
lp.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"LP最適解: x={pulp.value(x_lp):.2f}, y={pulp.value(y_lp):.2f}")
print(f"LP最適値（下界）: {pulp.value(lp.objective):.2f}")
# MIP（整数変数）
mip = pulp.LpProblem("MIP", pulp.LpMinimize)
x_ip = pulp.LpVariable("x", lowBound=0, cat='Integer')
y_ip = pulp.LpVariable("y", lowBound=0, cat='Integer')
mip += 5*x_ip + 4*y_ip
mip += 6*x_ip + 4*y_ip >= 24
mip += x_ip + 2*y_ip >= 6
mip.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"MIP最適解: x={pulp.value(x_ip):.0f}, y={pulp.value(y_ip):.0f}")
print(f"MIP最適値: {pulp.value(mip.objective):.0f}")
LP最適解: x=3.00, y=1.50
LP最適値（下界）: 21.00
MIP最適解: x=2, y=3.
MIP最適値: 22
LP最適解 $(3, 1.5)$ の $y=1.5$ は整数でないため MIP の実行可能解にはなりません。MIP では整数格子点の中から最良の $(2, 3)$ を選ぶ必要があり、最適値が 21 から 22 に悪化しています。
LP緩和問題とは
整数計画問題から整数条件だけを取り除いた問題を LP緩和問題 と呼びます。
MIP（原問題）:
minimize cᵀx
s.t. Ax ≥ b
x ∈ ℤ₊ ← 整数条件
LP緩和問題:
minimize cᵀx
s.t. Ax ≥ b
x ≥ 0 ← 整数条件を除去
LP緩和の実行可能領域はMIPの実行可能領域を包含しています（整数条件を緩めたので、より多くの点が許容される）。
LP緩和の3つの重要な性質
この包含関係から、以下の3つの性質が成り立ちます（最小化の場合）。
(1) LP最適値 ≤ MIP最適値
LP緩和の実行可能領域がMIPより広い → LP最適値はMIP最適値の下界になります。
(2) LP最適解が整数解ならMIPの最適解
運良くLP緩和の最適解が全変数で整数値になれば、それがそのままMIPの最適解です。
(3) LP緩和が実行不能ならMIPも実行不能
MIPの実行可能領域 ⊆ LPの実行可能領域なので、LPが解けなければMIPも解けません。
上界と下界で最適値を挟み込む
整数計画問題を解く際の基本戦略は、上界値と下界値で最適値を挟み込むことです。
| 種別 | 得られ方 | 最小化における意味 |
|---|---|---|
| 下界値（Lower Bound） | LP緩和の最適値 | 最適値はこれ以上になる |
| 上界値（Upper Bound、暫定値） | 見つかった実行可能整数解の目的関数値 | 最適値はこれ以下になる |
目的関数値
↑
│ 上界値（暫定解から得る） ← 下げたい
│
│ MIPの最適値（ここに真の答えがある）
│
│ 下界値（LP緩和から得る） ← 上げたい
アルゴリズムが進むにつれて：
- 下界値は単調に増加（LP緩和を繰り返し強化する）
- 上界値は単調に減少（より良い整数解が見つかるたびに更新）
- 上界値 ＝ 下界値 になった時点で最適解が確定
MIPギャップ（MIP Gap）
実務では上界値と下界値がぴったり一致するまで待たないことも多いです。多くのソルバーでは MIPギャップ（上界と下界の相対誤差）を閾値として指定し、一定の精度で早期終了します。
\text{MIP Gap} = \frac{|\text{上界値} - \text{下界値}|}{|\text{上界値}|} \times 100\%
Gurobi では以下のように設定します。
import gurobipy as gp
model = gp.Model()
# ... 問題定義 ...
model.setParam('MIPGap', 0.01) # 1% 以内で終了
model.setParam('TimeLimit', 60) # または 60 秒で打ち切り
model.optimize()
print(f"上界値: {model.ObjVal:.2f}")
print(f"下界値: {model.ObjBound:.2f}")
print(f"MIPGap: {model.MIPGap * 100:.2f}%")
「厳密な最適解でなくても 1% 以内の精度で十分」という実務の判断に使えます。
まとめ
- LP緩和は整数条件を外した問題で、最適値は元の MIP の下界になる
- 実行可能な整数解が得られるたびに 上界値（暫定値） を更新する
- 「下界を上げ、上界を下げて最適値を挟み込む」のが MIP 求解の基本戦略
- MIPギャップを設定することで、「十分に良い解」を効率的に取得できる
- 分枝限定法・切除平面法は、この挟み込み戦略を具体化したアルゴリズム
次の記事では 分枝限定法 を手計算で体感してみます。