いつものごとくChatGPTにプログラムを書いてもらった。最強・最凶クラスのアルゴリズムが出来たので、そのフローを記録したい。
引用 ChatGPT
■Cutting Stock Problem / 組合せ最適化 / 歩留まり最大とパターン種類最小のアルゴリズム設計【前編】
この記事は、cutting stock problem（カッティングストック問題）を、単なる「切断パターンの話」ではなく、組合せ最適化、数理最適化、離散最適化、operations research、manufacturing optimization、resource allocation、planning optimization の一例として説明するものです。
今回の目的ははっきりしています。
第1目的：
歩留まり最大化= 総損失最小化= 需要を等式で満たす条件の下で、総使用母材長最小化
第2目的：
上の最良歩留まりを固定したまま、使用パターン種類数を最小化
ここで重要なのは、「最小本数を先に固定しない」ことです。
本稿のアルゴリズムでは、母材本数は結果として表示しますが、主目的ではありません。
まず材料損失を極小化し、そのうえで現場が扱いやすいようにパターン種類数を減らします。
この目的順を明示しないと、アルゴリズム説明も比較評価も崩れます。
English summary:
This article explains a reproducible cutting stock algorithm for researchers, engineers, mathematicians, and practitioners.
The algorithm is lexicographic.
Priority 1 is maximum yield, equivalently minimum total loss.
Priority 2 is minimum number of distinct cutting patterns among all best-yield solutions.
The stock count is reported, but it is not the primary objective in this version.
■1. なぜこの問題は cutting stock problem だけの話ではないのか
カッティングストック問題は、より大きな世界では組み合わせ最適化、離散最適化、数理計画法、工業工学、生産計画、梱包、配分、パターン生成、および複雑なシステム意思決定 combinatorial optimization, discrete optimization, mathematical programming, industrial engineering, production planning, packing, allocation, pattern generation, and complex system decision making の一部です。
たとえば、次のような問題と構造が近いです。
・bin packing
・knapsack problem
・resource allocation
・crew or machine planning
・lot sizing
・scheduling with material loss
・column generation based planning
・pattern selection under exact demand constraints
つまり、「材料をどう切るか」だけでなく、
「有限資源の下で、需要を満たし、損失を減らし、運用負担も抑える」
という広い設計問題の1つとして見たほうが本質が掴みやすいです。
English note:
If you search for cutting stock, column generation, branch-and-price, discrete optimization, mixed integer programming, or industrial planning, you are often looking at the same family of ideas.
The details differ, but the core structure is similar:
generate feasible patterns, satisfy demand, reduce waste, and keep the operational plan manageable.
■2. 本稿で扱う最終目的
本稿の target は、次の一文で言い表せます。
「まず総損失を最小にして歩留まり最良の世界を確定し、その世界の中だけでパターン種類数を最小化する」
この一文を、実装可能な形へ落としたものが本アルゴリズムです。
ここでいう総損失は、単なる末尾残りではありません。
本稿では loss を次の3つに分けます。
1. 純残尾材
2. ノコ歯損失
3. 左右端切り損失
現場では全部まとめて「端材」と呼びがちですが、アルゴリズム設計と結果解釈のためには分けたほうが良いです。
English summary:
Total loss is decomposed into:
1. tail trim,
2. kerf loss,
3. edge trim.
This decomposition makes the model physically meaningful and easier to interpret.
■3. 入力仕様
再現性を高めるため、最初に input format を固定します。
本稿で想定する入力は次の通りです。
tei:無限在庫の定尺材長さ
zai:有限在庫材の長さと本数
noko:ノコ歯厚み
hasi:左右端切り量
cut:製品長さと必要数
例:
tei 5550
zai 0 0
noko 3
hasi 3 3
cut
1000 70
835 81
720 89
660 105
640 152
570 54
440 27
420 89
読み取り規則は次です。
・tei は無限在庫材
・zai は有限在庫材
・noko は 0 以上の整数1個
・hasi は 0 以上の整数2個
・cut は 製品長さ 必要数 のペア列
・同じ製品長が複数回出たら需要は合算
・0 や負値は材料・需要として採用しない
・材料長より長い製品長があれば infeasible とみなす
English summary:
Input fields:
tei = standard stock with unlimited quantity
zai = finite stock with explicit quantity
noko = kerf width
hasi = left and right edge trim
cut = item length and demand
Repeated item lengths are merged by summing demand.
■4. 切断条件の数式化
1本の母材から k 個の製品を切り出すとき、実際に消費される長さは
consumed=sum(item_length_i × count_i)+noko × (k - 1)+hasi_left+hasi_right
です。
ここで
k = sum(count_i)
です。
また、純残尾材は
tail_trim = stock_length - consumed
です。
そして、総損失は
total_loss=stock_length-sum(item_length_i × count_i)
です。
この total_loss は
tail_trim + kerf_loss + edge_trim
に一致します。
English explanation:
If one stock bar produces k pieces, then the physically consumed length is:
sum(piece_length × count) + kerf × (k - 1) + left_edge_trim + right_edge_trim.
A pattern is feasible only if consumed <= stock_length.
■5. 実効長変換
ノコ歯と端切りをそのまま扱うと、pricing DP や列挙の状態遷移がやや煩雑になります。
そこで、本稿では exact な代数変換を使います。
effective_item_length = item_length + noko
effective_stock_length = stock_length - hasi_left - hasi_right + noko
すると feasibility は
sum(effective_item_length_i × count_i) <= effective_stock_length
に変わります。
これは近似ではなく、元の条件と等価です。
最後の1ピースには余分なノコ歯が不要であることを、右辺の +noko がちょうど打ち消します。
English summary:
This transformed-length representation is exact, not heuristic.
It allows the pricing DP and full pattern enumeration to remain simple bounded-capacity procedures.
■6. パターンの定義
1つの pattern は(stock_idx, counts)
で持ちます。
ここで
stock_idx は使用する母材種別
counts は各製品長について何本切るかの整数ベクトル
です。
実務上は、この pattern から次の量を計算できるようにします。
・製品長合計
・ノコ＋端切損失
・消費長
・純残尾材
・総損失
この5つを pattern 単位で取れるようにしておくと、アルゴリズムの途中評価と最終表示が楽になります。
English note:
A pattern is not only a count vector.
It should also carry derived measures such as used product length, process loss, consumed length, tail trim, and total loss.
■7. 全体構成
アルゴリズム全体は大きく二段です。
Phase 1:
Column generation で候補パターン集合を育てる。
Restricted Master Problem を解き、pricing DP で改善列を見つけて追加する。
途中で整数化を入れ、実行可能解を更新する。
Phase 2:
候補集合の上で 2-pass MIP を解く。
Pass 1 で総使用母材長最小を解き、歩留まり最適値を確定する。
Pass 2 でその最適総使用母材長を固定し、パターン種類数を最小化する。
English overview:
Phase 1 is constructive and exploratory.
Phase 2 is selective and certifying.
This separation is important because it preserves the lexicographic objective order.
■8. なぜ weighted sum ではなく 2-pass なのか
よくある書き方は
min trim + epsilon × types
です。
しかし、この方法には問題があります。
・epsilon の設計に依存する
・数値スケールが不安定になりやすい
・目的順が説明しにくい
・ソルバーが微小係数つきの binary を同時に意識するため重くなりやすい
本稿では、目的順を絶対に崩したくありません。
そこで 2-pass の lexicographic optimization を採用します。
Pass 1:
総損失だけを最適化
Pass 2:
Pass 1 の最適値を固定し、その中で種類数だけを最適化
English summary:
The algorithm uses lexicographic optimization, not a single weighted objective.
This is cleaner, more reproducible, and easier to explain.
■9. Phase 1 の Restricted Master Problem
Phase 1 の master は、現在持っている候補パターンだけを使って需要を満たす LP または MIP です。
変数:
x_j = pattern j を何本使うか
制約:
各製品 i について
sum_j a_ij x_j = demand_i
有限在庫材 s があるなら
sum_{j in stock s} x_j <= cap_s
目的:
min sum_j stock_length_j × x_j
需要が等式なので、総製品長は固定です。
したがって、総使用母材長を最小にすることは総損失最小と同じです。
English explanation:
Because demand is enforced as equality, total product length is constant.
Therefore minimizing total stock length is equivalent to minimizing total loss and maximizing yield.
■10. 初期列の作り方
再現性のため、初期列ルールを固定します。
本稿では次の5系統を seed patterns とします。
1. 単品1本
2. 単品最大詰め
3. 需要大きい順 greedy
4. 長尺優先 greedy
5. pair greedy
この初期列は厳密解ではありません。
しかし、列生成の立ち上がりを良くし、早い段階で意味のある実行可能解を得るために非常に重要です。
とくに pair greedy は、長い材料の中で「大きい物を先に詰め、残りを別製品で埋める」形になりやすく、端材の少ない pattern を初期 pool に入れやすくなります。
English summary:
Initial columns are a practical engineering choice.
They do not determine the final optimum, but they strongly affect startup quality and runtime.
■11. pricing 問題の定義
RMP を解くと dual 値が得られます。
その dual を使い、「新しく追加すべき pattern があるか」を調べるのが pricing subproblem です。
各母材長について、dual 価値最大の pattern を bounded DP で探します。
入力:
・stock length
・item lengths
・demands
・dual values
・kerf and edge trim spec
出力:
・dual 価値最大 pattern
・その使用長
・reduced cost
本稿の reduced cost は
rc = stock_length - dual_value - stock_dual
です。
rc が負なら、その pattern は master に追加する価値があります。
English explanation:
The pricing dynamic program searches for a pattern with negative reduced cost.
The dual tie-break matters.
If two patterns have the same dual value, the implementation should prefer the one with larger consumed length, because it tends to reduce bad trim patterns in the pool.
■12. pricing DP の tie-break
ここは記事で省略されがちですが、再現性のために書きます。
dual 価値が同じなら、used length が大きい pattern を優先します。
理由:
同じ dual 価値でも、短くて端材が大きい pattern を選び続けると、列プールの質が悪くなるためです。
この tie-break は理論の主役ではありません。
しかし実装の挙動には効きます。
English note:
Tie-breaking is not cosmetic.
It changes the pool quality and therefore changes the practical behavior of the algorithm.
■13. Phase 1 の停止と途中整数化
Phase 1 は LP を解いて列を足すだけでは終わりません。
一定反復ごと、または一定本数以上の新列が増えたタイミングで、現在の列プール上の integer RMP を解きます。
目的:
・今ある列だけで作れる実行可能解を得る
・best incumbent を更新する
・Phase 2 の MIP start に使う
典型設定例:
・CHECK_INT_EVERY = 8
・CHECK_INT_MIN_NEW_COLS = 24
列追加が止まり、十分な改善がなければ Phase 1 を終了します。
English summary:
Integer restricted master solves during column generation provide incumbents.
These incumbents are extremely useful later as MIP starts for the exact phase.
■14. 前編のまとめ
前編の要点は次の通りです。
・目的順は「総損失最小」→「種類数最小」
・ノコ歯と端切りは実効長変換で正しく扱う
・Phase 1 は column generation + pricing DP
・初期列、tie-break、途中整数化まで固定すると再現性が高まる
後編では、PatternTable、Phase 2 Pass 1、Phase 2 Pass 2、fast モードと exact モード、Big-M 上限、MIP start、結果の読み方まで具体化します。
English closing:
Part 1 fixed the objective, input format, transformed feasibility rule, initial columns, pricing DP, and the role of intermediate integer restricted master solves.
Part 2 will explain the exact two-pass MIP layer in a more reproducible way.
検索キーワード / SEO:
カッティングストック問題
組合せ最適化
数理最適化
離散最適化
列生成法
分枝価格法
動的計画法
製造最適化
歩留まり改善
端材最小化
パターン種類最小化
複雑系解析
complex systems optimization
cutting stock problem
combinatorial optimization
mathematical optimization
operations research
column generation
pricing dynamic programming
yield maximization
pattern minimization
manufacturing optimization
■15. 記号とデータ構造
再現実装しやすいように、記号も固定します。
s:母材種別 index
i:製品種別 index
j:pattern index
L_s:母材長
l_i:製品長
d_i:需要
a_ij:pattern j に含まれる item i の本数
x_j:pattern j の使用本数
noko:kerf width, saw thickness
h_left, h_right:left and right edge trim
counts_j:pattern j の count vector
pattern j が使う piece 本数は
k_j = sum_i a_ij
です。
そして
製品長合計:
used_product_len_j = sum_i l_i a_ij
工程損失:
process_loss_j = noko × (k_j - 1) + h_left + h_right
ただし k_j = 0 の empty pattern は使わない
消費長:
consumed_len_j = used_product_len_j + process_loss_j
純残尾材:
tail_trim_j = L_s - consumed_len_j
総損失:
total_loss_j = L_s - used_product_len_j
となります。
English note:
The model uses an explicit separation between product length, process loss, consumed length, and final tail trim.
This is useful for both optimization and reporting.
■16. データの読み込みで迷わないための規則
実際に他人が実装するときは、ここが意外とブレます。
そこで parsing rules を明示します。
ルール1:
行頭・行末の空白は無視する
ルール2:
タブは空白と同じ扱いにする
ルール3:
全角空白も通常空白へ寄せる
ルール4:
# 以降はコメントとして捨てる
ルール5:
tei, zai, noko, hasi, cut は小文字化して判定する
ルール6:
section をまたぐときは、その後の数値列をその section に属するとみなす
ルール7:
同一長さの cut は demand を合算する
ルール8:
材料長が1つも無ければエラー
ルール9:
最大材料長を超える製品長があればエラー
ルール10:
noko は 0 以上の整数1個、hasi は 0 以上の整数2個
この程度まで書いておくと、別環境の人でも再現しやすくなります。
English summary:
A reproducible algorithm description must also describe its parser behavior.
Whitespace, comments, repeated cut lengths, and validation rules matter.
■17. 有限在庫材と無限在庫材
本稿では有限在庫材と無限在庫材を同時に扱えます。
StockType は
(length, cap, name)
を持ちます。
・cap = None なら unlimited stock
・cap = integer なら finite stock
Master problem では、
有限在庫材だけ
sum_{j in stock s} x_j <= cap_s
を追加します。
この設計は simple ですが、実務では強いです。
たとえば定尺材は無限、端材置場の在庫だけ有限、という混在が自然に書けます。
English note:
Unlimited stock and finite stock can coexist in the same model.
This is very practical in industrial settings.
■18. 初期列5系統の具体像
ここは検索流入してきた実務家の方にも分かりやすいように、言葉で具体化します。
1. 単品1本
各製品を1本だけ切る pattern。
目的は可行性の保険です。
2. 単品最大詰め
同じ製品だけで、入るだけ詰める pattern。
長い製品や需要の大きい製品で効きます。
3. 需要大きい順 greedy
需要の大きいものから順に詰める。
「足りなくなりやすい製品」を先に入れる seed です。
4. 長尺優先 greedy
長いものから順に詰める。
大物優先の詰め方を初期 pool に入れる役目です。
5. pair greedy
ある item を起点にして残りを埋める。
相性の良い組合せを早めに見つけるための seed です。
初期列は厳密解ではありません。
ただし、列生成がゼロから始まるのを防ぐために重要です。
English summary:
The initial pool is intentionally heterogeneous.
It includes feasibility-oriented, demand-oriented, length-oriented, and combination-oriented seeds.
■19. pricing DP の実装の考え方
bounded knapsack DP の実装では、以下を持ちます。
入力:
・残容量
・各 item の effective length
・各 item の demand upper bound
・dual value
状態:
dp_val[w] = 容量 w で達成できる最大 dual value
dp_pat[w] = そのときの count vector
各 item i ごとに
extra_cap_i の範囲で個数を試し、new_val と new_pat を更新します。
最後に、全 w について
価値最大を探し、同価値なら consumed length 最大を選びます。
ここで注意したいのは、DP の「容量」は effective capacity であり、表示用の used length や trim は元の長さ系で計算する点です。
ここを混同すると、後で結果表示がずれます。
English explanation:
The DP capacity lives in transformed effective length space.
The final reporting values must be converted back to the original physical interpretation.
■20. reduced cost と dual の読み方
RMP を解くと、需要制約の dual と有限在庫制約の dual が得られます。
pricing 側では、それらを用いて
reduced_cost = stock_length - dual_value - stock_dual
を計算します。
ここで dual_value は pattern によって回収できる demand-side の価値です。
stock_dual は有限在庫の希少性を表します。
reduced cost が負であれば、その列を追加する価値があります。
English summary:
The pricing step interprets the master duals as pattern value signals.
A negative reduced cost means the current restricted master is missing a useful pattern.
■21. 列生成反復の擬似コード
再現性重視のため、Phase 1 の流れを擬似コードで書きます。
initialize pattern pool with 5 seed families
best incumbent = integer solve on initial pool if possible
repeat:
solve restricted master LP
read duals
for each stock type:
solve pricing DP and related forced variants
collect negative reduced-cost patterns
add up to MULTI_COL_PER_ITER patterns
if checkpoint condition holds:
solve integer restricted master on current pool
update best incumbent
until no useful column is found for enough rounds
この程度まで書くと、他人が別言語へ移植しやすくなります。
English pseudocode:
initialize pool
loop:
solve LP
run pricing
add profitable patterns
periodically solve integer restricted master
stop when improvement stalls
■22. checkpoint 条件の意味
なぜ一定反復ごとに integer RMP を解くのか。
理由は3つです。
1. 現時点での実行可能計画が欲しい
2. best incumbent を更新したい
3. Phase 2 用の MIP start が欲しい
設定例として
CHECK_INT_EVERY = 8
CHECK_INT_MIN_NEW_COLS = 24
のような値を置いておくと、過度な整数化を避けつつ seed を育てられます。
English note:
Checkpoint integer solves balance two needs:
not solving too often, and not waiting too long for a good incumbent.
■23. Phase 1 の出力に含めるべき指標
Phase 1 の記事では、単に「良い解が出た」では不十分です。
少なくとも次の値は表示したいです。
・母材本数
・パターン種類数
・総損失
・ノコ＋端切
・純残尾材
・総使用母材長
・歩留まり
これにより、
「歩留まりが良いのか」
「工程損失が多いのか」
「純粋に残りが多いのか」
が見えるようになります。
English summary:
A reproducible report must define its metrics, not only its algorithm.
■24. このアルゴリズムがつながる周辺分野
SEO だけのためではなく、本質的にも、次の分野はかなり近いです。
・exact cover with structured patterns
・set partitioning / set covering variants
・hierarchical planning
・inventory-constrained cutting
・resource-constrained pattern selection
・mixed integer optimization in manufacturing
・industrial analytics
・decision science
・complex systems planning
・operations research in production engineering
このように広く見ると、「カッティングストックだけをやっている」のではなく、「構造化された候補集合から目的順を守って選ぶ」問題を扱っていると理解できます。
English note:
This viewpoint helps connect the article to broader research and engineering communities.
■25. 前編のFAQ
Q1. 需要を >= にして余剰を許してもよいですか。
A1. 可能ですが、本稿では demand equality にして total product length を固定し、歩留まり解釈を明快にしています。
Q2. noko = 0, hasi = 0 にするとどうなりますか。
A2. 単純な cutting stock に戻ります。実効長変換も自然に元へ戻ります。
Q3. pair greedy は必須ですか。
A3. 理論的必須ではありませんが、初期 pool の質を上げる practical trick として有効です。
Q4. pricing DP は 0-1 knapsack ですか。
A4. いいえ。需要上限を持つ bounded knapsack 型です。
Q5. なぜ dual tie-break で長く使う pattern を優先するのですか。
A5. 同価値でも短くて端材の悪い列を増やしすぎないためです。
Q6. Branch-and-Price そのものですか。
A6. Phase 1 は column generation 的です。後半は full or restricted candidate set 上の 2-pass MIP です。
English FAQ:
Is this a pure branch-and-price implementation?
Not exactly in the strict textbook sense for the whole algorithm.
Phase 1 is column-generation-based, and Phase 2 is a two-pass MIP on a candidate set.
■26. 前編の結論
前編では、アルゴリズムの「入口」を固定しました。
・何を最適と呼ぶか
・入力をどう読むか
・損失をどう数えるか
・ノコ歯と端切りをどう feasibility に入れるか
・Phase 1 をどう回すか
ここが曖昧だと、後編の exact phase をどれだけ綺麗に書いても、別物が出来上がります。