いつものごとくChatGPTにプログラムを書いてもらった。最強・最凶クラスのアルゴリズムが出来たので、そのフローを記録したい。その続き。
引用 ChatGPT
Cutting Stock Problem / 数理最適化 / 歩留まり最大を固定してパターン種類数を最小化する2-pass法【後編・再現仕様】
後編では、再現性をさらに高めるために、Phase 2 の仕様を中心に書きます。
ここでのポイントは、「良さそうな話」ではなく、第三者が同じ思想で実装しやすい順番で説明することです。
■1. なぜ後半が難しいのか
Phase 1 の列生成は比較的素直です。
しかし「パターン種類数最小化」を入れた瞬間に、問題は一気に重くなります。
理由は simple です。
各候補 pattern j について、
x_j = その pattern を何本使うか
z_j = その pattern を使うかどうか
の2種類の変数が必要になるからです。
そして、両者を結ぶために
x_j <= U_j z_j
という linking constraint が必要になります。
候補パターン数を P とすると、
・x 変数が P 個
・z 変数が P 個
・linking constraint が P 本
増えます。
exact mode で全 feasible pattern を並べると、ここが急激に重くなります。
English summary:
Pattern minimization is hard because it introduces activation binaries.
For each candidate pattern j, a binary variable z_j and a linking constraint x_j <= U_j z_j are needed.
This doubles the modeling burden and greatly enlarges the MIP.
■2. Phase 2 を 2-pass に分ける理由
本稿では weighted sum は使いません。
つまり、
min total_loss + epsilon × pattern_types
のような1本化は採りません。
理由:
・目的順が曖昧になる
・epsilon の設計に依存する
・binary を含む微小係数目的は solver にとって扱いづらいことがある
・ブログで説明したときに「本当に歩留まり最適なのか」が読み手に伝わりにくい
したがって、後半は必ず 2-pass です。
Pass 1:
総使用母材長最小 = 総損失最小 = 歩留まり最大
Pass 2:
Pass 1 の最適総使用母材長を固定
その上で pattern type 数を最小化
English summary:
The second stage is lexicographic, not weighted.
Pass 1 determines the best-yield world.
Pass 2 minimizes the number of active pattern types inside that world.
■3. PatternTable を作る
Python 実装でも C++ 実装でも、後半で重要なのは pattern metadata の前計算です。
各 pattern を毎回総なめして行列を組み立てると、solver を呼ぶ前に時間を失います。
そこで PatternTable を作ります。
最低でも次を持つと実用的です。
・patterns
・stock_idx_arr
・stock_len_arr
・used_len_arr
・trim_arr
・x_upper_arr
・demand_col_idx
・demand_col_val
・stock_col_idx
これにより、需要行、在庫行、x の上限、表示情報を何度も再計算せずに済みます。
English explanation:
PatternTable is preprocessing, not a change of mathematical logic.
It simply caches everything needed to build Pass 1 and Pass 2 quickly and consistently.
■4. Phase 2 Pass 1 の定式化
Pass 1 は z を使いません。
使うのは x_j だけです。
変数:
x_j ∈ Z_+
制約:
(1) 需要等式
sum_j a_ij x_j = demand_i
(2) 有限在庫制約
有限在庫材 s について
sum_{j in stock s} x_j <= cap_s
目的:
min sum_j stock_length_j × x_j
需要が等式なので、総製品長は固定です。
よって、総使用母材長最小は総損失最小と同じです。
ノコ歯と端切りは pattern feasibility の中へ吸収されているため、ここでは stock_length_j を cost に置けば足ります。
English formulation:
Pass 1:
min Σ c_j x_j
s.t. demand equalities
finite stock upper bounds
x_j integer and nonnegative
Here c_j is the stock length used by pattern j.
■5. Pass 1 の出力
Pass 1 が返すべきものは少なくとも次の3つです。
・usage: pattern ごとの使用本数
・optimal_total_stock_len
・solver status
さらに実務では、
・母材本数
・総損失
・ノコ＋端切
・純残尾材
・歩留まり
も同時に計算しておくとよいです。
Pass 1 の本質は、「歩留まり最良の面」を確定することです。
まだ種類数は問いません。
ここで binary を入れないのが重要です。
English summary:
Pass 1 should return a feasible or optimal usage plan, the best total stock length, and the solver status.
Its job is to certify the best loss level, not to reduce pattern variety yet.
■6. Phase 2 Pass 2 の定式化
Pass 2 で初めて z_j を導入します。
変数:
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_len
(4) linking constraints
x_j <= U_j z_j
目的:
min sum_j z_j
これで、「歩留まり最良の解集合の中で、最小の pattern type 数」を得られます。
English formulation:
Pass 2:
min Σ z_j
s.t. demand equalities
finite stock limits
Σ c_j x_j = L*
x_j <= U_j z_j
x_j integer, z_j binary
This produces the minimum number of distinct pattern types among all best-yield solutions.
■7. U_j の設計
Big-M つまり U_j を雑に置くと、Pass 2 はさらに重くなります。
再現性と実用性のため、上限は明示的に設計します。
基本上限:
U_j <= min_i ceil(demand_i / a_ij)
有限在庫材なら:
U_j <= cap_s
Pass 2 ではさらに:
U_j <= floor(optimal_total_stock_len / stock_length_j)
理想論では floor のみでよりタイトにしたい場面もありますが、実装との一致を重視するなら、実際に採用している規則を明記することが大切です。
ブログでは「使っている上限式」を正直に書くべきです。
English note:
A tight linking upper bound U_j is crucial for MIP performance.
Even if you later refine it, the article should clearly state which rule is actually implemented.
■8. MIP start
Phase 1 で得た incumbent usage は、Phase 2 の出発点として有益です。
そこで Pass 1 には x only の MIP start、Pass 2 には x と z の両方の MIP start を入れます。
Pass 1 の seed:
x_j = incumbent usage
Pass 2 の seed:
x_j = incumbent usage
z_j = 1 if x_j > 0 else 0
これは最適性保証そのものではありませんが、探索の立ち上がりを改善することがあります。
English summary:
MIP start is not a substitute for a strong model, but it is still valuable.
A good incumbent often helps the solver begin from a meaningful region of the search space.
■9. fast mode と exact mode
再現性を高めるため、候補集合の作り方も mode として分けておくと親切です。
fast mode:
Phase 1 で得た列プールだけを使う
長所:速い
短所:真の最適種類数を見逃す可能性がある
exact mode:
全 feasible pattern を列挙して使う
長所:目的順に対して最も明快
短所:問題規模が大きいと非常に重い
研究者向けには exact が魅力的です。
実務家向けには fast が魅力的です。
English summary:
Fast mode is for daily practical operation.
Exact mode is for proof-oriented work and smaller instances where full enumeration is still manageable.
■10. 全 feasible pattern の列挙
exact mode の候補生成は、effective length を使った DFS で書けます。
for each stock type:
dfs over item index i
choose count c from max feasible down to 0
recurse with reduced remaining effective capacity
このとき
max feasible count は
min(remaining_effective_capacity // effective_item_length_i, demand_i)
です。
重複 pattern を防ぐため、(stock_idx, counts) を key にして seen 管理します。
English explanation:
The full candidate set can be generated by DFS over count vectors under transformed effective capacity.
This is simple and reproducible, although it may become expensive on large instances.
■11. 結果比較の順番
このアルゴリズムの結果を読むときは、必ず次の順番で比較します。
1. 総損失
2. 種類数
3. 母材本数
4. ノコ＋端切
5. 純残尾材
6. 歩留まり
ここで 3 を先に見ないことが大切です。
本稿では本数最小化は主目的ではありません。
ブログを読んだ人にも、この評価順を理解してもらいたいです。
English summary:
Read the result in the same order as the objective.
First loss, then pattern count, then other indicators.
■12. 実装チェックリスト
第三者が再現実装するときの checklist をまとめます。
・入力として tei, zai, noko, hasi, cut を読む
・同じ cut length は需要を合算する
・feasibility は実効長変換で判定する
・pattern は (stock_idx, counts) で保持する
・初期列は5系統で作る
・RMP の目的は stock length の総和
・需要は等式
・有限在庫は上限制約
・pricing は bounded DP
・同価値なら使用長が大きい pattern を優先
・Phase 1 の途中で integer RMP を解く
・Phase 2 は必ず 2-pass
・Pass 2 でのみ z を使う
・PatternTable を使って行列構築の再走査を減らす
・MIP start を試す
・出力では総損失、種類数、本数、ノコ＋端切、純残尾材、歩留まりを出す
English checklist:
Input, transformed feasibility, pattern structure, initial pool, pricing DP, intermediate integer solves, exact two-pass MIP, precomputed PatternTable, and full reporting metrics.
■13. 研究者・実務家・数学者・エンジニアへのメッセージ
研究者にとっては、これは cutting stock, column generation, lexicographic optimization, mixed integer programming の組合せです。
実務家にとっては、材料歩留まりと段取り数の同時改善です。
数学者にとっては、exact demand, discrete pattern space, hierarchical objectives の定式化です。
エンジニアにとっては、DP、疎行列、前計算、solver API、MIP start をどう噛み合わせるかの話です。
つまり本稿は、1つの業界の話ではありません。
問題の外見は違っても、
「候補構造を生成し、制約を満たし、目的順を守って選ぶ」
という骨格は、多くの optimization problem で共通です。
English summary:
This is not only a cutting stock article.
It is also a reproducible example of hierarchical optimization over a generated combinatorial candidate space.
■14. 実例 / Reproducible Examples achieved by this algorithm
Below are two achieved solutions for the same demand instance.
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
Case A: noko = 0, hasi = 0
This is the zero-kerf, zero-edge-trim reference case.
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
Case B: noko=3 and hasi=3 included
Here kerf loss and edge trim are included in the physical cutting model.
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
この2ケース比較のポイントは明確です。
1. noko = 0, hasi = 0 の基準ケースでは、非常に高い歩留まりと少ない pattern type 数が達成できています。
2. noko と hasi を導入すると、same demand でも feasible pattern の集合が変わります。
3. その結果、母材本数、種類数、総損失、歩留まりがすべて変化します。
4. とくに Case B では、loss を pure tail trim と process loss に分けて読めるため、現場説明と改善議論がしやすくなります。
つまり、この比較は
「ノコ歯や端切りをモデルへ入れるかどうかで、最適解の構造が本当に変わる」
ことを示しています。
これは単なる表示上の補正ではなく、optimization model 自体の違いです。
English remark:
These two cases are worth showing side by side.
Case A is the clean reference model with zero kerf and zero edge trim.
Case B is the physically richer model with kerf loss and edge trim included.
The feasible pattern space changes, so the optimal plan also changes.
This is exactly why the loss model must be stated clearly in a reproducible technical article.
■15. このアルゴリズムを一文で言うと
「Column generation で候補 pattern を育て、Pass 1 で best yield を固定し、Pass 2 で minimum pattern variety を選ぶ」
English one-line summary:
Generate strong patterns first, certify the best yield second, and minimize pattern variety third.
■16. 後編のまとめ
後編で伝えたかったことは次の4点です。
・パターン種類最小化は z 変数の導入で急に重くなる
・だからこそ 2-pass の lexicographic optimization が必要
・PatternTable と MIP start は実装再現性と実用性を高める
・fast mode と exact mode を分けると、研究と実務の両方に対応しやすい
この問題に関心がある方は、cutting stock, discrete optimization, resource allocation, planning optimization, operations research, manufacturing analytics, complex system optimization の文脈から見ても、同じ骨格を多く見つけられるはずです。
検索キーワード / SEO:
カッティングストック問題
組合せ最適化
数理最適化
列生成法
混合整数計画
辞書式最適化
動的計画法
パターン最適化
製造計画
複雑系最適化
cutting stock problem
column generation
mixed integer programming
lexicographic optimization
pattern selection
yield maximization
minimum number of pattern types
resource allocation
industrial optimization
complex systems analysis
■17. Pass 2 の linking constraint の意味
x_j <= U_j z_j
は、見た目は単純ですが非常に重要です。
z_j = 0 のとき:
x_j = 0 でなければならない
z_j = 1 のとき:
x_j は 0 から U_j の範囲で使える
つまり z_j は「その pattern を採用したかどうか」を表します。
Pass 2 の目的が min sum(z_j) なので、solver は可能な限り少ない種類の pattern だけで demand を満たそうとします。
English summary:
The linking constraints connect usage variables to activation variables.
Without them, the binary count objective would have no physical meaning.
■18. なぜ Pass 1 の最適総使用母材長を等式固定するのか
ここは検索で流入した数学者・研究者の方が最も気にする点かもしれません。
もし Pass 2 で
sum_j stock_length_j x_j <= L*
のように不等式にすると、solver はより小さな stock length を使う解も許されます。
理論上それでも良さそうに見えますが、Pass 1 の世界をそのまま切り出したいなら、等式のほうが解釈が明快です。
すでに Pass 1 で最小値 L* が分かっているので、
sum_j stock_length_j x_j = L*
と固定すれば、
「best-yield face の上だけで種類数を減らす」
ことが明確になります。
English note:
The equality constraint is the cleanest way to stay exactly on the optimal loss level found in Pass 1.
■19. Pass 2 の擬似コード
reproducibility のため、Pass 2 も擬似コードを書きます。
build x variables
build z variables
add demand equality rows
add finite stock rows
add total stock length equality to Pass-1 optimum
for each pattern j:
add x_j <= U_j z_j
apply MIP start if available
solve MIP
extract x solution
count active pattern types
この flow を書いておくと、Python でも C++ でも、あるいは他 solver でも移植しやすくなります。
English pseudocode:
Pass 2 is structurally simple once the candidate set and metadata table are ready.
■20. PatternTable に入れる x_upper_arr
x_upper_arr は Pass 1 と Pass 2 の両方で効きます。
各 pattern j について、事前に x_j の安全な上限を計算しておくと、モデル構築も速く、Big-M も揃えやすくなります。
候補例:
x_upper_j = min over positive a_ij of ceil(d_i / a_ij)
finite stock があるならさらに min with cap_s
Pass 2 ではさらに min with floor(L* / stock_length_j)
このように上限を前計算しておけば、後半の MIP で毎回同じ logic を再実装しなくて済みます。
English summary:
Pattern-specific upper bounds are practical metadata.
They reduce model size and keep the linking constraints consistent.
■21. fast mode の位置づけ
fast mode は「雑な近似」ではありません。
正確には、
「Phase 1 で育てた、すでに有望と分かっている candidate pool に限定して exact two-pass MIP を解く」
ものです。
したがって、
候補集合の上では exact
候補集合の外には保証なし
という立ち位置です。
これは実務ではとても使いやすいです。
日常の計画では runtime が大事で、常に full enumeration をする必要はありません。
English note:
Fast mode is exact on a restricted candidate set, but not globally exact over the full pattern universe.
■22. exact mode の位置づけ
exact mode は、full feasible pattern set を作った上で 2-pass を解く方式です。
概念的には最も分かりやすいです。
一方で、規模が少し大きくなると candidate explosion が起きます。
このため、ブログでは exact mode を「理想形」として紹介しつつ、運用では fast mode を使うことも明記したほうが親切です。
English summary:
Exact mode is excellent for clarity and proof, but expensive.
Fast mode is excellent for operational use.
■23. solver status の扱い
再現性を高めるうえで、solver status の扱いも仕様化したほうが良いです。
基本方針:
・Optimal ならそのまま採用
・Time limit 系なら incumbent が可行なら採用
・Unknown や Not Set は原則採用しない
English note:
Solver status policy is part of reproducibility.
It defines what counts as an acceptable returned solution.
■24. MIP start の実装上の現実
solver API は版差があり、setSolution の署名が違うことがあります。
したがって、実装では複数方式を順に試す設計が現実的です。
例:
・(num_nz, idx, val) 方式
・(idx, val) 方式
・dense solution object 方式
English summary:
MIP start is partly an API engineering issue, not only a mathematical idea.
■25. 結果表示フォーマット
最終出力は、実務と研究の両方で読める形が望ましいです。
私は少なくとも次を表示する設計を勧めます。
summary:
・Stock bars used
・Pattern types
・Total trim loss
・Total stock length used
・Yield
・Kerf plus edge loss
・Pure tail trim
details:
各 pattern について
・使用本数
・stock length
・count vector
・used product length
・process loss
・consumed length
・tail trim
・total loss
English note:
A good report separates compact summary metrics from detailed pattern-by-pattern descriptions.
■26. 研究論文風に書くなら
もしこの記事を研究メモや technical note に寄せたいなら、次の章立てが使いやすいです。
1. Problem statement
2. Loss model with kerf and edge trim
3. Candidate pattern representation
4. Column generation phase
5. Pricing dynamic program
6. Intermediate integer restricted master solves
7. Two-pass lexicographic MIP
8. Fast mode and exact mode
9. Computational results
10. Discussion and limitations
この章立ては、operations research, applied mathematics, industrial engineering の文脈にも乗せやすいです。
English suggestion:
This structure is suitable for technical blogging, internal documentation, or a research-oriented note.
■27. 実務報告書風に書くなら
実務家向けには、次の順番も有効です。
1. 目的
2. 入力条件
3. 切断ロスの考え方
4. アルゴリズム概要
5. 結果
6. なぜその結果が良いのか
7. 現場効果
8. 今後の改善
つまり、論文調だけでなく、現場報告書調にも落とせるアルゴリズムです。
■28. 複雑系・解析一般との接続
ユーザーの方針に合わせてあえて広めに言えば、この問題は complex systems analysis のほんの一部です。
なぜなら、現実の意思決定はたいてい
・多変数
・離散選択
・制約つき
・複数目的
・局所ルールと全体評価の両立
を要求するからです。
cutting stock problem はその中でも、非常に分かりやすく、しかも industrial value が高い例です。
そのため、以下の検索文脈から来た人にも届きやすいように説明しておく価値があります。
・complex systems optimization
・multi-objective planning
・constrained discrete search
・industrial decision analytics
・resource-constrained optimization
・pattern-based planning
・hierarchical objective optimization
English summary:
The problem can be viewed as a specific but highly practical instance of constrained discrete optimization in complex operational systems.
■29. 限界と今後の改善
本稿のアルゴリズムには限界もあります。
・exact mode は候補爆発しやすい
・Pass 2 の binary 導入で重くなる
・候補列の外側にある真の最適種類数は fast mode では保証できない
・大規模化すると Python の前処理も無視できない
ただし、これらはアルゴリズムの価値を否定するものではありません。
むしろ、どこまでを厳密、どこからを practical compromise とするかを明示することが大事です。
English note:
A good reproducible article should also state its limits.
That increases trust rather than reducing it.
■30. C++ へ移すときに残すべき本質
実装言語を C++ に変えても、守るべき本質は次の順です。
1. objective order
2. transformed feasibility model
3. initial pool policy
4. pricing DP behavior
5. intermediate integer incumbent policy
6. two-pass exact phase
7. reporting metrics
つまり、速さのために移植しても、意味まで変えてはいけません。
English summary:
When porting the code to C++, preserve the semantics first and optimize the implementation second.
■31. 実例の読み方
最後に掲載した実例は、単に数字がきれいというだけではありません。
注目点は次の3つです。
1. Yield が非常に高い
2. Pattern types が 3 まで落ちている
3. 各 pattern が現場で説明しやすい
実務では、pattern type が減ると
・段取りが減る
・指示票が簡潔になる
・教育コストが下がる
・取り違えが減る
という効果があります。
English interpretation:
Pattern count is an operational complexity metric, not just a mathematical decoration.
■32. 後編のFAQ
Q1. Pass 2 だけ解けばよいのでは。
A1. だめです。Pass 1 で best yield level を固定しないと、歩留まりの悪い単純解へ流れる可能性があります。
Q2. 需要制約を >= にしたい場合は。
A2. 可能ですが、本稿の objective interpretation は変わります。再現性重視なら equality で揃えるのが無難です。
Q3. exact mode は必須ですか。
A3. 研究・検証では有益です。日常運用では fast mode のほうが実用的なことが多いです。
Q4. PatternTable は本当に必要ですか。
A4. 小規模では必須ではありません。ただし後半の行列構築コストを抑えるには有効です。
Q5. solver を HiGHS 以外に変えてもよいですか。
A5. はい。モデルと候補生成の考え方は多くの MIP solver に移せます。
Q6. この方法は他問題にも使えますか。
A6. はい。candidate generation + hierarchical selection という構造は多くの離散最適化問題に現れます。
English FAQ:
Can this method be transferred to other optimization problems?
Yes.
The general structure of candidate generation, exact-demand satisfaction, and lexicographic selection appears in many discrete optimization settings.
■33. 最終まとめ
本稿のアルゴリズムを最短で言うなら、次の通りです。
前半:
Generate strong candidate patterns with column generation and a pricing DP.
後半:
Fix the best yield exactly, then minimize the number of active pattern types.
日本語で言えば、
「良い候補を作り、最良歩留まりを確定し、その中で最少種類数を選ぶ」
です。
これが、研究者にも実務家にも説明しやすく、実装者にも移植しやすい理由です。
検索キーワード / SEO 追加:
最適化アルゴリズム
組合せ爆発
列生成アルゴリズム
離散計画
複数目的最適化
工程最適化
資源配分最適化
数理計画
complex systems optimization
multi-objective discrete optimization
hierarchical optimization
pattern generation
manufacturing planning
industrial analytics