君たちはどう木、切るか ~板取り問題を列生成法で解こう~

こんにちは。
株式会社WOGOでインターンをしているArashoといいます。

この記事では「板取り問題」(Cutting Stock Problem)という組合せ最適化問題の解法である、列生成法を用いたアプローチを紹介します。

「板取り問題」(Cutting Stock Problem)　とは？

板取り問題とは、定形サイズの母材から所要サイズの製品を切り出す際に、廃材を最小化する切断計画の最適化問題のことです。

オペレーションズ・リサーチにおける板取り問題（いたどりもんだい、英: cutting stock problem）、またはカッティングストック問題とは、定形の母材（ストック（stock）とも。例えばロール紙や板金）から廃材の量が最小になるように特定の大きさの製品群を切り出す問題である。産業上の応用から生じた数学的な最適化問題の1つであり、また計算複雑性理論においてはナップサック問題に還元されるNP困難問題の1つである。整数計画問題として定式化することができる。

板取り問題のwiki より引用

実際に板取り問題は、紙・フィルム・プラスチックのロール、金属・鋼材・パイプ類、さらには布・皮革・テキスタイルなど、多様な産業において資材ロス削減を目的として応用されています。

なお本記事では、1次元に限定して板取り問題を説明していきます。

なぜ板取り問題が難しいのか？

板取り問題は一般的に、NP困難であることが知られています。

板取り問題はつまるところ、「1本の材料をどう切るか」という切断パターンの選択・組合せ問題です。しかし、製品の種類が少し増えただけで、そのパターン数は一気に天文学的に膨れ上がります。そのために、製品の種類、個数が増えてしまうと、最初からすべての切断パターンを列挙して最適化を行うことは計算量の観点から難しくなります。いわゆる組み合わせ爆発と呼ばれる問題の一種ですね。

大まかなオーダー評価

率直に考えると、母材長さ$L$、製品需要を$n$として切断パターン数は$O(L^n)$で増加していきます。
（もちろんこれは上界評価ですが。）

というわけで、取り合い問題は工夫して解かねばなりません。
そこでこの記事では、効率よく板取り問題を解くアルゴリズムの一つである、列生成法を紹介します。

本記事の目的

前置きが長くなりましたが、この記事では

- 板取り問題の概要
- 列生成法のアルゴリズム

を理解してもらうことが目的です。

この記事では、直感的なわかりやすさを優先して説明しているので、数学的に厳密でない部分もあります。厳密な議論は数理最適化の教科書などにあたってもらえればと思います。ご了承ください。

板取り問題の定式化

さっそく板取り問題を定式化していきましょう。
なお具体例も下記に挙げているので、適宜参考にしてください。

木材での具体例

数式のみですとイメージがつきにくいので、木材を具体例にとっていきます。
ここでは、木の母材（定尺材）を小さな板材の製品に切り分ける問題を考えていきます。

製品	長さ	必要本数
A	120	100
B	70	180
C	50	150

製品をつくるための素材は、以下の2種類の母材（定尺材）です。

母材	長さ
S	400
L	1000

目的:
これらの母材を、どのように切って A/B/C を作るかを決め、母材の使用量（＝コスト）を最小化すること

例えば、

400cm の母材で作れる切り出し方の例：

• A×3 → 360cm（余り40cm）
• B×5 + C×1 → 350 + 50 = 400cm（余り0cm）
• A×1 + B×2 + C×2 → 120 + 140+ 100 = 360cm（余り40cm）

1000cmの母材を使う場合には、さらに多くの切り出し方が可能です。

製品、母材の種類が増えるとさらに切り出し方の数は膨大になり、すべての切り出し方を事前に列挙することは現実的ではありません。

製品の情報

$I$ 種類の製品を作ることを考えます。
$i$ 番目の製品は、以下のパラメータを持ちます。

• $w_i$ ：製品幅
• $d_i$ ：需要（必要本数）

木材での具体例

先ほどの木材の例だと、

