この記事について
整数計画でモデリングをしていると「制約A または 制約Bのどちらかを満たせばよい」というケースに出くわすことがあります。普通の制約は AND（全て満たす）で扱われるので、OR を表現するには工夫が必要です。
この記事では、Big-M法 を使って 離接制約（Disjunctive Constraints） を表現する技法と、その応用例（スケジューリング・長方形詰込み）を紹介します。地味ですが、実務の定式化で最もよく使う道具のひとつかと思います。
離接制約（Disjunctive Constraints）とは
通常の最適化問題：
制約1 AND 制約2 AND ... AND 制約m をすべて満たす解を求める
これが離接制約になると：
制約1 OR 制約2 OR ... OR 制約m のうち少なくとも k 本を満たす
「m本のうち少なくとも k本を満たす」という選択的な制約です。
これは選択や順序付けなどの組合せ的な制約を表すときによく現れます。スケジューリングや配置問題では事実上避けて通れない概念です。
Big-M法による表現
最もシンプルな「2本のうち少なくとも1本を満たす」場合：
\sum_{j=1}^{n} a_{1j} x_j \leq b_1 \quad \vee \quad \sum_{j=1}^{n} a_{2j} x_j \leq b_2
これを整数計画として書きたい場合、補助2値変数 $y_1, y_2$ と十分大きな定数 $M$ を使って：
\begin{aligned}
\sum_{j=1}^{n} a_{1j} x_j &\leq b_1 + M(1 - y_1) \\
\sum_{j=1}^{n} a_{2j} x_j &\leq b_2 + M(1 - y_2) \\
y_1 + y_2 &= 1 \\
y_1, y_2 &\in \{0, 1\}
\end{aligned}
仕組み
- $y_1 = 1$ なら制約1は $\sum a_{1j} x_j \leq b_1 + 0 = b_1$ で有効化
- $y_1 = 0$ なら制約1は $\sum a_{1j} x_j \leq b_1 + M$ で実質的に無効化（$M$ が十分大きければ任意の解が満たす）
- $y_1 + y_2 = 1$ なので、ちょうど一方の制約が有効になる
「少なくとも k 本」に拡張するなら $y_1 + y_2 + \cdots + y_m \geq k$ にすればOKです。
Big-M の選び方
$M$ は 「左辺が取りうる最大値 − 右辺」より大きい 適当な値を選びます。
| Mの選び方 | 問題 |
|---|---|
| 小さすぎる | 有効解を切ってしまう |
| 大きすぎる | LP緩和が弱くなって計算が遅くなる |
| ちょうど良い | 実行可能領域は壊さず、LP緩和もタイト |
「とりあえず $M = 10^9$」のような極端に大きな値を使うと、ソルバーで数値的に不安定になり計算が遅くなることがあります。問題構造から導ける最小の Big-M を選ぶのが理想です。
応用：1機械スケジューリング問題
問題設定
- 1台の機械で $n$ 個の仕事を処理する
- 仕事 $i$ の処理時間 $p_i$、納期 $d_i$
- 同時に2つの仕事は処理できない、中断もできない
- 目的：納期遅れの合計 $\sum_i \max(s_i + p_i - d_i, 0)$ を最小化
変数
- $s_i$：仕事 $i$ の開始時刻（連続変数）
- $x_{ij}$：仕事 $i$ が仕事 $j$ に先行するなら 1、しないなら 0
非重複制約（離接制約）
「仕事 $i$ と $j$ は同時に処理できない」を式で書くと：
(s_i + p_i ≤ s_j) ∨ (s_j + p_j ≤ s_i)
つまり「$i$ が終わってから $j$ が始まる」 OR 「$j$ が終わってから $i$ が始まる」のどちらか。Big-M で表現すると：
s_i + p_i \leq s_j + M(1 - x_{ij})
x_{ij} + x_{ji} = 1
- $x_{ij} = 1$ なら $s_i + p_i \leq s_j$（$i$ が先）
- $x_{ij} = 0$ なら制約は実質無効化
目的関数の線形化
$\max(s_i + p_i - d_i, 0)$ は非線形（区分関数）です。これを線形化するために補助変数 $t_i \geq 0$ を導入
\begin{aligned}
\text{minimize} \quad & \sum_{i=1}^{n} t_i \\
\text{subject to} \quad & s_i + p_i - d_i \leq t_i \\
& t_i \geq 0
\end{aligned}
- 納期遅れがある場合（$s_i + p_i - d_i > 0$）：$t_i$ がそれを上から押さえる
- 遅れがない場合（$s_i + p_i - d_i \leq 0$）：$t_i \geq 0$ の自由度で $t_i = 0$ にできる
最小化されるので、$t_i$ は常に $\max(s_i + p_i - d_i, 0)$ ピッタリ になります。
Pythonでの実装
import pulp
# データ
n = 4
p = [3, 2, 4, 1] # 処理時間
d = [5, 7, 8, 4] # 納期
M = sum(p) + max(d) + 10 # Big-M
prob = pulp.LpProblem("1mach_sched", pulp.LpMinimize)
s = [pulp.LpVariable(f"s{i}", lowBound=0) for i in range(n)]
t = [pulp.LpVariable(f"t{i}", lowBound=0) for i in range(n)]
x = [[pulp.LpVariable(f"x{i}_{j}", cat='Binary') if i != j else None
for j in range(n)] for i in range(n)]
# 目的関数：納期遅れの合計
prob += pulp.lpSum(t)
# 納期遅れ制約
for i in range(n):
prob += s[i] + p[i] - d[i] <= t[i]
# 非重複制約（Big-M）
for i in range(n):
for j in range(n):
if i != j:
prob += s[i] + p[i] <= s[j] + M * (1 - x[i][j])
# 順序の対称性：x_ij + x_ji = 1
for i in range(n):
for j in range(i+1, n):
prob += x[i][j] + x[j][i] == 1
prob.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"納期遅れ合計 = {pulp.value(prob.objective):.0f}")
order = sorted(range(n), key=lambda i: pulp.value(s[i]))
for i in order:
si, ti = pulp.value(s[i]), pulp.value(t[i])
print(f" 仕事{i}: 開始={si:.0f}, 終了={si+p[i]:.0f}, 納期={d[i]}, 遅れ={ti:.0f}")
実行結果例：
納期遅れ合計 = 2
仕事3: 開始=0, 終了=1, 納期=4, 遅れ=0
仕事0: 開始=1, 終了=4, 納期=5, 遅れ=0
仕事1: 開始=4, 終了=6, 納期=7, 遅れ=0
仕事2: 開始=6, 終了=10, 納期=8, 遅れ=2
仕事3 → 0 → 1 → 2 の順で処理することで納期遅れ合計が 2（ただし仕事2が2遅れる）程度に抑えられます。
Big-M法を使うときの注意点
Big-M は便利ですが、注意点も少なくないです。
① LP緩和が弱くなる
Big-M を入れた制約は LP緩和では「ほぼ自由な値が許される」状態になるので、下界が緩く なり分枝限定法の効率が落ちます。
② 数値的に不安定になる
$M = 10^{12}$ のような巨大な値を使うとソルバー内部で丸め誤差が発生しやすく、「実行不能」と誤判定されたり、整数性が崩れたりします。
③ 代替手段：Indicator Constraint
Gurobi や CPLEX には Indicator Constraint という機能があります。
# Gurobi の例
model.addGenConstrIndicator(y, True, expr <= bound)
これは「$y = 1$ なら制約有効、$y = 0$ なら無視」を Big-M 不要で内部的に処理してくれる機能です。Big-M を選ぶ手間が省けて数値的にも安定します。可能なら積極的に使うと良いかと思います。
まとめ
- 離接制約：「制約A または 制約B」を表現したいとき
- Big-M法：補助2値変数 $y$ と十分大きな $M$ で「片方の制約を無効化」
- $M$ は「十分大きい範囲で最小」が理想
- 1機械スケジューリング：仕事ペアの順序を $x_{ij}$、納期遅れを補助変数 $t_i$ で線形化
- Indicator Constraint が使えるなら Big-M より好ましい（Big-M使いがちなんだけどね）