この記事について
LPは知っているけど、整数計画（IP・MIP）になると「どう変数を作ればいいのか分からない」「論理制約はどう書くのか」という疑問が出てきます。いろいろ勉強すると、整数計画は単なる「変数に整数条件を付けたLP」というより、離散的な状態をモデル化する特殊な記法 だと考えると見え方が変わってきます。
この記事では、整数計画の基本モデリングテクニックとして、2値変数の使い方・論理制約・固定費用付き目的関数 を整理します。次の記事以降のBig-M法や非線形の線形化の土台になる内容となります。
LP・IP・MIPの違い
最初に用語を整理しておきます。
| 種別 | 内容 |
|---|---|
| LP（Linear Program） | 線形制約のもとで線形関数を最小化・最大化 |
| IP（Integer Program） | 変数に整数条件が付いた最適化問題 |
| MIP（Mixed Integer Program） | 連続変数と整数変数が混在する問題 |
幾何的なイメージは以下のとおりです。
LP の実行可能領域は制約式が定める凸多面体（連続領域）そのものですが、IP では「凸多面体の中にある格子点（整数点）」だけが実行可能解になります。
そのため、計算が一気に難しくなります。
整数計画ソルバーの現状
だいたいその辺のPCで以下ぐらいの性能が出るかと思います。
| 変数数 | 状況 |
|---|---|
| 〜 5,000 | おそらく解ける |
| 〜 10,000 | 最適性の証明が難しいこともある |
| 〜 50,000 | 問題が簡単なら解ける |
「整数計画問題の難しさは必ずしも入力サイズに比例しない」というのも大事なポイントで、変数100個の問題でも極めて難問になることがあります。LP緩和の質や対称性の有無で計算量が大きく変わるからです。なので、逆に100万変数でもサクッと解けちゃうこともあります。
実務的には、ソルバーを途中で止めても 暫定解（incumbent）を取得できるので、 整数計画ソルバーを近似解法として使うことも多いです。下界値があれば暫定解の精度も事後的に評価できます。
2値変数の使い方
整数計画でよく出てくる初心者の罠が「整数変数 vs 2値変数」の使い分けです。
ルール
| 表したいもの | 使う変数 |
|---|---|
| 数（個数・台数・人数） | 整数変数 $x \in \mathbb{Z}_{\geq 0}$ |
| 状態・ラベル・選択 | 2値変数 $x \in {0,1}$ |
例：「4つの状態のうちどれか1つ」を表したいとき。
\text{NG:} \quad x \in \{0, 1, 2, 3\}
これは数値的に扱いにくく、線形制約と組み合わせにくいです。
\text{OK:} \quad x_1, x_2, x_3, x_4 \in \{0, 1\}, \quad x_1 + x_2 + x_3 + x_4 = 1
こちらは「ちょうど1つが 1」を線形に表現できて、LP緩和も自然になります。
なぜ2値変数の方がよいか
- LP緩和の幾何構造が綺麗（0と1の間の点が連続的に意味を持たせることができる）
- 論理制約と組み合わせやすい
- ソルバーは2値変数に対する最適化に強く特化している
「とりあえず整数変数で表現しよう」は罠なので、状態・選択は2値変数と覚えておくと良いかと思います。
論理的な制約条件（ナップサック問題で見てみる）
ナップサック問題：
\text{maximize} \quad \sum_{j=1}^{n} p_j x_j \quad \text{s.t.} \quad \sum_{j=1}^{n} w_j x_j \leq C,\ x_j \in \{0,1\}
$x_j$ は「荷物 $j$ を詰め込むかどうか」の2値変数です。ここに論理的な制約を追加してみます。
パターン1：詰め込める荷物は高々 k 個
x_1 + x_2 + \cdots + x_n \leq k
パターン2：荷物 i または荷物 j を詰め込む（少なくとも片方）
x_i + x_j \geq 1
これは論理 OR を表します。$x_i = 1$ または $x_j = 1$ なら満たされます。
パターン3：荷物 i を詰め込むならば荷物 j も詰め込む
x_i \leq x_j
「$i$ なら $j$」を表します。$x_i = 1$ なら $x_j = 1$ が強制されます。$x_i = 0$ のときは $x_j$ は自由。
パターン4：詰め込める荷物の数は 0 もしくは 2
x_1 + x_2 + \cdots + x_n = 2y, \quad y \in \{0, 1\}
補助変数 $y$ を使う方法。$y = 0$ なら個数は 0、$y = 1$ なら個数は 2 になります。
補助変数なしで書く方法もあります（$n=3$ の場合の凸包を直接表現）：
x_1 + x_2 + x_3 \leq 2, \quad -x_1 + x_2 + x_3 \geq 0, \quad x_1 - x_2 + x_3 \geq 0, \quad x_1 + x_2 - x_3 \geq 0
実行可能な格子点 ${(0,0,0), (1,1,0), (1,0,1), (0,1,1)}$ のみを含む凸包を不等式で記述しています。少し複雑ですが、LP緩和がタイトになるメリットがあります。
固定費用付き目的関数
実務でよくある「生産量に応じた費用 + 段取り替えなどの初期費用」を線形化する方法です。
問題
生産量 $x$ に対する総費用 $f(x)$：
f(x) = \begin{cases} 0 & x = 0 \\ c_1 x + c_2 & 0 < x \leq C \end{cases}
- $c_1$：単位量あたりの生産費
- $c_2$：少しでも生産すれば発生する初期費用
- $C$：生産量の上限
$x = 0$ では $f = 0$ ですが、$x$ が少しでも正になった瞬間に $c_2$ の初期費用がジャンプして加算される、という不連続な構造になっています。そのままでは線形最適化に使えません。
線形化
補助変数 $y \in {0, 1}$ を導入：
\begin{aligned}
\text{minimize} \quad & f(x) = c_1 x + c_2 y \\
\text{subject to} \quad & x \leq C y \\
& 0 \leq x \leq C \\
& y \in \{0, 1\}
\end{aligned}
仕掛け：
- $y = 0$ ⇒ $x \leq 0$ ⇒ $x = 0$、$f = 0$
- $y = 1$ ⇒ $x \leq C$（普通の上限）、$f = c_1 x + c_2$
少しでも $x > 0$ なら $y = 1$ にせざるを得ず、初期費用 $c_2$ が発生する仕組みです。
Pythonで実装
import pulp
# 例：生産量 0〜100、単位生産費 c1=3、初期費用 c2=50
# 利益最大化（収益 5x からコストを引く）
C = 100
c1 = 3
c2 = 50
revenue_per_unit = 5
prob = pulp.LpProblem("fixed_cost", pulp.LpMaximize)
x = pulp.LpVariable("x", lowBound=0, upBound=C)
y = pulp.LpVariable("y", cat='Binary')
# 目的関数：収益 - コスト
prob += revenue_per_unit * x - (c1 * x + c2 * y)
prob += x <= C * y
prob.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"x = {pulp.value(x):.2f}")
print(f"y = {pulp.value(y):.0f}")
print(f"利益 = {pulp.value(prob.objective):.2f}")
x = 100.00
y = 1
利益 = 150.00
$y=1$ で初期費用 50 を払って 100 単位生産。$5 \times 100 - 3 \times 100 - 50 = 150$ の利益となります。
例題：拡張ナップサック問題
論理制約をまとめて入れたナップサック問題も作ってみます。
import pulp
# データ
n = 6
weights = [3, 5, 2, 4, 6, 1]
values = [4, 7, 3, 5, 8, 2]
C = 10 # 容量
prob = pulp.LpProblem("ext_knapsack", pulp.LpMaximize)
x = [pulp.LpVariable(f"x{j}", cat='Binary') for j in range(n)]
# 目的関数
prob += pulp.lpSum(values[j] * x[j] for j in range(n))
# 容量制約
prob += pulp.lpSum(weights[j] * x[j] for j in range(n)) <= C
# 論理制約の例
prob += pulp.lpSum(x) <= 4 # 高々4個
prob += x[0] + x[1] >= 1 # 荷物0または1は必ず詰める
prob += x[2] <= x[3] # 荷物2を詰めるなら3も詰める
prob.solve(pulp.PULP_CBC_CMD(msg=0))
print(f"目的関数値 = {pulp.value(prob.objective):.0f}")
for j in range(n):
if pulp.value(x[j]) > 0.5:
print(f" 荷物{j}: 重さ={weights[j]}, 価値={values[j]}")
目的関数値 = 14
荷物1: 重さ=5, 価値=7
荷物3: 重さ=4, 価値=5
荷物5: 重さ=1, 価値=2
論理制約も含めてシンプルに扱えるのが整数計画モデリングの良いところです。
まとめ
- LP / IP / MIP の違いと、整数計画ソルバーの性能目安
- 状態・選択は2値変数で表現する（数を表すときだけ整数変数）
- 論理的な制約のパターン：高々$k$個・OR・含意・「0または2」
- 固定費用付き目的関数は2値変数 $y$ と $x \leq C y$ で線形化できる
次の記事では、「制約のうちどれか1つを満たせばよい」という離接制約を表現する Big-M 法を扱います。