$w_1 = 120,\; w_2 = 70,\; w_3 = 50$
$d_1 = 100,\; d_2 = 180, \;d_3 = 150$

母材の情報

$K$ 種類の母材があります。
$k$ 番目の母材は、以下のパラメータを持ちます。

• $l_k$ ：長さ
• $c_k$ ：コスト

木材での具体例

先ほどの木材の例だと、

$l_1 = 400, \;l_2 = 1000$
$c_1 = 400, \;c_2 = 1000$

ここでは、$c_k = l_k$ としています。（使った母材の長さ分だけコストがかかる）

これらの情報を受け取って、製品の切り出し方を求めます。

製品の切り出し方

これが板取り問題で求める値となります。

• $J$ ：使う母材の本数
• $k_j \in \{1,2,\cdots,K\}$ ：使用する母材の種類
• $a_{ij} ∈ Z_{\ge 0}$ ：$i$ 番目の製品を何本切り出すか

以下の制約がかかります。

• $∑_{i} w_i a_{ij} \leq l_{k_j} \quad (\mathrm{for} \; j = 1, \cdots, J)$： 長さ制約
• $∑_{j} a_{ij} \geq d_i\quad (\mathrm{for} \;i = 1, \cdots, I)$ ： 需要制約

木材での具体例

400cmの母材から A × 1, B × 2, C × 2 を得る切り出し方$j'$の場合、

$k_{j'}=1,\; a_{1j'} = 1, \;a_{2j'} = 2,\;a_{3j'} = 2$

また長さ制約は
$120*1 + 70*2 + 50*2 = 360 ≤ 400$ → OK

別の切り出し方例：

• A × 3 → 360cm　≤ 400
• B × 5 + C × 1 → 400cm　≤ 400
• C × 8 → 400cm　≤ 400

など、無数の切り出し方がある。

上記が一般的な板取り問題の定式化となります。

以下の列生成法では、簡略化のため、製品の切り出し方をパターンとしてまとめて扱うことにします。

列生成法での決定変数

$$\begin{aligned} x_p \in \mathbb{Z}_{\ge 0} \end{aligned}$$

$p = 1, \ldots, P$ は切断パターンの種類であり、$x_p$ は各切断パターン $p$ を何回使うか（何本の母材をそのパターンで切るか）を表す変数です。
前節の $j$ では、個々の母材の切り出し方での重複を区別していましたが、ここの $p$ では同じ母材種類から同じ切り出し方をするものを同一パターンとしてまとめて考えます。

つまり、需要制約は $x_p$ を使用して

$$\begin{aligned} \sum_{p} a_{ip} x_p &\ge d_i \quad (i = 1, \ldots, I) \end{aligned}$$

とかけます。

木材での具体例

• パターン $q =$「A×1, B×2, C×2」の切り方を 17 回使う場合 → $x_q = 17$
• パターン $r =$「C×8」の切り方を 25 回使う場合 → $x_r = 25$

など。

目的関数

以上の記号を用いて、板取り問題は以下のように定式化できます。

$$\begin{aligned} \min\ & \sum_{p} c_{k_p} x_p \\ \text{s.t.}\quad & \sum_{p} a_{ip} x_p \ge d_i \quad (i = 1, \ldots, I) \\ & x_p \in \mathbb{Z}_{\ge 0} \quad ( p= 1, \ldots, P) \\ & \sum_i w_i a_{ip} \le l_{k_p} \quad (p = 1, \ldots, P) \end{aligned}$$

1つ目の式が最小化したい目的関数であり、コストを最小限にするという意です。
これらの式から分かる通り、これは整数計画問題 (Integer programming, IP)です。

ここで、一度、変数を離散値から連続値へと緩和した、線形計画問題 (Linear Programming, LP)として考えていきます。

便宜上、$x_p$を整数という制約から、正の実数という制約へと緩和したLPを考えていきますが、解を得た後に制約条件に気をつけて整数値に丸め込むなどすれば問題ありません。
なお、最初から整数制約をきちんと組み込んだアルゴリズム手法としては、Branch-and-Priceなどが知られています。

