オペレーションズリサーチ 第 5 回¶
整数計画法：0-1 変数による定式化と分枝限定法¶
日本大学生産工学部 オペレーションズリサーチ（柿本・大前）
0. この資料の使い方¶
第 3・4 回の線形計画問題では、決定変数は実数（小数も可）でした。今回は、決定変数が 整数 の値しかとれない 整数計画問題 を扱います。特に、0 か 1 しかとらない 0-1 変数 で「選ぶ・選ばない」「入れる・入れない」を表す定式化と、そうしてできた問題をどう解くかを学びます。
目的は次の 3 点です。
- 0-1 変数を使って、ナップサック問題のような 組合せの問題を定式化 できる（ビンパッキング問題は別冊『演習問題 1 の解説』）。
- 整数計画問題が線形計画問題より 難しい理由（LP の解を丸めてはいけない、全列挙は爆発する）を説明できる。
- 貪欲法・LP 緩和・分枝限定法 の考え方を理解し、小さなナップサック問題を分枝限定法で解ける。
前半（§1〜§2）は定式化、後半（§3〜§6）は解き方です。§7 ではソルバー（PuLP）を使い、定式化した問題をそのまま計算機に解かせます。
章立て¶
| 章 | 内容 |
|---|---|
| 1 | 整数計画問題とは |
| 2 | 0-1 変数で表す（ナップサック問題） |
| 3 | 解き方 (1)：全列挙 |
| 4 | 解き方 (2)：貪欲法 |
| 5 | 解き方 (3)：LP 緩和と上界 |
| 6 | 解き方 (4)：分枝限定法 |
| 7 | ソルバーで解く（PuLP） |
| 8 | 演習 |
| 付録 | 用語早見表 |
記法¶
第 1 回の記法をそのまま使います。品物や荷物（決定変数の添字）は $j \in J$、容器（制約の添字）は $i \in I$、係数は $a$、右辺（容量）は $b$、目的関数の係数（価値）は $c$ です（第 3 回 §2.7 と同じ並びです）。
1. 整数計画問題とは¶
1.1 定義¶
整数計画問題（IP: integer programming）とは、線形計画問題（LP: linear programming。目的関数も制約条件も 1 次式）に、決定変数が整数の値しかとらない という条件を加えた問題です。1 次式とは、$y = a_1 x_1 + a_2 x_2 + \dots + a_n x_n$ のように直線（平面）になる式のことです。正確には 整数線形計画問題 ですが、整数計画問題は基本的に線形を前提とするので、「線形」を省略して整数計画問題と呼ぶのがふつうです（この資料でもそう呼びます）。整数の条件は次のように書きます（第 1 回 §1.6、§1.7）。
$$ x_j \in \mathbb{Z}_+, \quad \forall j \in J $$
「すべての $j \in J$ について、$x_j$ は 0 以上の整数」と読みます。特に 0 か 1 しかとらない変数は
$$ x_j \in \{0, 1\}, \quad \forall j \in J $$
と書き、0-1 変数 と呼びます。決定変数がすべて 0-1 変数の問題を 0-1 整数計画問題 と呼びます。整数変数と実数変数が混在している問題は 混合整数計画問題 と呼びます。整数計画問題は混合整数計画問題の特殊形（実数変数が 0 個）とみることができます。この授業では混合整数計画問題は扱いません（解き方は同じです）。
実務で使われる整数計画問題の多くは 0-1 整数計画問題です。「する・しない」「選ぶ・選ばない」という決定が 0-1 変数で表せるからです（§2）。そこで、§1.2 で整数変数の例を 1 つ見たあとは、0-1 整数計画問題を前提に 説明します。
線形計画問題と並べると次のとおりです。
| 線形計画問題（第 3・4 回） | 整数計画問題（今回） | |
|---|---|---|
| 目的関数・制約条件 | 1 次式 | 1 次式 |
| 決定変数 | 実数（$x_j \ge 0$） | 整数（$x_j \in \mathbb{Z}_+$）または 0-1（$x_j \in \{0, 1\}$） |
| 表せるもの | 生産量・時間など連続的な量 | 個数、「する・しない」の選択 |
| 実行可能解 | 実行可能領域（凸多角形）の全体 | その中の格子点（座標がすべて整数の点）だけ |
| 解き方 | 単体法。大規模でも現実的な時間で解ける | 分枝限定法（§6）。問題によっては時間がかかる |
| 長所 | 大規模でも現実的な時間で解ける | モノの個数や状態（0 か 1）を表現できる |
| 短所 | 連続値しかとれないので、個数や状態を記述しにくい | 大規模だと現実的な時間で解けないことがある |
1.2 生産計画問題を整数で解く¶
第 3 回の生産計画問題で、製品 $P_1, P_2$ を kg ではなく 個数 で作ることにしましょう。$x_1, x_2$ は 0 以上の整数です（$x_1, x_2 \in \mathbb{Z}_+$。これを 整数制約 と呼びます）。
$$ \begin{aligned} & z = 3x_1 + 5x_2 \rightarrow \max, \\ \text{s.t.} \quad & x_1 + 7x_2 \le 140, \\ & 2x_1 + 4x_2 \le 100, \\ & 3x_1 + 2x_2 \le 120, \\ & x_1 \in \mathbb{Z}_+,\ x_2 \in \mathbb{Z}_+. \end{aligned} $$
整数の条件を外した問題（元の線形計画問題）の最適解は、第 3・4 回で求めた頂点 B $(35, 7.5)$、$z = 142.5$ でした。整数の条件を外した線形計画問題を、元の整数計画問題の LP 緩和（線形計画緩和）と呼びます（§5 で詳しく扱います）。
LP と比べて問題はどう変わるでしょうか。LP の最適解は $x_2 = 7.5$ で整数になっていないので、整数計画問題の答えにはなりません。「頂点の中に最適解がある」という LP の性質が使えないのです。では、近くの整数の点にすればよいでしょうか。図で確かめます。実行可能領域の中の黒い点が、整数計画問題の実行可能解（格子点）です。
B の周りを拡大します。
- $x_2$ を四捨五入した $(35, 8)$ は、$2 \cdot 35 + 4 \cdot 8 = 102 > 100$ なので 2 本目の制約を破り、実行不能です。
- 切り捨てた $(35, 7)$ は実行可能で、$z = 105 + 35 = 140$ です。
- しかし、整数計画問題の最適解は $(34, 8)$ で、$z = 102 + 40 = 142$ です。B の隣ではない点が最適解です。
LP 緩和の最適解を丸めても、整数計画問題の最適解は得られません。
1.3 丸めてはいけない理由¶
実数をあるルールに従って整数にすることを 丸め と呼びます（四捨五入、切り捨て、切り上げなど）。LP 緩和の解を丸めてすませられない理由は次の 3 つです。
- 丸めた点が実行不能になることがあります（上の $(35, 8)$）。
- 丸めた点が実行可能でも、最適とは限りません（上の $(35, 7)$。最適解 $(34, 8)$ は LP 緩和の最適解の「隣」ではありません）。
- 0-1 変数では、丸めはそもそも意味がありません。$x_j = 0.5$ を 0 にするか 1 にするかで「入れない」と「入れる」が変わり、答えがまったく変わります（§2）。
変数が $n$ 個あれば、各変数を切り上げるか切り捨てるかで $2^n$ 通りの丸め方があり、どれが正しいかは試してみないと分かりません。
一方で、LP 緩和の最適値 $142.5$ は無駄ではありません。整数の実行可能解はすべて LP 緩和の実行可能解でもあるので、整数計画問題の最適値は LP 緩和の最適値を超えない ことが分かります（$142 \le 142.5$。最大化の場合、整数の実行可能解の目的関数値は LP 緩和の最適値を超えません）。この性質は、整数計画問題の標準的な解法である分枝限定法（§6）で重要になります。§5 で詳しく見ます。
1.4 なぜ整数計画問題は難しいのか¶
線形計画問題には「最適解は頂点にある」という性質があり（第 3 回 §5.1、第 4 回 §3.5）、単体法は頂点だけを調べます。整数計画問題にはこの性質がありません。上の図のとおり、最適解 $(34, 8)$ は実行可能領域の頂点ではなく、内部の格子点です。調べる候補は頂点ではなく格子点全体で、その数は変数が増えると爆発的に増えます（§3）。
整数計画問題を一般に効率よく解く方法は知られていません。しかし、「調べなくても分かる候補」をうまく省けば、現実の大きさの問題でも最適解が求まることが多く、§6 の分枝限定法がその基本です。
2. 0-1 変数で表す¶
2.1 ナップサック問題¶
次の問題を考えます。
貨物輸送にあたり、箱にいくつかの品物を詰めて送ります。品物は 6 個あり、それぞれの価値と重さは表のとおりです。箱には 60 kg までしか入りません。価値の合計が最大になるように、どの品物を入れればよいでしょうか。
| 品物 $j$ | 品物名 | 価値 $c_j$ | 重さ $a_j$ [kg] |
|---|---|---|---|
| 1 | 書籍セット | 120 | 10 |
| 2 | ワークステーション | 250 | 21 |
| 3 | プリンター | 185 | 16 |
| 4 | モニター | 100 | 9 |
| 5 | バッテリー | 130 | 12 |
| 6 | ケーブル | 80 | 7 |
箱の容量は $b = 60$ kg です。つまり、品物 $j$ を箱に「入れるか、入れないか」を決める問題です。
これを ナップサック問題 と呼びます（ナップサック = リュックサック）。
2.2 0-1 変数¶
「品物 $j$ を箱に入れるか、入れないか」のような「する・しない」の決定は、$x_j \in \{0, 1\}$ と宣言した変数 $x_j$ で表します。「$j$ について、する（1）か、しない（0）か」を表す変数で、0-1 変数 と呼びます。
$$ x_j = \begin{cases} 1 & \text{品物 } j \text{ を箱に入れる} \\ 0 & \text{入れない} \end{cases} $$
0-1 変数の便利なところは、選んだものの合計 が $\sum$ で書けることです。品物 $j$ の価値を $c_j$ とすると
$$ \sum_{j \in J} c_j x_j $$
は「箱に入れた品物の価値の合計」です。入れない品物は $x_j = 0$ なので、掛け算で消えます（第 1 回 §3.4）。同様に $\sum_{j \in J} x_j$ は「入れた品物の個数」です。
たとえば $J = \{1, 2, 3\}$ で $(x_1, x_2, x_3) = (1, 0, 1)$ なら、$\sum_{j \in J} c_j x_j = c_1 \cdot 1 + c_2 \cdot 0 + c_3 \cdot 1 = c_1 + c_3$、$\sum_{j \in J} x_j = 2$ です。
2.3 定式化¶
§2.1 の問題を、第 3 回 §2 の手順（決定変数 → 目的関数 → 制約条件）で定式化します。
決定変数 品物 $j$ を入れるかどうかを決めるので、品物ごとに 0-1 変数を用意します。
$$ x_j = \begin{cases} 1 & \text{品物 } j \text{ を箱に入れる} \\ 0 & \text{入れない} \end{cases}, \quad j = 1, \dots, 6 $$
目的関数 入れた品物の価値の合計を最大化します。
$$ z = 120x_1 + 250x_2 + 185x_3 + 100x_4 + 130x_5 + 80x_6 \rightarrow \max $$
制約条件 入れた品物の重さの合計が容量以下です。
$$ 10x_1 + 21x_2 + 16x_3 + 9x_4 + 12x_5 + 7x_6 \le 60 $$
定式化（まとめ）
$$ \begin{aligned} & z = 120x_1 + 250x_2 + 185x_3 + 100x_4 + 130x_5 + 80x_6 \rightarrow \max, \\ \text{s.t.} \quad & 10x_1 + 21x_2 + 16x_3 + 9x_4 + 12x_5 + 7x_6 \le 60, \\ & x_j \in \{0, 1\}, \quad j = 1, \dots, 6. \end{aligned} $$
線形計画問題の非負条件 $x_j \ge 0$ の代わりに、$x_j \in \{0, 1\}$ が入ります。
2.4 一般形で書く¶
品物の集合を $J = \{1, \dots, n\}$、品物 $j$ の価値を $c_j$、重さを $a_j$、箱の容量を $b$ とすると
$$ \begin{aligned} & z = \sum_{j \in J} c_j x_j \rightarrow \max, \\ \text{s.t.} \quad & \sum_{j \in J} a_j x_j \le b, \\ & x_j \in \{0, 1\}, \quad \forall j \in J. \end{aligned} $$
品物が何個あっても式の形は変わりません。$J = \{1, \dots, 6\}$ で展開すると §2.3 の式に戻ります（展開のしかたは第 1 回 §3.2）。制約は容量の 1 本だけで、変数の型 $x_j \in \{0, 1\}$ が整数計画問題の印です。
以降、変数をまとめて $\boldsymbol{x} = (x_1, x_2, \dots, x_n)$ と書きます（太字の $\boldsymbol{x}$ は $n$ 個の変数の値を並べたもので、ベクトルと呼びます）。例えば $\boldsymbol{x} = (1, 0, 1)$ は $x_1 = 1$、$x_2 = 0$、$x_3 = 1$ のことです。また、最適解や最適値を表すときには $\boldsymbol{x}^*$、$z^*$ のように $*$ を付けます。
§2.1 のナップサック問題の答えを先に示しておきます。最適解は $\boldsymbol{x}^* = (1, 1, 1, 0, 1, 0)$、つまり品物 1, 2, 3, 5（書籍セット、ワークステーション、プリンター、バッテリー）を入れることで、最適値は $z^* = 685$ です。重さは $59 \le 60$ で容量を満たし、価値 685 はこれ以上大きくできません。
では、どのようにしてこの最適解を得ればよいでしょうか。それが §3〜§6 の話題です。
2.5 0-1 変数で表せるもの¶
0-1 変数は「する・しない」を表せるので、さまざまな問題の定式化に使えます。
| 決める内容 | 変数 |
|---|---|
| 製品 $j$ を生産するか | $x_j = 1$（生産する）、$0$（しない） |
| 地域 $i$ に施設 $j$ を建てるか | $x_{ij}$ |
| 従業員 $i$ を曜日 $w$ の時間帯 $t$ のシフトに入れるか | $x_{iwt}$（添字が 3 つ） |
| 配送で地点 $i$ から地点 $j$ へ進むか | $x_{ij}$（第 6 回のグラフの問題） |
添字（$i$、$j$、$w$、$t$）は自然数（$1, 2, 3, \dots$）です。0-1 変数を組み合わせると、多種多様な状態を表現できます。
条件も 1 次式で書けます。
| 条件 | 式 |
|---|---|
| $j$ を選ぶのは高々 $k$ 個 | $\sum_{j \in J} x_j \le k$ |
| 品物 1 を入れるなら品物 2 も入れる | $x_1 \le x_2$ |
| 品物 1 と 2 は同時には入れない | $x_1 + x_2 \le 1$ |
3. 解き方 (1)：全列挙¶
3.1 すべてのパターンを調べる¶
0-1 変数の問題は、各変数が 0 か 1 なので、すべての組合せを書き出して調べる ことができます。§2.1 のナップサック問題なら、$(x_1, \dots, x_6)$ の組合せは $2^6 = 64$ 通りです。それぞれについて重さと価値を計算し、重さが 60 kg 以下のものの中で価値が最大のものを選べば、それが最適解です。
| $(x_1, x_2, x_3, x_4, x_5, x_6)$ | 重さ [kg] | 価値 | 実行可能？ |
|---|---|---|---|
| $(0, 0, 0, 0, 0, 0)$ | 0 | 0 | ○ |
| $(0, 0, 0, 0, 0, 1)$ | 7 | 80 | ○ |
| $(0, 0, 0, 0, 1, 0)$ | 12 | 130 | ○ |
| $(0, 0, 0, 0, 1, 1)$ | 19 | 210 | ○ |
| $\vdots$ | |||
| $(1, 1, 1, 0, 1, 0)$ | 59 | 685 | ○ ← 最大 |
| $\vdots$ | |||
| $(1, 1, 1, 1, 0, 0)$ | 56 | 655 | ○ |
| $(1, 1, 1, 1, 1, 0)$ | 68 | 785 | × |
| $(1, 1, 1, 1, 1, 1)$ | 75 | 865 | × |
64 通りのうち実行可能なものは 59 通りで、価値が最大なのは品物 1, 2, 3, 5 を入れる $(1, 1, 1, 0, 1, 0)$ です。重さ 59 kg、価値 685 です（§2.4 で示した $\boldsymbol{x}^*$、$z^* = 685$）。この方法を 全列挙 と呼びます。全列挙は必ず最適解を見つけます。
3.2 パターンの数¶
問題は、組合せの数です。品物が $n$ 個なら $2^n$ 通りあります。
| 品物の数 $n$ | パターンの数 $2^n$ | 1 秒に $10^9$ 通り調べると |
|---|---|---|
| 6 | 64 | 一瞬 |
| 10 | 1,024 | 一瞬 |
| 20 | 1,048,576（約 $10^6$） | 0.001 秒 |
| 30 | 約 $1.1 \times 10^9$ | 1 秒 |
| 50 | 約 $1.1 \times 10^{15}$ | 約 13 日 |
| 100 | 約 $1.3 \times 10^{30}$ | 約 $4 \times 10^{13}$ 年 |
品物が 100 個のナップサック問題は、実務では小さい問題です。それでも全列挙では宇宙の年齢（約 $1.4 \times 10^{10}$ 年）の 1000 倍以上かかります。第 4 回 §3.6 の「基底解を総当たりする」と同じ状況で、全部調べる方法は使えません。
ビンパッキング問題はもっと急に増えます。荷物 $n$ 個をそれぞれどの容器（$m$ 個）に入れるかで $m^n$ 通りです。荷物 8 個・容器 4 個でも $4^8 = 65{,}536$ 通り、荷物 30 個・容器 10 個なら $10^{30}$ 通りです。
3.3 全列挙の無駄¶
ただし、64 通りの多くは 調べなくても結果が分かる パターンです。たとえば品物 1〜4 を入れると重さは $10 + 21 + 16 + 9 = 56$ kg で、残りは 4 kg です。品物 5（12 kg）も 6（7 kg）も入らないので、品物 1〜4 を入れた上で 5 や 6 を入れる 3 通りは、計算しなくても実行不能と分かります。
逆に、「残りの品物を全部入れても、今までに見つけた解に届かない」組合せも、調べる必要がありません。全列挙のこのような無駄を系統的に省くのが、§6 の分枝限定法です。その準備として、§4 で「速いが最適とは限らない方法」、§5 で「最適値の上限を知る方法」を見ます。
4. 解き方 (2)：貪欲法¶
4.1 考え方¶
全列挙が無理なら、「よさそうな順に決めていく」単純な方法が考えられます。ナップサック問題なら、重さ 1 kg あたりの価値 $c_j / a_j$（いわゆるコスパ）が大きい品物ほど「お得」なので、
比 $c_j / a_j$ の大きい順に品物を見て、入るなら入れる、入らないなら飛ばす
という方法です。このように、目先の得で順に決めていき、一度決めたら戻らない方法を 貪欲法 と呼びます。計算は、比を $n$ 回計算して並べ替えるだけです。
4.2 例¶
§2.1 のナップサック問題で比を計算します。
| 品物 $j$ | 価値 $c_j$ | 重さ $a_j$ | 比 $c_j / a_j$ | 順位 |
|---|---|---|---|---|
| 1 | 120 | 10 | $120/10 = 12.00$ | 1 |
| 2 | 250 | 21 | $250/21 = 11.90$ | 2 |
| 3 | 185 | 16 | $185/16 = 11.56$ | 3 |
| 4 | 100 | 9 | $100/9 = 11.11$ | 5 |
| 5 | 130 | 12 | $130/12 = 10.83$ | 6 |
| 6 | 80 | 7 | $80/7 = 11.43$ | 4 |
比の大きい順は品物 1, 2, 3, 6, 4, 5 です。この順に入れていきます。
- 品物 1（10 kg）を入れる。合計 10 kg、価値 120。
- 品物 2（21 kg）を入れる。合計 31 kg、価値 370。
- 品物 3（16 kg）を入れる。合計 47 kg、価値 555。
- 品物 6（7 kg）を入れる。合計 54 kg、価値 635。
- 品物 4（9 kg）は残り 6 kg に入らないので飛ばす。
- 品物 5（12 kg）も入らないので飛ばす。
結果は品物 1, 2, 3, 6 を入れて、重さ 54 kg、価値 635 です。
4.3 貪欲法の答えは最適とは限らない¶
§3.1 の全列挙で求めた最適値は 685（品物 1, 2, 3, 5）でした。貪欲法の 635 はそれより小さく、最適解ではありません。貪欲法は品物 6（比では 4 位）を入れた時点で残りが 6 kg になり、品物 5（12 kg）を入れる余地がなくなりました。品物 6 を入れずに品物 5 を入れた方が価値は高いのですが、貪欲法は一度決めたことを戻して試しません。
「価値の大きい順」に入れる貪欲法も考えられます。この例では品物 2, 3, 5, 1 の順に入れて 59 kg、価値 685 となり、偶然最適解と一致します。しかし、たとえば価値 $(10, 7, 5)$、重さ $(5, 3, 3)$、容量 6 の問題では、価値の順では品物 1 を入れて終わり（価値 10）ですが、品物 2 と 3 を入れた方が価値 12 で高くなります。どんな順番で詰めても、貪欲法が最適解を見つける保証はありません。
4.4 貪欲法の使いどころ¶
貪欲法は速く、それなりに良い解を出します。実務では「最適でなくてもよいから速く」という場面で使われます。また、§6 の分枝限定法では、貪欲法の解を 出発点の暫定解（これより悪い解は調べない、という基準）として使います。貪欲法の解は実行可能なので、最適値は少なくとも 635 以上だと分かります。貪欲法の解の値を $z_{\text{greedy}}$ と書くと、$z_{\text{greedy}} = 635 \le z^* = 685$ です。
5. 解き方 (3)：LP 緩和と上界¶
5.1 LP 緩和¶
整数計画問題の $x_j \in \{0, 1\}$ を $0 \le x_j \le 1$ に置き換えた問題を LP 緩和 と呼びます（§1.2）。整数の条件を「ゆるめた」（緩和した）線形計画問題なので、第 4 回の単体法で解けます。整数計画のソルバーも、LP 緩和を単体法で解いています。
§2.1 のナップサック問題の LP 緩和を単体法で解くと、最適解は $\boldsymbol{x} = (1, 1, 1, \tfrac{2}{3}, 0, 1)$、最適値は $2105/3 \approx 701.67$ で、分数になる変数は $x_4$ の 1 つだけです（単体法の計算は長いので省きます。§5.2 で答えを確かめます）。
この形になる理由は次のとおりです。$0 \le x_j \le 1$ なら品物を「一部だけ」入れてよいので、
比 $c_j / a_j$ の大きい順に品物を入れ、入らなくなった品物は 入る分だけ（分数で）入れて容量を使い切る
のが最適です。1 kg あたりの価値が高いものから容量を埋めるのが、価値の合計を最も大きくするからです。分数になる品物は高々 1 つです。手計算で毎回単体法を実行するのは大変なので、この近道で LP 緩和の最適解を求めてかまいません。ナップサック問題では、この近道が LP 緩和を解くことそのものになり、単体法と同じ答えになります（演習問題 2 もこの方法で解きます）。
5.2 例¶
§2.1 のナップサック問題では、§4.2 と同じ順に品物 1, 2, 3, 6 を入れて 54 kg、価値 635 です。次の品物 4（9 kg）は残り 6 kg に入りませんが、LP 緩和なら $x_4 = 6/9 = 2/3$ だけ入れられます（§4.2 の図の下の棒）。
$$ \boldsymbol{x} = \left(1, 1, 1, \tfrac{2}{3}, 0, 1\right), \qquad z = 635 + 100 \cdot \tfrac{2}{3} = \tfrac{2105}{3} \approx 701.67 $$
$x_4 = 2/3$ は整数ではないので、これは整数計画問題の解ではありません。「モニターの 3 分の 2」は送れません。
5.3 LP 緩和の最適値は上界¶
§1.3 で述べたとおり、整数計画問題の実行可能解はすべて LP 緩和の実行可能解でもあります（$x_j \in \{0, 1\}$ なら $0 \le x_j \le 1$ を満たす）。LP 緩和はより広い範囲から最大値を探すので、
整数計画問題の最適値 $\le$ LP 緩和の最適値
が常に成り立ちます（最大化の場合）。LP 緩和の最適値は、整数計画問題の最適値の 上界 です。上界とは、「最適値はこれより絶対に良くならない」と分かっている値のことで、$z_{\text{upper}}$ と書きます（$z^* \le z_{\text{upper}}$）。最適値そのものではなく、最適値を上から押さえる値です。LP 緩和の最適値を $z_{\text{LP}}$ と書くと、$z_{\text{upper}} = z_{\text{LP}}$ にとれます。
この問題では価値がすべて整数なので、整数計画問題の最適値も整数です。したがって上界は $z_{\text{LP}} = 701.67$ を切り捨てた $z_{\text{upper}} = \lfloor z_{\text{LP}} \rfloor = 701$ にできます。実際の最適値 $z^* = 685$ はこれ以下です。$z_{\text{LP}} = 701.67$ は条件をゆるめて得た最適値なので、$z^*$ より大きいことは確実です。LP 緩和の解は整数計画問題の実行可能解にはなりませんが、上界にはなります。
5.4 下界と上界で挟む¶
§4 の貪欲法と §5 の LP 緩和を合わせると、最適値 $z^*$ を計算せずに、その範囲が分かります。
$$ 635 \le z^* \le 701 $$
左は貪欲法の解（実行可能解の値なので、最適値はこれ以上。下界）、右は LP 緩和の上界です。下界とは、「最適値は最低限これ」と分かっている値のことで、$z_{\text{lower}}$ と書きます（$z_{\text{lower}} \le z^*$）。貪欲法の解の値を $z_{\text{greedy}}$ と書くと、ここでは $z_{\text{lower}} = z_{\text{greedy}} = 635$ です。まとめると
$$ z_{\text{lower}} \le z^* \le z_{\text{upper}}, \qquad 635 \le z^* \le 701 $$
です。
$635 \le z^* \le 701$ と分かれば、「貪欲法の解は最適値に対して最大でも 1 割しか悪くない」と言えます。下界と上界の幅は狭いほどよい情報です。実務ではこの保証があれば十分なことも多く、整数計画のソルバーは、計算を途中で打ち切ったときにこの形で答えを出します。
もし LP 緩和の最適解がたまたますべて整数なら、それは整数計画問題の実行可能解であり、しかも上界と一致するので、そのまま最適解です。この観察が §6 の分枝限定法の終了条件になります。
6. 解き方 (4)：分枝限定法¶
6.1 考え方¶
§5 の LP 緩和では、$x_4 = 2/3$ という分数が出ました。整数計画問題の解では $x_4$ は 0 か 1 です。そこで、問題を
- 制約 $x_4 = 0$ を追加した問題（品物 4 を入れない）
- 制約 $x_4 = 1$ を追加した問題（品物 4 を入れる）
の 2 つに 分ける ことにします。元の問題の最適解は、このどちらかの最適解です。分けた問題の LP 緩和を解いてまた分数が出れば、さらに 2 つに分けます。これを繰り返すと、問題が枝分かれしていきます。これが 分枝（場合分け）です。この枝分かれを図にしたもの（§6.3 の図）を 木 と呼び、木の箱の 1 つ 1 つ、つまり変数を固定した部分問題を ノード と呼びます。
分けるだけでは、最後は全列挙と同じ $2^n$ 通りになります。そこで、分けた問題ごとに LP 緩和の上界（§5.3）を計算し、
その上界が、すでに見つけた実行可能解（暫定解）の値以下なら、その問題を分けても暫定解より良い解は出ない
ので、それ以上調べずに捨てます。これが 限定（枝刈り。捨てる枝を決めること）です。分枝限定法を始める時点で持っている実行可能解を 初期解 と呼び、最初の暫定解にします。この資料では貪欲法の解（§4）を初期解にします。初期解が良い（値が大きい）ほど、早い段階で枝刈りができます（§6.4）。分枝と限定を組み合わせた方法を 分枝限定法 と呼びます。
図は §2.1 の 6 品目の問題で、ノード 1（制約なし）の LP 緩和で $x_4 = 2/3 \notin \{0, 1\}$ が出たので、制約 $x_4 = 1$ を追加した問題と $x_4 = 0$ を追加した問題に分けたところです。$\lfloor z_{\text{LP}} \rfloor = 701 > z_{\text{lower}} = 635$ なので、ノード 1 は枝刈りできません。
6.2 手順¶
分けた問題を ノード と呼び、追加した制約（固定した変数）の組で区別します。初期解（最初の暫定解）は貪欲法の解（§4）にし、その値を下界 $z_{\text{lower}}$ とします。各ノードで次を行います。
- 追加した制約（固定した変数）を守って LP 緩和を解く（単体法。手計算では §5.1 の近道）。固定した品物だけで容量を超えるなら、そのノードは 実行不能 として終わり。
- LP 緩和の最適値 $z_{\text{LP}}$ を切り捨てたものを、そのノードの 上界 $z_{\text{upper}} = \lfloor z_{\text{LP}} \rfloor$ とする。
- 判定する。
- $z_{\text{upper}} \le z_{\text{lower}}$ → このノードから暫定解より良い解は出ない。枝刈り して終わり。
- LP 緩和の解がすべて整数 → それは実行可能解で、値は $z_{\text{upper}}$（$> z_{\text{lower}}$）。暫定解を更新（$z_{\text{lower}}$ をその値に）して終わり。
- 分数の変数 $x_k$ がある → $x_k = 1$ と $x_k = 0$ の 2 つのノードに 分枝 する。分数の変数が複数あるときは、添字が最小のものを選ぶ（ナップサック問題では分数は高々 1 つなので起こらないが、ビンパッキング問題のように制約が多い問題では複数出る）。どれを選んでも最適解には着き、選び方は計算の速さにだけ効く。
- 分枝で作ったノードのうち、まだ調べていないものを順に調べる（枝刈り・整数解・実行不能で終わったノードの下には、調べるノードはない）。この資料では $x_k = 1$ の側を先に、深さ優先（子を先に調べ切ってから兄弟へ）で調べる。
調べるノードがなくなったら終了で、そのときの暫定解が最適解です。途中のノードは、どれも「暫定解より良い解はこの中にない」と確かめた上で捨てているからです。手順全体をフローチャートにすると次のとおりです。
6.3 例：4 品目のナップサック問題¶
手で追えるように、小さい問題で分枝限定法を実行します。
| 品物 $j$ | 価値 $c_j$ | 重さ $a_j$ | 比 $c_j / a_j$ | 順位 |
|---|---|---|---|---|
| 1 | 16 | 2 | $16/2 = 8.00$ | 1 |
| 2 | 11 | 4 | $11/4 = 2.75$ | 2 |
| 3 | 19 | 7 | $19/7 = 2.71$ | 3 |
| 4 | 13 | 5 | $13/5 = 2.60$ | 4 |
容量は $b = 8$ です。比の大きい順は品物 1, 2, 3, 4 で、番号の順と同じです。
準備（貪欲法で初期解を得る） 比の順に入れていきます。
$$ \begin{aligned} & a_1 = 2 < 8 \;\rightarrow\; x_1 = 1, \\ & a_1 + a_2 = 6 < 8 \;\rightarrow\; x_2 = 1, \\ & a_1 + a_2 + a_3 = 13 \not\le 8 \;\rightarrow\; x_3 = 0, \\ & a_1 + a_2 + a_4 = 11 \not\le 8 \;\rightarrow\; x_4 = 0. \end{aligned} $$
初期解は $\boldsymbol{x} = (1, 1, 0, 0)$、$z_{\text{lower}} = z_{\text{greedy}} = 27$ です（重さ $6 <$ 容量 $8$）。
ノード 1（固定なし） LP 緩和は品物 1, 2 を入れて 6、品物 3 を $2/7$ だけ入れて $\boldsymbol{x} = (1, 1, \tfrac{2}{7}, 0)$、$z_{\text{LP}} = 27 + 19 \cdot \tfrac{2}{7} = 227/7 \approx 32.43$ です。上界は $z_{\text{upper}} = 32$ で、$z_{\text{lower}} = 27$ より大きいので枝刈りできません。$x_3$ が分数なので、$x_3 = 1$ と $x_3 = 0$ に分枝します。
ノード 2（$x_3 = 1$） 品物 3（7）を先に入れ、残り 1 に品物 1 を $1/2$ だけ入れて $\boldsymbol{x} = (\tfrac{1}{2}, 0, 1, 0)$、$z_{\text{LP}} = 19 + 16 \cdot \tfrac{1}{2} = 27$、$z_{\text{upper}} = 27$ です。$z_{\text{upper}} = 27 \le z_{\text{lower}} = 27$ なので、このノードの下には初期解より良い解はありません。枝刈りです。初期解のおかげで、$x_3 = 1$ の側を調べずにすみました。
ノード 3（$x_3 = 0$） 品物 1, 2 で 6、残り 2 に品物 4 を $2/5$ だけ入れて $\boldsymbol{x} = (1, 1, 0, \tfrac{2}{5})$、$z_{\text{LP}} = 27 + 13 \cdot \tfrac{2}{5} = 161/5 = 32.2$、$z_{\text{upper}} = 32 > 27$。$x_4$ で分枝します。
ノード 4（$x_3 = 0, x_4 = 1$） 品物 4（5）を先に入れ、残り 3 に品物 1（合計 7）、品物 2 は $1/4$ だけ入れて $\boldsymbol{x} = (1, \tfrac{1}{4}, 0, 1)$、$z_{\text{LP}} = 29 + 11 \cdot \tfrac{1}{4} = 127/4 = 31.75$、$z_{\text{upper}} = 31 > 27$。$x_2$ で分枝します。
ノード 5（$x_3 = 0, x_4 = x_2 = 1$） 固定した品物だけで $5 + 4 = 9 > 8$ なので実行不能です。
ノード 6（$x_3 = 0, x_4 = 1, x_2 = 0$） 品物 4 で 5、残り 3 に品物 1（2）が入って 7。これ以上入れる品物はなく、$\boldsymbol{x} = (1, 0, 0, 1)$ はすべて整数で、値 29 です。暫定解を更新し、$z_{\text{lower}}$ を 27 から 29 にします。
ノード 7（$x_3 = 0, x_4 = 0$） 品物 1, 2 を入れて 6、値 27。品物 3, 4 は固定で入れないので $\boldsymbol{x} = (1, 1, 0, 0)$、$z_{\text{upper}} = 27$。$z_{\text{lower}} = 29$ 以下なので枝刈りです。
調べるノードがなくなったので終了です。最適解は $\boldsymbol{x}^* = (1, 0, 0, 1)$（品物 1, 4）、最適値 $z^* = 29$ です。
以上を表にまとめると次のとおりです（演習問題 2 の解答用紙もこの形です）。
| ノード | 追加した制約 | $\boldsymbol{x}$ | $z_{\text{LP}}$ | $z_{\text{upper}}$ | 判定 |
|---|---|---|---|---|---|
| 1 | なし | $(1, 1, \tfrac{2}{7}, 0)$ | $227/7$ | 32 | $x_3 = 2/7 \notin \{0, 1\}$ → 分枝 |
| 2 | $x_3 = 1$ | $(\tfrac{1}{2}, 0, 1, 0)$ | 27 | 27 | $z_{\text{upper}} = 27 \le z_{\text{lower}} = 27$ → 枝刈り |
| 3 | $x_3 = 0$ | $(1, 1, 0, \tfrac{2}{5})$ | $161/5$ | 32 | $x_4 = 2/5 \notin \{0, 1\}$ → 分枝 |
| 4 | $x_3 = 0, x_4 = 1$ | $(1, \tfrac{1}{4}, 0, 1)$ | $127/4$ | 31 | $x_2 = 1/4 \notin \{0, 1\}$ → 分枝 |
| 5 | $x_3 = 0, x_4 = 1, x_2 = 1$ | — | — | — | 重さ $9 > 8$ → 実行不能 |
| 6 | $x_3 = 0, x_4 = 1, x_2 = 0$ | $(1, 0, 0, 1)$ | 29 | 29 | 整数解 → $z_{\text{lower}} = 29$ |
| 7 | $x_3 = 0, x_4 = 0$ | $(1, 1, 0, 0)$ | 27 | 27 | $z_{\text{upper}} = 27 \le z_{\text{lower}} = 29$ → 枝刈り |
6.4 何が省けたか¶
全列挙なら $2^4 = 16$ 通りを調べます。分枝限定法ではノードが 7 つで、LP 緩和を解いたのは 6 回です。ノード 2 の枝刈りで $x_3 = 1$ の組合せ 8 通りを、ノード 7 の枝刈りで $x_3 = x_4 = 0$ の組合せ 4 通りを、まとめて調べずにすませました。品物が 4 個では大した差ではありませんが、品物が 100 個の問題でも、分枝限定法なら $2^{100}$ 通りのうちごく一部を調べるだけで最適解に着くことが多くあります。
枝刈りが効くのは、上界が小さく、暫定解が良いときです。ノード 2 の枝刈りは、初期解の値 27 があったからできました。もし初期解を持たずに始める（$z_{\text{lower}} = 0$ とする）と、ノード 2 は $z_{\text{upper}} = 27 > 0$ なので分枝され、その下で実行不能のノードを 3 つと値 19 の整数解を見つけてからやっと $x_3 = 0$ の側に移ります。ノードは全部で 13 になります。だから、初期解に貪欲法の解を使い、$x_k = 1$ の側（良い解が見つかりやすい側）を先に調べます。
6.5 分枝限定法の性質¶
- 分枝限定法は、終了すれば必ず最適解を出します。捨てたノードには暫定解より良い解がないことを確かめているからです。
- 計算時間は問題によります。枝刈りがほとんど効かない問題では、全列挙と同じ $2^n$ 個のノードを調べることになります。整数計画問題が「難しい」と言われるのはこのためです。
- 計算を途中で打ち切っても、そのときの暫定解（下界）と、残っているノードの上界の最大値（上界）が得られます。「最適値との差は 2% 以内」のように、最適値との誤差保証を与えることができます。
- 実際のソルバー（§7 で使う無料の CBC や、商用の Gurobi など）は、分枝限定法に、LP 緩和を強くする工夫（切除平面）や、良い暫定解を早く見つける工夫（ヒューリスティック）を組み合わせています。基本は今回の手順と同じです。
7. ソルバーで解く（PuLP）¶
7.1 PuLP とは¶
PuLP は、Python で線形計画問題・整数計画問題を書いてソルバーに渡すライブラリです。ソルバー CBC（パッケージ cbcbox で入ります）が、分枝限定法（と §6.5 の工夫）で解きます。定式化（§2）をそのままプログラムに写せるので、変数が数千個あっても手間は変わりません。
この節のコードは、配布するノートブック 05_pulp.ipynb に入っています。Google Colab で開いて実行してください（提出は不要です）。Colab では最初に !pip install pulp cbcbox が必要です。
この資料のコードは PuLP 4.x（2026 年）の書き方です。3.x 以前は変数を pulp.LpVariable(名前, …) で作り、prob.solve(pulp.PULP_CBC_CMD(msg=0)) で解き、状態を pulp.LpStatus[prob.status] で見ました（4.0 で変わりました）。
7.2 生産計画問題（整数版）¶
§1.2 の問題です。整数変数は cat="Integer" で宣言します。
import pulp
prob = pulp.LpProblem("production", pulp.LpMaximize) # 最大化問題
x1 = prob.add_variable("x1", lowBound=0, cat="Integer") # x1 ∈ Z+
x2 = prob.add_variable("x2", lowBound=0, cat="Integer") # x2 ∈ Z+
prob += 3 * x1 + 5 * x2 # 目的関数
prob += x1 + 7 * x2 <= 140 # 制約条件
prob += 2 * x1 + 4 * x2 <= 100
prob += 3 * x1 + 2 * x2 <= 120
stats = prob.solve(pulp.COIN_CMD(msg=0)) # CBC で解く（msg=0 で途中経過を出さない）
print("状態:", stats.status_str)
print("最適解: x1 =", x1.value(), ", x2 =", x2.value())
print("最適値: z =", pulp.value(prob.objective))
状態: Optimal 最適解: x1 = 34.0 , x2 = 8.0 最適値: z = 142.0
§1.2 の図のとおり、$(34, 8)$、$z = 142$ です。cat="Integer" を外せば線形計画問題（LP 緩和）になり、$(35, 7.5)$、$z = 142.5$ が出ます。
7.3 ナップサック問題¶
§2.4 の一般形をそのまま書きます。0-1 変数は cat="Binary" です。Python の添字は 0 始まりなので、品物 $j$ は j = 0, …, 5 で、表示するときに 1 を足します。
import pulp
c = [120, 250, 185, 100, 130, 80] # 価値 c_j
a = [10, 21, 16, 9, 12, 7] # 重さ a_j
b = 60 # 容量 b
J = range(len(c)) # 品物の添字（0 始まり）
prob = pulp.LpProblem("knapsack", pulp.LpMaximize)
x = [prob.add_variable(f"x{j + 1}", cat="Binary") for j in J] # x_j ∈ {0, 1}
prob += pulp.lpSum(c[j] * x[j] for j in J) # z = Σ c_j x_j → max
prob += pulp.lpSum(a[j] * x[j] for j in J) <= b # Σ a_j x_j ≤ b
stats = prob.solve(pulp.COIN_CMD(msg=0))
print("状態:", stats.status_str)
print("最適値:", pulp.value(prob.objective))
print("入れる品物:", [j + 1 for j in J if x[j].value() > 0.5])
print("重さの合計:", sum(a[j] for j in J if x[j].value() > 0.5))
状態: Optimal 最適値: 685.0 入れる品物: [1, 2, 3, 5] 重さの合計: 59
§3.1 の全列挙と同じ答え（品物 1, 2, 3, 5、価値 685）です。
7.4 定式化とプログラムの対応¶
| 定式化 | PuLP |
|---|---|
| 最大化／最小化 | pulp.LpProblem(名前, pulp.LpMaximize) ／ pulp.LpMinimize |
| $x_j \in \{0, 1\}$ | prob.add_variable(名前, cat="Binary") |
| $x_j \in \mathbb{Z}_+$ | prob.add_variable(名前, lowBound=0, cat="Integer") |
| $x_j \ge 0$（実数） | prob.add_variable(名前, lowBound=0) |
| $\sum_{j \in J} c_j x_j$ | pulp.lpSum(c[j] * x[j] for j in J) |
| 目的関数 | prob += 式 |
| 制約条件 $\le$、$\ge$、$=$ | prob += 式 <= 右辺、>=、== |
| $\forall i \in I$ | for i in I: の中で prob += … |
| 解く | stats = prob.solve(pulp.COIN_CMD(msg=0)) |
| 状態（最適か） | stats.status_str（"Optimal" なら最適解） |
| 解の値 | x[j].value()、pulp.value(prob.objective) |
$\sum$ は lpSum、$\forall$ は for 文です。第 1 回で学んだ「$\sum$ は足す、$\forall$ は式の束」が、そのままプログラムの構造になります。
7.5 演習問題と PuLP¶
演習問題 1 のビンパッキング問題の定式化と PuLP のプログラムは、別冊『演習問題 1 の解説：ビンパッキング問題』（05_binpack）にあります。演習問題 2 のナップサック問題は 05_pulp.ipynb に入れてあります。自分の分枝限定法の答えを、ソルバーの答えと比べてください。
8. 演習¶
今回のまとめ
- 整数計画問題は、線形計画問題に「変数が整数または 0-1」を加えたもの。LP 緩和の解を丸めても最適解にはならない（§1）。
- 0-1 変数は「する・しない」を表し、$\sum_{j \in J} c_j x_j$ で選んだものの合計が書ける。ナップサック問題（容量の制約 1 本）、ビンパッキング問題（$x_{ij}$ と $y_i$。別冊）（§2）。
- 解き方：全列挙は $2^n$ 通りで不可能、貪欲法は速いが保証なし。LP 緩和の最適値は上界、貪欲法の解の値は下界（§3〜§5）。
- 分枝限定法：分数になった変数で場合分けし、上界 $\le$ 暫定値なら捨てる。終了すれば必ず最適解。ソルバー（PuLP + CBC）はこれに工夫を足したもの（§6〜§7）。
演習問題は別紙（05_problem）にあります。解答用紙に記入して提出してください（解答用紙のみ回収。出席確認を兼ねます）。PuLP のノートブックは配布のみで、提出はありません。
- ビンパッキング問題の定式化（別冊『演習問題 1 の解説：ビンパッキング問題』§1〜§2。解答用紙の表）。荷物 8 個・容器 4 個のデータで、決定変数の意味、目的関数、制約条件を展開した形で書く。容量の制約の右辺は $b_i y_i$、「ちょうど 1 つ」の制約は $= 1$ です。
- 4 品目のナップサック問題（§3〜§6。解答用紙の裏）。全列挙のパターン数、貪欲法の解、LP 緩和の解と上界を求め、分枝限定法を手で実行して最適解を求める。分枝限定法は深さ優先、$x_k = 1$ の側を先、暫定解の初期値は貪欲法の解です。
次回はグラフネットワーク上の最適化（最短路、最小全域木など）です。
参考文献¶
- 福島雅夫『新版 数理計画入門』朝倉書店、2011。
- 梅谷俊治『しっかり学ぶ数理最適化 モデルからアルゴリズムまで』講談社、2020。
付録：用語早見表¶
| 用語 | 意味 | 本資料の節 |
|---|---|---|
| 整数計画問題 | 線形計画問題に、決定変数が整数という条件を加えた問題 | §1.1 |
| 0-1 変数 | $x_j \in \{0, 1\}$。「する（1）・しない（0）」を表す | §1.1、§2.2 |
| 格子点 | 座標がすべて整数の点。整数計画問題の実行可能解 | §1.2 |
| ナップサック問題 | 容量の制約 1 本のもとで、入れる品物の価値の合計を最大にする | §2.1 |
| ビンパッキング問題 | すべての荷物を容器に入れ、使う容器の数を最小にする | 別冊 §2 |
| $x_{ij}$ | 添字が 2 つの 0-1 変数。「$j$ を $i$ に割り当てる」 | 別冊 §1 |
| 全列挙 | すべての組合せ（$2^n$ 通り）を調べる。必ず最適解を出すが、$n$ が大きいと不可能 | §3 |
| 貪欲法 | 比 $c_j / a_j$ の大きい順に入れる。速いが最適とは限らない | §4 |
| LP 緩和 | $x_j \in \{0, 1\}$ を $0 \le x_j \le 1$ にゆるめた線形計画問題 | §5.1 |
| 上界・下界 | 最適値は LP 緩和の最適値以下（上界）、実行可能解の値以上（下界） | §5.3、§5.4 |
| 暫定解 | それまでに見つかった最も良い実行可能解。その値が下界 | §6.1 |
| 分枝 | 分数になった変数 $x_k$ を $x_k = 0$ と $x_k = 1$ に場合分けする | §6.1 |
| 限定（枝刈り） | ノードの上界が暫定解の値以下なら、そのノードを調べない | §6.1 |
| ノード | 変数のいくつかを固定した部分問題 | §6.2 |
| 分枝限定法 | 分枝と限定を繰り返す。終了すれば必ず最適解 | §6 |
| PuLP・CBC | Python のモデリングライブラリと、整数計画ソルバー | §7 |