Guillotine Cutting

Orthogonal cutting constrained to edge-to-edge straight cuts.

Also called: Guillotine Cutting · 길로틴 컷 · Guillotine-cut packing

Definition

A cutting & packing problem where rectangles are cut or placed under the constraint that each cut runs straight from one edge of the current piece to the opposite edge.

Example

From a $4\times4$ panel, a horizontal edge-to-edge cut splits it into $4\times1$ and $4\times3$ ; a vertical cut then divides the $4\times3$ into two $2\times3$ — each cut runs edge to edge, satisfying the guillotine constraint. By contrast, a “pinwheel” arrangement, where one piece is boxed in at the center, cannot be separated by any single straight cut and so is not guillotine-producible.

Why it matters

The guillotine constraint is not arbitrary — many cutting machines (panel saws, glass cutters, paper guillotines) can only make edge-to-edge straight cuts. This recursive structure fits dynamic programming well.

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 8

variant of
Guillotine Cutting to 2D Bin Packing
Guillotine cutting is a variant of 2D orthogonal cutting & packing with the added constraint that cuts must be edge-to-edge and straight.
EvidenceA · Peer-reviewed / official
Equiv.E1 · same base, different side constraints
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.
uses method
Guillotine Cutting to Dynamic Programming
Guillotine patterns, thanks to their recursive subdivision structure, can be handled efficiently with dynamic programming (Gilmore–Gomory).
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialMultistage Cutting Stock Problems of Two and More Dimensions
  Citation details
  Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
shares method with
Guillotine Cutting to 2D Strip Packing
Guillotine cutting and strip packing share orthogonal placement methodology.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
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.
uses method
Guillotine Cutting to Column Generation
Gilmore & Gomory extended the column-generation / pattern-generation approach to two-dimensional guillotine cutting stock.
EvidenceA · Peer-reviewed / official
Sources
- Source grade: A — Peer-reviewed / officialMultistage Cutting Stock Problems of Two and More Dimensions
  Citation details
  Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
uses method
Guillotine Cutting to Genetic Algorithm
Guillotine cutting / panel cutting has also been addressed with metaheuristics such as genetic algorithms.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method
Guillotine Cutting to Branch and Bound
Exact approaches to guillotine cutting have been reported with branch and bound.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey
  Citation details
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
shares method with
Guillotine Cutting to 2D Knapsack
Maximizing on a single sheet under the guillotine constraint is the guillotine 2D knapsack, sharing methodology with 2D knapsack.
EvidenceB · Survey / tutorial / community
Equiv.E2 · shared methodology
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.
adjacent benchmark
Guillotine Cutting to 2DPackLib
Some orthogonal instances in 2DPackLib relate to guillotine variants, making it an adjacent benchmark.
EvidenceB · Survey / tutorial / community
Sources
- Source grade: A — Peer-reviewed / official2DPackLib: a two-dimensional cutting and packing library
  Citation details
  Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.

Relationships from this entry
Relationship	Claim	Evidence	Equiv.	Sources
variant of Guillotine Cutting to 2D Bin Packing	Guillotine cutting is a variant of 2D orthogonal cutting & packing with the added constraint that cuts must be edge-to-edge and straight.	A · Peer-reviewed / official	E1 · same base, different side constraints	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.
uses method Guillotine Cutting to Dynamic Programming	Guillotine patterns, thanks to their recursive subdivision structure, can be handled efficiently with dynamic programming (Gilmore–Gomory).	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialMultistage Cutting Stock Problems of Two and More Dimensions Citation details Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
shares method with Guillotine Cutting to 2D Strip Packing	Guillotine cutting and strip packing share orthogonal placement methodology.	B · Survey / tutorial / community	E2 · shared methodology	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.
uses method Guillotine Cutting to Column Generation	Gilmore & Gomory extended the column-generation / pattern-generation approach to two-dimensional guillotine cutting stock.	A · Peer-reviewed / official	—	Source grade: A — Peer-reviewed / officialMultistage Cutting Stock Problems of Two and More Dimensions Citation details Gilmore, P.C., Gomory, R.E. (1965). Multistage Cutting Stock Problems of Two and More Dimensions. Operations Research 13(1):94-120. Extends column generation and the knapsack-function dynamic program to two-dimensional (guillotine) cutting.
uses method Guillotine Cutting to Genetic Algorithm	Guillotine cutting / panel cutting has also been addressed with metaheuristics such as genetic algorithms.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
uses method Guillotine Cutting to Branch and Bound	Exact approaches to guillotine cutting have been reported with branch and bound.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / officialTwo-dimensional packing problems: A survey Citation details Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
shares method with Guillotine Cutting to 2D Knapsack	Maximizing on a single sheet under the guillotine constraint is the guillotine 2D knapsack, sharing methodology with 2D knapsack.	B · Survey / tutorial / community	E2 · shared methodology	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.
adjacent benchmark Guillotine Cutting to 2DPackLib	Some orthogonal instances in 2DPackLib relate to guillotine variants, making it an adjacent benchmark.	B · Survey / tutorial / community	—	Source grade: A — Peer-reviewed / official2DPackLib: a two-dimensional cutting and packing library Citation details Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.

Relationships to this entry 1

industry instance of
Wood Panel Cutting to Guillotine Cutting
Wood panel cutting is an industrial instance of guillotine cutting because panel saws make edge-to-edge straight cuts.
EvidenceB · Survey / tutorial / community
Equiv.E1 · same base, different side constraints
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
industry instance of Wood Panel Cutting to Guillotine Cutting	Wood panel cutting is an industrial instance of guillotine cutting because panel saws make edge-to-edge straight cuts.	B · Survey / tutorial / community	E1 · same base, different side constraints	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.