1D Cutting Stock
Cut stock rods/rolls into ordered lengths, minimizing waste or stock used.
Also called: 1D Cutting Stock · 절단 재고 문제 · 1D CSP · 트림 손실 문제
Last verified: 2026-05-27
Definition
Given stock of a fixed length and a list of required shorter lengths with demands, choose cutting patterns to meet demand using the fewest stock pieces (equivalently, minimizing trim loss).
Example
Suppose stock of length and demand for three pieces of length 6 and five of length 4. Using the pattern “6+4” (, zero trim) three times yields three 6s and three 4s; the remaining two 4s are covered by one use of “4+4” (length 8, trim 2). That is 4 stock pieces with total trim loss 2 — and no fewer is possible, since each 6 needs its own stock (at least 3) plus one more for the leftover 4s.
Why it matters here
It is the historical home of column generation: rather than enumerate all cutting patterns, the Gilmore–Gomory approach generates promising patterns on demand by solving a knapsack pricing subproblem. The same machinery reappears across the cutting & packing family.
Related nodes
See the depth-1 graph below.
Claims & evidence
Every relationship is a claim with an equivalence level and an evidence grade. See the evidence policy.
| Relationship | Claim | Equiv. | Evidence | Sources |
|---|---|---|---|---|
| uses methodColumn Generation | Gilmore & Gomory (1961) introduced the column-generation (delayed pattern generation) LP approach for the cutting-stock problem. | — | A |
|
| shares method with2D Bin Packing | 1D cutting stock and bin packing are closely related members of the same cutting & packing family; both are addressed with pattern/configuration formulations. | E3 | B |
|
| direct benchmarkBPPLIB | BPPLIB is a direct benchmark providing instances for bin packing and cutting stock problems. | — | A |
|
| uses methodBranch and Bound | Integer solutions to cutting stock have been reported with branch-and-price, combining column generation with branch and bound. | — | B |
|
| uses methodInteger Linear Programming | 1D cutting stock is formulated as an integer linear program over pattern (cutting-pattern) variables — the Gilmore-Gomory pattern formulation is its basis. | — | A |
|
Neighborhood
Direct graph neighbors. Toggle depth to expand.
See also
Not directly linked, but conceptually close — by the connections and descriptions they share.