Cutting Stock Problem¶
An optimization problem that chooses feasible cutting patterns for available stock and their use counts to meet item demands while minimizing a declared stock-use, cost, or waste objective.
Core Idea¶
The cutting stock problem asks how to obtain specified quantities of smaller pieces from available larger stock while using stock economically. An instance specifies stock units and their dimensions or costs, demanded item types and counts, feasible ways to cut a unit, and an objective such as minimum stock cost, number of units, or trim loss. A solution selects cuts and how often to use them so that output meets the order. Gilmore and Gomory's original one-dimensional statement is explicit about required numbers of lengths, given stock lengths and costs, and minimum-cost order fulfillment.[1]
In a pattern formulation, one cutting pattern represents an admissible collection of pieces from a single stock unit. Nonnegative integer pattern multiplicities tell how many units follow each pattern. In a simple identical-stock case, if stock length is \(L\), item type \(i\) has length \(l_i\) and required count \(d_i\), and pattern \(p\) yields \(a_{ip}\) items of type \(i\), then feasible patterns obey \(\sum_i l_i a_{ip}\leq L\). The plan chooses integer \(x_p\geq0\) with \(\sum_p a_{ip}x_p\geq d_i\) (or equality when overproduction is forbidden), minimizing a declared expression such as \(\sum_p c_p x_p\). This is a classical one-dimensional formulation, not a universal model of every dimensional, mixed-stock, or staged variant.[1][2]
The abstraction is the stock–demand–pattern–plan relation. Column generation, integer programming, and heuristics are ways to search for a plan, not parts of the problem's identity. The first Gilmore–Gomory paper addressed the huge number of variables in an LP treatment; their later paper explicitly extended the setting from one dimension to multistage cutting in two or more dimensions.[1][3]
Structural Signature¶
Sig role-phrases: available stock — required smaller items — feasible cut patterns — integral pattern use — declared optimization objective.
- Available stock. Raw rolls, bars or sheets have dimensions, costs, and sometimes limited counts. Those facts determine what can be cut and what a unit of consumption costs.[1][2]
- Item demand. Smaller output types have dimensions and required quantities. A pattern efficient in isolation does not solve the problem unless enough pattern repetitions cover the order.[1]
- Cut feasibility. A pattern must fit a stock unit and obey relevant cutting geometry, orientation, staging, or machine restrictions. The one-dimensional length inequality above is one case; multistage two-dimensional patterns require a different feasibility test.[3]
- Pattern-use decision. Whole stock units are assigned to patterns, so actual production counts are integral. A formulation may use another representation, but it must still give an executable stock-to-item plan.[1][2]
- Objective and policy. Minimum unit count, monetary cost, trim, underproduction, or pattern changes are different optimization goals. Availability and whether excess items are allowed must be stated rather than silently assumed.[2]
What It Is Not¶
It is not column generation. That method can search a large pattern space by generating useful columns; Gilmore and Gomory used it for the LP formulation, but it is not necessary to pose a cutting-stock instance. Nor does an LP relaxation with fractional pattern counts directly specify whole rolls or sheets to cut.[1][3]
It is not guillotine cutting as such. Recursive full-edge cuts can restrict feasible patterns in rectangular stock, but one-dimensional slitting and other cutting variants do not all share that constraint. It is not any use of scissors or a saw: without demanded outputs, feasible plan alternatives and an optimization or fulfillment criterion, a cut instruction is merely an operation. It is also not identical to the full packing problem genus. Packing can arrange objects in containers without requiring production of ordered pieces by cutting larger stock.[3][2]
Scope of Application¶
The classical one-dimensional case appears when a wide paper master roll is slit into demanded narrower rolls. The paper-industry study by Kallrath and colleagues distinguishes a standard master-roll formulation from variants with different roll widths, availability, overproduction rules and setup concerns. Gilmore and Gomory's later research treats multistage cutting in two or more dimensions and discusses corrugated-box production, including an auxiliary sequencing condition.[2][3]
These extensions preserve the stock-to-demand problem but alter what counts as a feasible pattern and how a plan is judged. A mixed-stock instance need not minimize the same thing as a uniform-stock instance, and a layout feasible geometrically may violate cutting order or production restrictions. The entry is a mathematical model of such decisions, not guidance on operating industrial cutting equipment.
Clarity¶
Separate problem data, feasibility, objective, and solver. Stock sizes and item orders are data; allowable cut patterns define feasibility; an objective ranks valid plans; column generation is one way of finding them. Confusing the four can make a successful LP computation look like proof of an executable optimum even when some pattern variables are fractional.[1][3]
Also distinguish stock count from trim. With identical stock and fixed demand, using fewer units often reduces unused material, but that need not remain true once units differ in width, cost or availability, or remnants have value. Even within one mill, minimizing distinct patterns may reduce knife-setting changes while consuming more material. The objective is part of an instance's identity, not an interchangeable slogan.[2]
Manages Complexity¶
Pattern counts compress many individual cuts into a manageable production plan: all master rolls using one feasible layout can share a variable. The compression makes repeated orders and stock types analyzable as demand constraints rather than one-off cutting stories. It also exposes why many potential patterns need not be listed in advance—Gilmore and Gomory's method works with a small active LP matrix and searches for additional promising patterns.[1][3]
Compression can hide practical restrictions. A pattern that fits by length might not be allowable under staged two-dimensional cuts, knife arrangements, sequence constraints, or limits on overproduction. Those omissions are not minor details if they change the feasible set or objective.[3][2]
Abstract Reasoning¶
First fix a stock type, item demands, allowed cuts and objective. A candidate pattern has an output vector; compare its use of stock with the demanded vector. A proposed plan is valid only if its whole-number pattern counts meet every required quantity and every chosen pattern satisfies its stock and process constraints. Only then compare total stock or costs across plans.[1][2]
For identical one-dimensional stock of length \(L\), \(\left\lceil\sum_i d_i l_i/L\right\rceil\) is a necessary lower bound on the number of units: total requested length must fit in the chosen stock. It need not be attainable because the pieces may not combine into patterns without leftover gaps. The bound does not directly settle mixed-stock cost or two-dimensional feasibility. A continuous LP optimum can yield a stronger bound, but fractional \(x_p\) values are not a completed cutting schedule.[1][3]
Knowledge Transfer¶
The role structure transfers from roll width to sheet area only with a revised pattern-feasibility model. In a paper mill, width combinations fit across a master roll; in corrugated-box production, rectangular blank layouts and staged separations determine what a sheet can yield. In both, repeated stock units supply demanded smaller outputs, and a valid plan compares alternative use counts. The geometry, cut order and operational cost do not transfer automatically.[2][3]
At a more abstract level, the problem resembles packing: items occupy finite containers without overlap under an optimization objective. That is the basis of the proposed strict DAG parent Packing Problem. The cutting-stock residual is production of ordered item quantities from raw units by feasible cuts, so the two names should not be merged simply because a simple one-dimensional instance can be modeled as bin packing.
Examples¶
Paper-roll slitting. A mill receives orders for several narrower roll widths and has master rolls of specified width. A pattern is a compatible set of widths produced from one roll; the count of each pattern says how many master rolls use that setup. A plan must meet each customer quantity. Kallrath and colleagues describe both the standard stock-count objective and variants involving different master-roll widths and pattern setups; a plan minimizing roll count can therefore differ from one minimizing changes of knife settings.[2] Mapped back: stock = master rolls; demand = ordered smaller-roll widths and counts; feasibility = widths fitting in one roll with applicable restrictions; pattern use = number of rolls assigned to each slit layout; objective = declared roll use, cost or setup criterion.
Staged corrugated-box cutting. The raw unit is a sheet, and demanded output is a collection of rectangular blanks. A candidate pattern must be achievable by the allowed sequence of cuts, not merely by an area inequality. Gilmore and Gomory's two-or-more-dimensional study discusses this industrial class and an auxiliary sequencing problem under simplifying assumptions.[3] Mapped back: stock = sheet sizes; demand = blank sizes and counts; feasibility = allowed multistage subdivisions; pattern use = sheets assigned to each admissible layout; objective = stock consumption/cost subject to production and sequencing restrictions.
Boundary case. A single rectangle can be split by a legal guillotine cut without any order or comparison among stock-use plans. That establishes a possible cut, not yet a cutting-stock optimization instance.
Structural Tensions¶
Material economy versus pattern-change economy. The plan using the fewest stock units can require many distinct patterns, while a simpler production program can consume more stock or leave more trim. Kallrath and colleagues identify pattern minimization as a separate concern tied to machine setup. Diagnostic: Does the objective price material alone, or do setup changes materially alter the preferred plan?[2]
Compact relaxation versus executable integral plan. An LP method can avoid enumerating all patterns and provide a useful lower bound, but its fractional pattern counts are not literal numbers of rolls or sheets. Enforcing whole counts can require a different search or leave an optimality gap. Diagnostic: Are the reported counts integer and demand-feasible, and what bound supports the claimed quality of the plan?[1][3]
Structural–Framed Character¶
The entry lies toward the structural end of the structural–framed spectrum: feasible patterns, demand satisfaction, and objective comparison can be formalized and checked across unlike materials, yet actual stock types, admissible cuts, and valued costs retain a production frame. Vocabulary travel: stock, pattern and demand transfer among paper, metal and sheet processing, while a “pattern” must be redefined for each geometry. Evaluative weight: “less waste” or “minimum cost” is a chosen production aim, not a theorem that every use of stock should optimize the same metric. Institutional origin: operations research and industrial production planning gave the pattern-count formulation its recognizable name. Human-practice dependence: people specify orders, machines, permissible cuts and costs; the resulting feasibility and objective can then be checked mathematically. Import versus recognition: calling an arbitrary packing puzzle cutting stock imports a production-from-stock frame unless it actually has raw stock, demanded outputs and allowable cuts. Its character: a predominantly structural but still domain-specific problem family whose formal stock-to-order pattern is stable while dimensions, constraints and objectives are instance-dependent.[1][3][2]
Structural Core vs. Domain Accent¶
The broad structure is constrained optimization of objects placed into finite containers. That portable optimization reach is already supplied by live Optimization, indirectly through the proposed live Packing Problem parent. The domain accent is that the container is stock to be partitioned, the placed pieces are demanded outputs, and the plan selects allowable cuts and repetitions to fulfill an order. Those production-from-stock and order-fulfillment roles are necessary to the named identity, so Cutting Stock Problem stays domain-specific rather than becoming a new prime. A pure packing problem may have containers and nonoverlap but not a production demand or cutting process; a bare cutting instruction may have stock and a cut but not optimization over competing plans.[1][2]
This is why Packing Problem is a proposed genus, not a synonym. Its live definition includes optimization of arrangement in one or more containers; the narrower cutting-stock entry adds the stock-to-demand relation. Independent graph review must confirm that every admitted multistage variant remains a packing instance before accepting the proposed edge.
Instantiates / Related Primes¶
This entry is a kind of Packing Problem. A cutting-stock plan packs demanded items without overlap into stock units under a declared optimization objective.
Relationships to Other Abstractions¶
Current abstraction Cutting Stock Problem Domain-specific
Parents (1) — more general patterns this builds on
-
Cutting Stock Problem is a kind of Packing Problem Domain-specific
A cutting-stock plan packs demanded items without overlap into stock units under a declared optimization objective.Every admitted cutting-stock instance assigns nonoverlapping demanded pieces to one or more stock containers under capacity or geometric feasibility and optimizes the resulting arrangement. The narrower problem additionally requires production of specified item quantities by feasible cuts from raw stock and often counts pattern repetitions.
Hierarchy path (1) — routes to 1 parentless root
- Cutting Stock Problem → Packing Problem → Optimization
Neighborhood in Abstraction Space¶
Cutting Stock Problem sits in a sparse region of the domain-specific corpus (73rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Supply Chain & Inventory Management (28 abstractions)
Nearest neighbors
- Mass Customization — 0.85
- Assemble-to-order system — 0.84
- Economic Order Quantity — 0.83
- Portfolio Optimization — 0.83
- Quadratic Assignment Problem — 0.83
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
Bin packing: the simple uniform-stock one-dimensional formulation can be expressed as bin packing, but the cutting-stock name foregrounds repeated order types, stock production and cutting variants; the two are close enough to demand a careful catalog comparison, not automatic identity. Guillotine cutting: a restriction on rectangular cut patterns. Pattern minimization: reducing the number of distinct setups, potentially a separate objective from stock count. Column generation: a technique for handling many pattern variables in a relaxation, not the problem definition. Cutting-plane algorithms: methods for integer optimization with a similar word, not literal material cuts.[1][3][2]
References¶
[1] P. C. Gilmore and R. E. Gomory, “A Linear Programming Approach to the Cutting-Stock Problem,” Operations Research 9(6) (1961), 849–859, publisher abstract (problem statement, integer-versus-LP distinction, many variables). https://doi.org/10.1287/opre.9.6.849 registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o
[2] Julia Kallrath, Steffen Rebennack, Josef Kallrath and Rüdiger Kusche, “Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges,” European Journal of Operational Research 238(1) (2014), 374–389, publisher abstract and visible Introduction (standard master-roll model, variants and pattern-minimization distinction). https://doi.org/10.1016/j.ejor.2014.03.027 registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o
[3] P. C. Gilmore and R. E. Gomory, “Multistage Cutting Stock Problems of Two and More Dimensions,” Operations Research 13(1) (1965), 94–120, publisher abstract (higher-dimensional staged variants, knapsack-column limitations, corrugated-box sequencing). https://doi.org/10.1287/opre.13.1.94 registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n