いつものごとくChatGPTにプログラムを書いてもらった。最強・最凶クラスのアルゴリズムが出来たので、そのフローを記録したい。AIで再現できるようにした。ソルバーはHiGHSを使用
引用 ChatGPT
この記事は、cutting stock problem（カッティングストック問題）を、単なる切断パターン作成ではなく、組合せ最適化、数理最適化、離散最適化、列生成法、動的計画法、混合整数計画、製造最適化、資源配分最適化、complex systems optimization の一例として整理し、AI が Python コードとして再現可能なレベルまで仕様化して示すものです。
目的は明確です。
第一目的：
歩留まり最大化
= 総損失最小化
= 需要を等式で満たす条件の下で、総使用母材長最小化
第二目的：
第一目的で得た最適歩留まりを固定したまま、使用パターン種類数を最小化
ここで重要なのは、本稿の主目的が「母材本数最小化」ではないことです。
母材本数は結果として併記しますが、最上位目的ではありません。
最初に材料損失を極小化し、そのうえで現場が扱いやすいようにパターン種類数を減らします。
この目的順を崩さないため、本稿では weighted sum ではなく 2-pass の辞書式最適化を採用します。
English summary:
This post presents a reproducible algorithm for the cutting stock problem.
Priority 1 is maximum yield, equivalently minimum total loss.
Priority 2 is the minimum number of distinct cutting patterns among all best-yield solutions.
The stock count is reported, but it is not the primary optimization objective in this version.
The algorithm is designed so that an AI can reproduce it as Python code from the specification.
■1. この問題の数理学上の位置づけ
この問題は cutting stock problem そのものですが、同時に次の分野にも属します。
・組み合わせ最適化 ・離散最適化 ・数理最適化 ・オペレーションズリサーチ ・混合整数計画法 ・列生成法 ・価格設定動的計画法 ・資源配分 ・産業工学 ・製造分析 ・複雑系最適化
・combinatorial optimization
・discrete optimization
・mathematical optimization
・operations research
・mixed integer programming
・column generation
・pricing dynamic programming
・resource allocation
・industrial engineering
・manufacturing analytics
・complex systems optimization
つまり「材料を切る問題」であると同時に、「有限資源の下で、需要を満たし、損失を減らし、現場運用の複雑さも減らす」問題です。
このため、研究者、数学者、実務家、製造エンジニア、最適化エンジニア、AI 実装者のどこから読んでも意味のある構造になっています。
■2. このアルゴリズムの有用性
このアルゴリズムが有用なのは、単に高歩留まりの解を出すからではありません。
有用性は次の4点にあります。
1.歩留まりを最優先にしているため、材料ロスの評価軸が明確です。
2.ノコ歯厚みと左右端切りをモデルに組み込んでいるため、現場条件に近い解が得られます。
3.最良歩留まりの世界の中でパターン種類数を減らすため、段取り、教育、検査、指示票、取り違え防止に効きます。
4.列生成法、pricing DP、2-pass MIP という分解により、アルゴリズムの役割分担が明快で、AI にコードを再現させやすいです。
English summary:
The method is useful because it is not only material-efficient, but also operationally efficient.
It models kerf and edge trim explicitly, preserves the objective hierarchy exactly, and is structured in a way that is reproducible by AI-assisted coding.
■3. 入力仕様
AI が再現実装しやすいように、入力形式を固定します。
セクションは以下の5つです。
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 は unlimited stock
・zai は finite stock
・noko は 0 以上の整数1個
・hasi は 0 以上の整数2個
・cut は 製品長さ 必要数 のペア列
・同じ製品長が複数回出たら需要は合算
・材料長より長い製品長があれば infeasible とする
・0 や負値は採用しない
■4. 切断条件の定式化
1本の母材から k 個の製品を切り出すとき、消費長は次式で与えます。
consumed_length=
sum(product_length_i × count_i)
+ noko × (k - 1)
+ hasi_left
+ hasi_right
ここでk = sum(count_i)
です。
純残尾材は
remaining_tail = stock_length - consumed_length
総損失は
total_loss = stock_length - sum(product_length_i × count_i)
です。
総損失は、
・pure tail trim
・kerf loss
・edge trim
に分解できます。
■5. 実効長変換
ノコ歯と端切りをそのまま扱うと 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
となります。
これは近似ではなく、元の条件と等価です。
したがって、pricing DP や全列挙は bounded knapsack 型の枠組みをほぼそのまま使えます。
English summary:
The transformed effective-length representation is exact.
It keeps the algorithm simple without changing the physics of the cutting process.
■6. アルゴリズム全体構成
アルゴリズムは二段構成です。
Phase 1:
列生成法で有望な pattern pool を育てる。
Restricted Master Problem を解き、pricing DP で改善列を追加する。
途中で integer restricted master を解き、実行可能解を育てる。
Phase 2:
2-pass の MIP を解く。
Pass 1 で総使用母材長最小 = 歩留まり最大を確定する。
Pass 2 で Pass 1 の最適総使用母材長を固定し、パターン種類数を最小化する。
これにより、目的順が崩れません。
■7. Phase 1 の仕様
目的：
候補パターン集合を育てること。
変数：
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
需要制約が等式なので、総製品長は固定です。
したがって、総使用母材長最小は総損失最小と同義です。
■8. 初期パターンの生成仕様
初期列は次の5系統で生成します。
1. 単品1本
2. 単品最大詰め
3. 需要大きい順 greedy
4. 長尺優先 greedy
5. pair greedy
目的：
列生成の立ち上がりを良くし、早い段階で意味のある実行可能解を得ること。
注記：
初期パターンは最適解ではないが、列生成の seed として重要です。
■9. pricing DP の仕様
目的：
各 stock type について negative reduced cost を持つ新パターンを探すこと。
入力：
・stock length
・item lengths
・demands
・dual values
・kerf / edge trim spec
出力：
・dual 価値最大 pattern
・その used length
・reduced cost
reduced cost は次式で計算します。
rc = stock_length - dual_value - stock_dual
rc < 0 の pattern は追加候補とします。
tie-break：
同じ dual value なら used length が大きい pattern を優先する。
理由：
同価値でも端材の悪い列ばかり増えることを防ぐため。
■10. Phase 1 の途中整数化
一定反復ごと、または一定数以上新列が増えたときに、現在の列プール上で integer restricted master を解きます。
目的：
・現時点の実行可能解を得る
・best incumbent を更新する
・Phase 2 の MIP start に使う
これは単なる dual 計算ではなく、後半の exact phase の土台を育てる工程です。
■11. Phase 2 の仕様
Phase 2 は 2-pass に分けます。
weighted sum は使いません。
理由：
・目的順が曖昧になる
・epsilon の設計に依存する
・再現性が落ちる
・ブログや仕様書で説明しにくい
■12. Phase 2 Pass 1 の仕様
変数：
x_j ∈ Z_+
制約：
(1) 需要等式
sum_j a_ij x_j = demand_i
(2) 有限在庫制約
sum_{j in stock s} x_j <= cap_s
目的：
min sum_j stock_length_j × x_j
役割：
best yield world を確定すること。
■13. Phase 2 Pass 2 の仕様
変数：
x_j ∈ Z_+
z_j ∈ {0,1}
制約：
(1) 需要等式
sum_j a_ij x_j = demand_i
(2) 有限在庫制約
sum_{j in stock s} x_j <= cap_s
(3) Pass 1 の最適総使用母材長を固定
sum_j stock_length_j × x_j = optimal_total_stock_length
(4) linking constraints
x_j <= U_j z_j
目的：
min sum_j z_j
役割：
最良歩留まりの世界の中で、パターン種類数最小を実現すること。
English summary:
Pass 1 determines the best total stock length.
Pass 2 fixes that value and minimizes the number of active patterns.
This is lexicographic optimization, not an approximation.
■14. Big-M 上限 U_j の仕様
U_j は pattern j ごとの安全な上限です。
少なくとも次を使います。
U_j <= min_i ceil(demand_i / a_ij)
有限在庫材ならさらに
U_j <= cap_s
Pass 2 ではさらに
U_j <= floor(optimal_total_stock_length / stock_length_j)
を併用できます。
■15. fast mode / exact mode の位置づけ
fast mode：
Phase 1 で育てた列プール上で Phase 2 を解く。
速い。
候補集合の外側にある真の最適種類数は保証しない。
exact mode：
全 feasible pattern を列挙してから Phase 2 を解く。
明快で、証明向き。
ただし規模が大きいと重い。
研究者向けには exact、実務家向けには fast が有用です。
■16. AI に Python コードを一発生成させるための仕様テキスト
以下をそのまま AI に渡せば、Python コードとしてかなり再現しやすい仕様になります。
--- ここから AI 再現仕様 ---
Python で cutting stock problem を解くコードを作成せよ。
目的は lexicographic である。
第一目的は maximum yield、すなわち minimum total loss である。
第二目的は minimum number of distinct cutting patterns である。
stock count は表示するが最優先目的ではない。
入力形式は tei, zai, noko, hasi, cut を持つテキストである。
tei は unlimited stock length、zai は finite stock length と quantity、noko は kerf width、hasi は left and right edge trim、cut は item length と demand である。
同じ cut length は demand を合算せよ。
材料長より長い item があれば infeasible とせよ。
feasibility は次で判定せよ。
consumed_length = sum(item_length_i * count_i) + noko * (k - 1) + hasi_left + hasi_right
k = total pieces in one pattern
pattern is feasible iff consumed_length <= stock_length
ただし実装では exact transformed lengths を使え。
effective_item_length = item_length + noko
effective_stock_length = stock_length - hasi_left - hasi_right + noko
そして
sum(effective_item_length_i * count_i) <= effective_stock_length
で判定せよ。
pattern は (stock_idx, counts_tuple) で持て。
各 pattern について、product_length_sum、process_loss、consumed_length、tail_trim、total_loss を計算可能にせよ。
Phase 1 は column generation とせよ。
初期 pattern pool は次の5系統から作れ。
1. single-item one-piece
2. single-item maximal packing
3. demand-first greedy
4. length-first greedy
5. pair-greedy
Restricted Master Problem は demand equality と finite stock upper bounds を持ち、目的は total stock length minimization とせよ。
各 pattern cost はその stock length である。
pricing subproblem は bounded dynamic programming とせよ。
reduced cost は
rc = stock_length - dual_value - stock_dual
とせよ。
negative reduced-cost pattern を pool に追加せよ。
同一 dual value なら used length が大きい pattern を優先せよ。
Phase 1 の途中で integer restricted master を定期的に解き、best incumbent を更新せよ。
この incumbent を Phase 2 の MIP start に使え。
Phase 2 は two-pass MIP とせよ。
Pass 1 は x variables only で、minimum total stock length を解け。
Pass 2 は x and z variables を使い、Pass 1 の optimal total stock length を equality で固定し、minimum number of active patterns を解け。
linking constraints は x_j <= U_j z_j とせよ。
U_j は pattern-based upper bound として、demand-based bound、finite stock bound、and Pass-2 stock-length bound を併用して計算せよ。
fast mode では Phase 1 pool のみを使え。
exact mode では全 feasible pattern を DFS で列挙して使え。
出力には少なくとも次を含めよ。
stock bars used
pattern types
total loss
kerf plus edge loss
pure tail trim
total stock length used
yield
各 pattern の詳細
--- ここまで AI 再現仕様 ---
■17. 結果例 A：noko = 0, hasi = 0
Case A は、鋸刃損失と端切り損失を 0 とした基準ケースです。
Stock length: 5550 mm
Product length Required quantity
(mm) (pieces)
1000 70
835 81
720 89
660 105
640 152
570 54
440 27
420 89
Result:
Stock bars used: 81 | Pattern types: 3 | Total trim loss: 1215 | Total stock length used: 449550 | Yield: 99.7297%
35 bars [5550] [1000x2, 720x1, 660x3, 420x2] used length = 5540, trim = 10
19 bars [5550] [640x8, 420x1] used length = 5540, trim = 10
27 bars [5550] [835x3, 720x2, 570x2, 440x1] used length = 5525, trim = 25
このケースは、ロスモデルが最も単純な cutting stock baseline として意味があります。
■18. 結果例 B：noko = 3, hasi = 3 3
Case B は、鋸刃と左右端切りを明示的に入れた現場寄りケースです。
Stock length: 5550 mm
Kerf width: 3 mm
Edge trim: left 3 mm, right 3 mm
Product length Required quantity
(mm) (pieces)
1000 70
835 81
720 89
660 105
640 152
570 54
440 27
420 89
Result:
Stock bars used: 82 | Pattern types: 5 | Total loss: 6765 | Total stock length used: 455100 | Yield: 98.5135%
Process loss (kerf + edge trim): 2247 | Pure tail trim: 4518
4 bars [5550] [720x5, 640x1, 440x1, 420x2] product length = 5520, kerf + edge = 30, consumed length = 5550, tail trim = 0, total loss = 30
9 bars [5550] [835x3, 660x1, 640x1, 440x1, 420x3] product length = 5505, kerf + edge = 30, consumed length = 5535, tail trim = 15, total loss = 45
54 bars [5550] [1000x1, 835x1, 720x1, 660x1, 640x2, 570x1, 420x1] product length = 5485, kerf + edge = 27, consumed length = 5512, tail trim = 38, total loss = 65
14 bars [5550] [1000x1, 720x1, 660x3, 640x2, 440x1] product length = 5420, kerf + edge = 27, consumed length = 5447, tail trim = 103, total loss = 130
1 bar [5550] [1000x2, 720x1, 640x3] product length = 4640, kerf + edge = 21, consumed length = 4661, tail trim = 889, total loss = 910
このケースのポイントは、単なる残尾材だけでなく、process loss と pure tail trim を分けて評価できることです。
これにより、アルゴリズムの出力が現場説明・改善議論・再現実装のいずれにも使いやすくなります。
English summary:
Case A is the zero-kerf, zero-edge baseline.
Case B includes kerf and edge trim explicitly.
The comparison shows that the loss model changes the feasible pattern space and therefore changes the optimal solution structure.
This is exactly why the loss model must be specified if reproducibility matters.
■19. この比較が示すこと
Case A と Case B を比べると、同じ需要でも最適解が変わります。
つまり、鋸刃厚みと端切り量は「最後に補正すればよい数字」ではなく、feasible pattern を変える本質的なパラメータです。
したがって、再現可能なアルゴリズムを公開するなら、loss model を曖昧にしてはいけません。
■20. まとめ
本稿のアルゴリズムは、
・列生成法で有望な pattern を育てる
・best yield を 2-pass MIP で厳密に固定する
・その中で最小 pattern variety を選ぶ
・kerf と edge trim を exact transformed feasibility で扱う
・AI が Python コードとして再現できるように仕様化する
という構成です。
これは cutting stock problem の実装であると同時に、組合せ最適化、数理最適化、離散計画、製造解析、complex systems optimization の一つの実用的な形でもあります。
研究者にも、実務家にも、数学者にも、エンジニアにも、そして AI に実装を頼む人にも有効な設計だと考えています。
検索キーワード / SEO:
カッティングストック問題
組合せ最適化
数理最適化
離散最適化
列生成法
動的計画法
混合整数計画
辞書式最適化
製造最適化
端材最小化
歩留まり改善
パターン種類最小化
複雑系解析
複雑系最適化
cutting stock problem
combinatorial optimization
mathematical optimization
operations research
column generation
pricing dynamic programming
mixed integer programming
lexicographic optimization
yield maximization
pattern minimization
manufacturing optimization
complex systems optimization