1D Cutting Stock

Cut stock rods/rolls into ordered lengths, minimizing waste or stock used.

Also called: 1D Cutting Stock · 절단 재고 문제 · 1D CSP · 트림 손실 문제

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 $L = 10$ and demand for three pieces of length 6 and five of length 4. Using the pattern “6+4” ( $6+4=10$ , 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.

Claims & evidence

Every relationship is a claim with an evidence grade; applicable problem-to-problem relationships also carry an equivalence level. See the evidence policy.

A–X describes evidence reliability; E0–E4 describes mathematical similarity between problems. The two axes are independent.

Relationships from this entry 5

uses method
1D Cutting Stock to Column Generation
Gilmore & Gomory (1961) introduced the column-generation (delayed pattern generation) LP approach for the cutting-stock problem.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem
  Citation details
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
shares method with
1D Cutting Stock to 2D 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.
EvidenceB · Survey / tutorial / community
Equiv.E3 · structural analogy
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
direct benchmark
1D Cutting Stock to BPPLIB
BPPLIB is a direct benchmark providing instances for bin packing and cutting stock problems.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialBPPLIB: a library for bin packing and cutting stock problems
  Citation details
  Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
uses method
1D Cutting Stock to Branch and Bound
Integer solutions to cutting stock have been reported with branch-and-price, combining column generation with branch and bound.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialBPPLIB: a library for bin packing and cutting stock problems
  Citation details
  Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
uses method
1D Cutting Stock to Integer 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.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem
  Citation details
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
uses method 1D Cutting Stock to Column Generation	Gilmore & Gomory (1961) introduced the column-generation (delayed pattern generation) LP approach for the cutting-stock problem.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem Citation details Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
shares method with 1D Cutting Stock to 2D 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.	B · Survey / tutorial / community	E3 · structural analogy	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
direct benchmark 1D Cutting Stock to BPPLIB	BPPLIB is a direct benchmark providing instances for bin packing and cutting stock problems.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialBPPLIB: a library for bin packing and cutting stock problems Citation details Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
uses method 1D Cutting Stock to Branch and Bound	Integer solutions to cutting stock have been reported with branch-and-price, combining column generation with branch and bound.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialBPPLIB: a library for bin packing and cutting stock problems Citation details Delorme, M., Iori, M., Martello, S. (2018). BPPLIB: a library for bin packing and cutting stock problems. Optimization Letters 12:235-250.
uses method 1D Cutting Stock to Integer 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 · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem Citation details Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.

Relationships to this entry 4

shares method with
0/1 Knapsack Problem to 1D Cutting Stock
In cutting-stock column generation the pricing subproblem appears as an (integer) knapsack problem, methodologically linking the two.
EvidenceA · Peer-reviewed / official
Equiv.E3 · structural analogy
Sources
- Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem
  Citation details
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
shares method with
Variable-Sized Bin Packing to 1D Cutting Stock
Variable-sized bin packing and 1D cutting stock share the structure of choosing among several stock/bin types at minimum cost, and both are addressed with pattern/configuration formulations.
EvidenceB · Survey / tutorial / community
Equiv.E3 · structural analogy
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
industry instance of
Paper Roll Slitting to 1D Cutting Stock
Paper roll slitting is an industrial instance of 1D cutting stock and was the real-world motivation behind Gilmore–Gomory's cutting-stock work.
EvidenceA · Peer-reviewed / official
Equiv.E1 · same base, different side constraints
Sources
- Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem
  Citation details
  Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
mentions
Wäscher Typology to 1D Cutting Stock
The typology classifies 1D cutting stock as an 'input minimization' type with strongly heterogeneous small items.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems
  Citation details
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

Relationships to this entry
Relationship	Claim	Evidence	Equiv.	Sources
shares method with 0/1 Knapsack Problem to 1D Cutting Stock	In cutting-stock column generation the pricing subproblem appears as an (integer) knapsack problem, methodologically linking the two.	A · Peer-reviewed / official	E3 · structural analogy	Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem Citation details Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
shares method with Variable-Sized Bin Packing to 1D Cutting Stock	Variable-sized bin packing and 1D cutting stock share the structure of choosing among several stock/bin types at minimum cost, and both are addressed with pattern/configuration formulations.	B · Survey / tutorial / community	E3 · structural analogy	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
industry instance of Paper Roll Slitting to 1D Cutting Stock	Paper roll slitting is an industrial instance of 1D cutting stock and was the real-world motivation behind Gilmore–Gomory's cutting-stock work.	A · Peer-reviewed / official	E1 · same base, different side constraints	Source grade: A — Peer-reviewed / officialA Linear Programming Approach to the Cutting-Stock Problem Citation details Gilmore, P.C., Gomory, R.E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research 9(6):849-859. Introduced the column-generation (delayed pattern generation) approach.
mentions Wäscher Typology to 1D Cutting Stock	The typology classifies 1D cutting stock as an 'input minimization' type with strongly heterogeneous small items.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialAn improved typology of cutting and packing problems Citation details Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.