この線形計画問題を効率的に解くアルゴリズムが列生成法です。

列生成法

ここから、列生成法のアルゴリズムについて解説していきます。

列生成法とはざっくりというと、
“必要な切断パターンだけを、必要になったときに後から追加する” という方法です。

これにより、多大な切断パターンを最初から準備する必要がなくなり、実際に役立つパターンだけを扱うことで計算量を劇的に削減できます。

列生成法のサイクルの概要

1. 現在あるパターンだけで LP を解く
   • ここでは「今ある切断パターンをどれだけ使うか」だけを決める
2. より良い切断パターンを探索する
   • 双対問題→ナップサック問題の利用
3. 良いパターンが見つかれば列（パターン）に追加する
4. 列を追加した状態で再び LP を解く
5. 1のステップに戻る。（新しい良い列が見つからなくなるまで、このサイクルを繰り返す）

上記が列生成法のおおまかな流れです。

それでは列生成法のアルゴリズムを理解する上で重要となる、双対問題とナップサック問題についての解説をしていきます。これらを理解している方は、列生成法のアルゴリズムの章までとばして構いません。

双対問題

列生成法において、より良いパターンだけを後から追加すると述べましたが、どのように追加すべきパターンを選ぶのでしょうか？

実は双対変数が鍵を握っているのです。
双対変数とは、双対問題を考えたときに出てくる変数のことです。
双対問題は簡単には、『元の最適化問題を、別の視点（制約側）から見た同等な問題』 といえます。

双対変数の役割のラフな理解

木材の例で説明します。

母材 SとL を切って、製品 A, B, Cを必要本数だけ作る問題を LP として解いたとします。

このとき 双対変数 は、製品 A/ B/ C を “1 本満たすこと” の価値（影響度）を表す重み として現れます。

• Aを1本作る価値 → $π_A$
• Bを1本作る価値 → $π_B$
• Cを1本作る価値 → $π_C$

双対変数 $π_A$ が大きいときとは、直感的にはこのような状況です。

• 製品 A を1本満たすのが難しい
• パターンの中で A を多く含むものが重要
• A を提供できる列（パターン）に価値がある

逆に $π_A$ が小さいときは

• A はすでに十分足りている
• A を追加で作れる列を増やしても、あまり役に立たない

つまり双対変数は、
「今の状況で、どの製品がボトルネックになっているか」
を示す指標と捉えることができます。

定式化

先ほどの式に対応する双対問題を定式化すると

$$\begin{aligned} \max\ & \sum_{i} d_i\, \pi_i \\ \text{s.t.}\quad & \sum_{i} a_{ip}\, \pi_i \le c_{k_p} \quad (p = 1, \ldots, P) \\ & \pi_i \ge 0 \quad (i = 1, \ldots, I) \end{aligned}$$

$π_i$ は「製品 $i$ の需要制約」に対応する双対変数です。

ここで双対制約　$∑_{i} a_{ip} π_i ≤ c_{k_p}$ を変形すると、

$$\begin{aligned} c_{k_p} - ∑_{i} a_{ip} π_i ≥ 0 \end{aligned}$$

この左辺を　$\text{reduced\_cost}(p) = c_{k_p} - ∑_{i} a_{ip} π_i$ と定義します。

reduced_costとは？

$π_i$ は「製品 $i$ を 1 本満たすことの価値」でした。


すると、　$∑_{i} a_{ip} π_i$　は、パターン $p$ を使うことで得られる製品の価値の合計と解釈できます。

$\text{reduced\_cost}$の式のそれぞれの項は、

$C_{k_p}$ ：母材 $k_p$ を 1 本使うコスト
$∑_{i} a_{ip} π_i$ ：その母材から切り出した製品の価値の合計

なので、$\text{reduced\_cost}(p)$ = (コスト) - (価値)　と解釈できます。


