定式化の技法｜数理最適化

← 数理最適化一覧

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

📎 前提：モデリングの作法・整数計画とは・LP緩和　|　関連：スケジューリング・配送のモデル化

要点（BLUF）

現実の 論理条件（「もし〜なら」「どちらか一方」「固定費用」）は、0/1 変数とビッグMで線形制約に翻訳できる。
ビッグM法：大きな定数 $M$ で、バイナリ変数が0/1のとき制約を有効化／無効化する。
$M$ は 必要十分に大きく、しかし大きすぎない値に取る（緩和が緩み、数値不安定になるため）。

概念 ── 論理を線形に翻訳する

整数計画（整数計画と組合せ最適化章目次）の強みは、連続変数では書けない 論理条件を 0/1 変数で表せること。鍵は「条件が成立するときだけ効く制約」を、バイナリ変数 $y$ と大きな定数 $M$ で作る ビッグM法。

代表的な定式化パターン

固定費用（fixed charge）

「生産するなら固定費 $f$ がかかる」。 $y=1$ なら生産可、 $y=0$ なら $x=0$ を強制：

x \le M\,y, \qquad y \in \{0,1\}, \qquad \text{目的に } -f\,y \text{ を加える}

$y=0$ なら $x\le0$ で生産ゼロ、 $y=1$ なら $x\le M$ （実質上限なし）で固定費 $f$ を払う。

either-or（どちらか一方）制約

「制約A または制約B の少なくとも一方を満たす」。バイナリ $y$ で切り替える：

a_1^\top x \le b_1 + M\,y, \qquad a_2^\top x \le b_2 + M(1-y)

$y=0$ なら制約Aが有効（Bは $M$ で緩和され無効）、 $y=1$ なら逆。

含意（if-then）

「 $x>0$ ならば $z\ge d$ 」のような含意は、 $x \le M y$ と $z \ge d - M(1-y)$ を組み合わせて表す。論理の「ならば」を2本の線形制約に分解する。

graph TD
  A["現実の論理条件"] --> B["0/1変数 y を導入"]
  B --> C["固定費用: x <= M*y"]
  B --> D["either-or: 片方をM*yで緩和"]
  B --> E["if-then: 含意をM*(1-y)で表現"]
  C --> F["線形な整数計画(MILP)"]
  D --> F
  E --> F

Pythonで固定費用モデルを解く

製品A・Bの利益は $40,30$ ／個。だが生産するには固定費 $150,100$ がかかる。機械時間 $2x_A+x_B\le120$ 、材料 $x_A+x_B\le100$ 。固定費を引いた 純利益を最大化する。

import pulp

p = [40, 30]      # 単位利益
f = [150, 100]    # 固定費(生産する場合のみ)
M = 100           # ビッグM (生産量の上限の目安)

prob = pulp.LpProblem("fixed_charge", pulp.LpMaximize)
x = [pulp.LpVariable(f"x{i}", lowBound=0) for i in range(2)]   # 生産量
y = [pulp.LpVariable(f"y{i}", cat="Binary") for i in range(2)] # 生産するか

prob += pulp.lpSum(p[i]*x[i] for i in range(2)) - pulp.lpSum(f[i]*y[i] for i in range(2))
prob += 2*x[0] + x[1] <= 120     # 機械時間
prob += x[0] + x[1] <= 100       # 材料
for i in range(2):
    prob += x[i] <= M * y[i]     # ビッグM: x>0 なら y=1(固定費発生)
prob.solve(pulp.PULP_CBC_CMD(msg=0))

print(f"純利益 = {pulp.value(prob.objective):.0f}")
print(f"生産量 x = {[x[i].value() for i in range(2)]}")
print(f"生産フラグ y = {[y[i].value() for i in range(2)]}")

実行結果：

純利益 = 2950
生産量 x = [20.0, 80.0]
生産フラグ y = [1.0, 1.0]

両製品を生産（ $y=[1,1]$ ）し、 $x=(20,80)$ 。粗利益 $40\cdot20+30\cdot80=3200$ から固定費 $150+100=250$ を引いて純利益 2950。ビッグM制約 $x_i\le100\,y_i$ が「生産量が正なら $y_i=1$ が強制され固定費を払う」という論理を正しく表現している。もし固定費が高すぎれば、片方を $y=0$ （生産せず固定費回避）にする解が選ばれる。

数式の直観的意味

ビッグM法の本質は「バイナリ変数で制約を オン/オフするスイッチ」を作ること。 $M$ は「制約を無効化するのに十分大きい」値で、 $y=1$ のとき $b+My$ が事実上無限大になり制約が消える。注意点は、 $M$ が 大きすぎると LP 緩和（整数計画とは・LP緩和）が緩むこと：緩和の上界が甘くなり、分枝限定（分枝限定法）の枝刈りが効かず遅くなる。さらに数値計算上も、巨大な $M$ は丸め誤差で「ほぼ0の $y$ 」を許してしまう。だから $M$ は 問題から導かれる最小の妥当な上界（ここでは生産量の物理的上限）に取るのが鉄則。可能なら、ビッグMを使わない強い定式化（凸包に近い定式化・指示制約）が望ましい。良い定式化は、同じ問題でも解く速さを桁で変える ── モデリングは「解けるか」だけでなく「速く解けるか」を決める。

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

$M$ を無闇に大きくしない：緩和が緩み、分枝限定が遅くなり、数値不安定になる。問題固有の上界を使う。
「 $x>0$ ならば $y=1$ 」は片側のみ強制： $x\le My$ は $x>0\Rightarrow y=1$ を保証するが、 $y=1$ でも $x=0$ はあり得る（固定費だけ払う無駄解は目的が排除する）。
厳密な不等式 $x>0$ は書けない：MILP は閉じた不等式のみ。 $x \ge \epsilon\,y$ など微小量で近似する場合がある。
論理制約が増えると非凸性（組合せ）が増し、解くのが難しくなる。必要最小限に。