つまり、

• $\text{reduced\_cost}(p) < 0$ → コストの割に価値が低い、"おいしくない" パターン
• $\text{reduced\_cost}(p) = 0$ → ちょうど釣り合っているパターン
• $\text{reduced\_cost}(p) > 0$ → 価値がコストを上回っている 、"おいしい" パターン

というイメージです。

列生成法の双対問題では、
$\text{reduced\_cost}(p)$ が負となるような、より良い切断パターン = "おいしい"パターン を見つけ出すのが目的です。

なぜ双対問題を考えることでうまくいくのかに関して、さらに厳密に知りたい方は双対定理（参考）について調べてみてください。

ナップサック問題

再度ここで、$\text{reduced\_cost}(p)$の定義を見てみましょう。

$$\begin{aligned} \text{reduced\_cost}(p) = c_{k_p} - ∑_{i} a_{ip} π_i \end{aligned}$$

これが負であるパターンを見つける　ということはすなわち、
符号をひっくり返した $∑_{i} a_{ip} π_i - c_{k_p}$　を最大化する問題と同じになります。

また、ここでパターン$p$ は母材の長さ制約 $∑_{i} w_i a_{ip} ≤ L_{k_p}$ を満たす必要があることに注意です。

つまり、

$$\begin{aligned} \max\ & \sum_{i} a_{ip}\, \pi_i \;-\; c_k \\ \text{s.t.}\quad & \sum_{i} w_i\, a_{ip} \le L_{k_p} \\ & a_{ip} \in \mathbb{Z}_{\ge 0} \end{aligned}$$

これはすなわち、

価値 $π_i$, 重さ $w_i$ の製品を
容量 $L$ のリュックに詰めて
価値の合計を最大化する

という、ナップサック問題と同じ構造であることがわかると思います。

列生成法のアルゴリズム

双対問題、そしてナップサック問題が出てくる理由を理解できました。
それでは、列生成法のアルゴリズムを詳しく解説していきます。

step 0. 初期パターン集合 $P_0$ を用意する

簡単なパターンでOKです。
全ての製品を詰めるなどして、適当に用意してください。

step 1. 今あるパターンで線形緩和されたLPを解く

$$\begin{aligned} \min\ & \sum_{p \in P} c_p\, x_p \\ \text{s.t.}\quad & \sum_{p \in P} a_{ip}\, x_p \ge d_i \quad (i = 1, \ldots, I) \\ & x_p \ge 0 \end{aligned}$$

ここで、需要制約から双対変数 $π_i$ を得ます。
（一般的なソルバーでは、双対変数も同時に計算してくれるものが多いです。）

step 2. 双対変数 $π_i$ を使って新しいパターンを探す

$$\begin{aligned} \max\ & \sum_{i} \pi_i\, a_i \\ \text{s.t.}\quad & \sum_{i} w_i\, a_i \le L_k \\ & a_i \in \mathbb{Z}_{\ge 0} \end{aligned}$$

このナップサック問題を解きます。

step 3. reduced_cost を計算し、パターンを追加

step 2で得られた解 ( $a_1,a_2,...,a_m$ )に対して、

$$\begin{aligned} \text{reduced\_cost} = c_k - \sum_i \pi_i a_i \end{aligned}$$

を計算。

$\text{reduced\_cost} < 0$ → パターンを $P$ に追加
$\text{reduced\_cost} ≥ 0$ → 追加不要

Step 4. パターン集合 $P$ を更新して Step 1 に戻る

再度Step 1から繰り返す。
追加すべきパターンがなくなったら、つまり全ての$\text{reduced\_cost} ≥ 0$となったら、列生成終了。

最終的に制約条件に気をつけて、整数値に丸め込みほぼ最適な解を得る。

このように、動的に列を増やしながら最適解を探していくので列生成法というのですね。

豆知識：板取り問題の歴史

ソ連の数学者レオニード・カントロヴィチが、1939年に切断問題(=板取り問題)を数学的に定式化しました。戦後1951年頃にはザルガラーらとともに、計算機の普及以前ではありましたが、切断における資材の経済的利用を線形計画法の枠組みで数学的に解く方法を提案しました。この手法は、のちの “列生成法 (column generation)” の先駆けとみなされています。またカントロヴィチは資源配分全般についての理論的業績により、1975年にノーベル経済学賞を受賞しました。

ここからも、板取り問題が産業上とても重要な問題であることがわかりますね。

実際に試してみた

ここまでで、列生成法のアルゴリズムを理解していただけたと思います。
実際に他の代表的なアルゴリズムと比べて、どの程度高速に、良い解を見つけることができるのか、を検証してみました。

比較するアルゴリズム

ここでは、
・DP
・分枝限定法
・列生成法
の3つのアルゴリズムを比較しました。
（DPと分子限定法に関する説明はここでは行いません。それぞれ適当な記事や教科書を参考にしてください）
実際にお手元の環境でコードを実行していただけます。
https://github.com/Arashooo/stock-allocation

以下の異なる4パターンで試しました。

パターンA

簡単なパターン

母材

$k$	$l_k$	$c_k$
1	500	500
2	1000	1000
3	1500	1500

製品

$i$	$w_i$	$d_i$
1	50	50
2	100	40
3	150	30
4	200	20

パターンB

母材が長いパターン

母材

$k$	$l_k$	$c_k$
1	10000	10000
2	20000	20000
3	30000	30000

製品

$i$	$w_i$	$d_i$
1	100	100
2	150	90
3	200	80
4	250	70

パターンC

製品タイプが多いパターン

母材

$k$	$l_k$	$c_k$
1	1000	1000
2	1500	1500
3	2000	2000
4	2500	2500
5	3000	3000

製品

$i$	$w_i$	$d_i$
1	100	200
2	150	180
3	200	160
4	250	140
5	300	120
6	350	100
7	400	90
8	450	80
9	500	70
10	550	60
11	600	50
12	650	40
13	700	30
14	750	20
15	800	10

パターンD

母材が長く、製品タイプも多いパターン

母材

$k$	$l_k$	$c_k$
1	6000	6000
2	9000	9000
3	12000	12000

製品

$i$	$w_i$	$d_i$
1	500	300
2	750	250
3	1000	200
4	1250	180
5	1500	150
6	1750	120
7	2000	100
8	2250	80
9	2500	50

結果

結果は以下のとおりです。
表内にて、「-」は計算量が膨大で解が得られなかったことを示しています。
（実装ではstack overflow回避のために、状態数が膨大に増えた際に打ち切るようにしています。）

パターンA:

アルゴリズム	cost	time [sec]
DP	15000	1.2328
分枝限定法	15000	6.1363
列生成法	15000	0.3480

パターンB:

アルゴリズム	cost	time [sec]
DP	60000	10.0333
分枝限定法	60000	2.5600
列生成法	60000	0.0133

パターンC:

アルゴリズム	cost	time [sec]
DP	-	-
分枝限定法	-	-
列生成法	426000	0.0155

パターンD:

アルゴリズム	cost	time [sec]
DP	-	-
分枝限定法	-	-
列生成法	1704000	0.0159

見てわかるとおり、列生成法はDPや分枝限定法に比べて実行速度がはやく、また大規模なケースでも十分に有用であることがわかります！

最後に

本記事では、板取り問題についての紹介、そして板取り問題が列生成法という手法で解けることを解説してきました。
また実際に、いくつかのアルゴリズムと比べてみることで、その強力さを実感していただけたのではと思います。

板取り問題は産業上、非常に多くの場面で出てくる問題です。板取り問題に直面した際には、ぜひこの記事を参考にしてみてください。

また列生成法に関して非常に参考になる記事として、梅谷先生の記事や、宮本先生の記事があります。ぜひ併せて読んでみてください。堅実な理解につながると思います。