Fact-checked by Grok 2 weeks ago

Cutting stock problem

The cutting stock problem is a fundamental optimization challenge in operations research and industrial engineering, involving the efficient partitioning of standard-sized stock materials—such as rolls of paper, sheets of metal, or bars of wood—into smaller items of specified sizes and quantities to meet production demands while minimizing material waste or the total number of stock items used.^[1] This problem arises in scenarios where raw materials must be cut to fulfill orders at minimal cost, often formulated as an integer linear programming task that balances demand satisfaction against trim losses.^[2] The origins of the cutting stock problem trace back to early work in linear programming and combinatorial optimization, with foundational contributions from Leonid Kantorovich in 1939 on resource allocation, though the modern formulation emerged in the 1960s.^[1] In 1961, Peter C. Gilmore and Ralph E. Gomory introduced a seminal linear programming approach that addressed the combinatorial explosion of possible cutting patterns through a technique known as delayed pattern generation or column generation, solving the one-dimensional case by iteratively generating feasible cutting patterns via knapsack subproblems.^[2] Their 1963 follow-up paper extended this method, demonstrating practical efficiency for large-scale instances and establishing the problem as a benchmark for decomposition algorithms in optimization. Subsequent developments in the 1970s and 1980s refined typologies for cutting and packing problems, with Harald Dyckhoff's 1990 classification system distinguishing variants based on dimensionality, item types, and constraints, later updated by Wäscher et al. in 2007 to provide a standardized framework widely adopted in research.^[3] Mathematically, the one-dimensional cutting stock problem (1D-CSP) is typically modeled as minimizing the number of stock rolls of fixed length W used to produce demanded quantities b_j of items of length a_j for j = 1, \dots, m, subject to constraints ensuring demand is met via non-negative integer combinations of cutting patterns.^[1] The two-dimensional variant (2D-CSP) extends this to rectangular sheets, incorporating guillotine cuts or more general patterns, which increases complexity due to geometric feasibility requirements.^[1] Exact solution methods rely on branch-and-price algorithms combining column generation with integer programming branching, while heuristics such as sequential first-fit or hybrid linear programming approaches offer practical approximations for real-time industrial use.^[1] Extensions like the cutting stock problem with usable leftovers (CSPUL) further consider remnants as potential future stock, enhancing sustainability in resource-constrained settings.^[4] Applications of the cutting stock problem span diverse industries, including paper and pulp manufacturing where rolls are slit into narrower widths to reduce trim losses, steel production for cutting bars or sheets to order specifications, and woodworking for efficient panel division.^[1] In metal fabrication, such as aluminum or copper processing, it optimizes coil or sheet utilization to minimize scrap, while in packaging like corrugated containers, it addresses two-dimensional guillotine cuts for cost-effective production.^[4] These implementations often integrate with enterprise resource planning systems, yielding significant savings in material costs in high-volume settings—and have influenced broader fields like supply chain optimization and sustainable manufacturing.^[5]

Overview and Illustration

Definition and Basic Concept

The cutting stock problem involves cutting standard-sized stock materials, such as rolls or sheets of paper, metal, or fabric, into smaller items of specified sizes and quantities to fulfill given demands while minimizing the total cost, typically measured by trim loss or the number of stock pieces used. This optimization challenge arises in manufacturing and resource allocation, where the goal is to efficiently utilize raw materials to reduce waste and production expenses.^[1] Key terms in the problem include stock material, which denotes the raw input available in fixed dimensions, such as rolls of uniform width; cutting patterns, which refer to the specific arrangements of cuts on a single stock piece to produce a combination of required items; trim waste, representing the unused portions left after cutting, often calculated as the difference between stock dimensions and the sum of item sizes in a pattern; and demand quantities, which specify the required numbers of each item type, sometimes with lower and upper bounds to account for flexibility in orders.^[1] These elements form the foundation for modeling the problem as a combinatorial optimization task. The basic workflow entails identifying feasible cutting patterns that satisfy the demand quantities for items without exceeding the stock dimensions, then selecting a combination of patterns that optimizes the objective.^[1] The problem is NP-hard, with its complexity stemming from its close relation to the bin packing problem, to which it can be reduced in principle.^[6]^[7] A simple one-dimensional case, involving linear cuts along a single axis, illustrates these concepts without the added intricacies of multi-dimensional arrangements.

One-Dimensional Example

Consider a simple illustrative example of the one-dimensional cutting stock problem, where stock rolls of fixed length 200 units must be cut to satisfy demands for two item types.^[1] The required items consist of 3 units of length 100 and 3 units of length 90, for a total demanded length of $3 \times 100 + 3 \times 90 = 570 units.^[1] To assess feasibility, a lower bound on the minimum number of stock rolls is obtained by dividing the total demanded length by the stock length and rounding up: \lceil 570 / 200 \rceil = 3 rolls.^[1] An upper bound can be established via a greedy packing heuristic, such as prioritizing larger items: one roll cut into two 100-unit items (using 200 units), one roll into two 90-unit items (using 180 units), and two additional rolls each for the remaining single 100-unit and 90-unit items (using 100 and 90 units each), yielding 4 rolls in total.^[1] Viable cutting patterns must satisfy the stock length constraint; for instance, patterns exceeding 200 units (e.g., three 100-unit items at 300 units) are infeasible.^[1] The possible viable patterns in this instance are limited due to the small number of item types and can be enumerated as follows:

Pattern	Composition	Total Length Used	Waste
1	2 × 100	200	0
2	1 × 100 + 1 × 90	190	10
3	2 × 90	180	20

These represent the non-dominated efficient patterns, with a total of 3 distinct options.^[1] An optimal solution requires exactly 3 rolls, each using Pattern 2 (one 100-unit item and one 90-unit item), for a total waste of $3 \times 10 = 30 units or 5% of the total stock length used (600 units).^[1] To manually verify this solution, confirm that the produced items meet demands (3 of 100 units and 3 of 90 units), the total length cut (570 units) matches the demand, and each pattern's length does not exceed 200 units, ensuring no overcutting occurs.^[1] This example demonstrates how the problem can be solved with minimal waste while satisfying all constraints.^[1]

Variants and Classifications

Cutting and packing problems, including the cutting stock problem, are classified using standardized typologies to distinguish variants based on key attributes. Dyckhoff's 1990 classification system categorizes problems by dimensionality (1D, 2D, 3D), item types (e.g., rectangular, irregular), and constraints (e.g., guillotine cuts, assortment limits). This was refined by Wäscher et al. in 2007, introducing criteria like input/output restrictions and objective functions, providing a framework widely used in research to compare and benchmark variants.^[8]

Dimensional Variants

The cutting stock problem extends across different spatial dimensions, adapting the core objective of minimizing waste from standard stock material to meet demand for smaller items. In one dimension, the problem involves linear arrangements; in two dimensions, it incorporates planar layouts; and in three dimensions, it addresses volumetric configurations. These variants influence the feasible cutting patterns and computational complexity, with higher dimensions often requiring specialized constraints to ensure manufacturability.^[4] The one-dimensional cutting stock problem focuses on dividing linear stock materials, such as rolls of paper, pipes, or cables, into segments of specified lengths using straight cuts along the length. This variant typically assumes guillotine cuts, where each cut spans the entire width of the stock perpendicular to its length, simplifying production on machines like slitting saws. Examples include optimizing paper roll trimming in printing industries to reduce trim loss.^[1]^[9] In the two-dimensional cutting stock problem, rectangular stock sheets—such as metal plates, glass panels, or wood for furniture—are cut into smaller rectangular or irregular pieces arranged in a plane. Cutting patterns here often employ guillotine cuts, which are through-cuts from one edge to the opposite edge, either horizontally or vertically, allowing staged partitioning of the sheet. Nesting patterns optimize the layout to maximize utilization, particularly for irregular shapes like clothing patterns or curved components, where pieces may be rotated or contoured to fit without overlap. This variant is prevalent in sheet metal fabrication and apparel manufacturing, where guillotine constraints align with guillotine shears or laser cutters.^[10]^[11]^[4] The three-dimensional cutting stock problem deals with volumetric stock, such as lumber blocks, foam, or metal ingots, partitioned into smaller three-dimensional items like boxes or structural components. It draws analogies to the three-dimensional bin packing problem, where items are orthogonally placed without overlap to minimize the number of bins or stock volume used. Packing can be orthogonal, aligning faces parallel to the stock axes for simplicity, or non-orthogonal, permitting rotations in three axes for denser arrangements, though the latter increases complexity. Guillotine cuts extend to planes slicing through the entire stock in one dimension at a time, facilitating multi-stage sawing in woodworking or foam cutting. Applications include optimizing lumber yields in construction and minimizing scrap in packaging materials.^[12]^[13]^[4] Related problems within dimensional variants include specialized cases like two-dimensional and three-dimensional guillotine cutting, which enforce recursive through-cuts for efficient production; strip packing, a 2D variant where stock has fixed width but unbounded length, minimizing total length used; and shelf packing, a guillotine-restricted strip packing approach that builds horizontal "shelves" of equal height before vertical cuts. These serve as subproblems or approximations in broader cutting stock formulations, particularly for unbounded or semi-continuous stock.^[14]^[15]

Constraint-Based Variants

In constraint-based variants of the cutting stock problem, additional operational restrictions arise from production processes, machinery limitations, or material properties, extending the basic formulation to better reflect real-world manufacturing constraints. These variants emphasize rules governing cutting sequences, equipment capabilities, or item attributes, rather than purely dimensional aspects. Such extensions are crucial in industries like paper and metal processing, where ignoring these constraints can lead to infeasible or inefficient solutions.^[1] The two-stage cutting stock problem involves an initial phase of slitting large stock rolls into intermediate strips, followed by a second phase of cross-cutting those strips into final items, commonly encountered in the paper industry to accommodate sequential machinery operations. This variant introduces linking constraints between stages to ensure intermediate outputs match subsequent inputs, often modeled using column generation to generate feasible patterns across both phases. Seminal work on this formulation has shown that solving the stages separately can lead to higher waste compared to integrated approaches, highlighting the need for coordinated optimization.^[16]^[17] Winder constraints impose fixed slitting widths or knife positions due to roll winder machinery limitations, typically in one-dimensional contexts where stock rolls must be divided into predefined intermediate widths before further processing. These restrictions limit pattern flexibility, requiring optimization to select compatible slitting configurations that minimize trim loss while satisfying equipment tolerances, such as minimum or maximum strip widths. In steel slitting lines, heterogeneous winder setups add allocation decisions, where assigning orders to specific machines respects varying capacity constraints, improving solution feasibility by 15-20% compared to existing industrial operations in benchmarks.^[18]^[19] Assortment problems focus on selecting a fixed number of cutting patterns or minimizing changes between patterns to enhance production efficiency, particularly when setup costs for pattern reconfiguration are significant. This variant optimizes a limited set of reusable assortments to cover demands, balancing waste reduction with operational simplicity; for instance, reducing the number of patterns can decrease inventory costs by around 30% while increasing trim loss by about 2% in roll-based applications. Generalized assortment models extend this by incorporating variable stock lengths, prioritizing patterns that maximize utilization across multiple orders.^[20]^[21] Other constraint-based variants include vector packing, where items have multiple attributes (e.g., length and quality) packed into multidimensional bins with vector-based compatibility rules, generalizing traditional cutting to handle non-scalar constraints. Multiple stock sizes introduce heterogeneous input rolls of varying lengths or widths, requiring inventory-aware optimization to select and cut from available stocks while minimizing overproduction. Quality grades add constraints on assigning higher-grade stock to lower-grade demands (overgrading) to avoid waste, often modeled with hierarchical objectives. Defect handling involves avoiding or minimizing cuts near material flaws, such as in sheet metal with faults, where robust optimization ensures viable patterns by excluding defective regions in automotive applications.^[22]^[23]^[24]

Real-World Applications

Traditional Industries

The cutting stock problem has long been central to the paper and pulp industry, where large master rolls are slit into narrower widths to produce newspapers, packaging materials, and other high-volume products. This one-dimensional variant involves generating cutting patterns to meet demand while minimizing trim waste, which arises from the difference between roll widths and required item sizes. Optimization techniques, such as column generation, enable efficient pattern selection, reducing material loss in continuous production processes.^[25]^[26] In metalworking, the problem manifests in two-dimensional sheet metal cutting for components used in automotive parts and appliances. Guillotine shears perform straight, edge-to-edge cuts on rectangular stock sheets to yield required rectangles, often under constraints like defect avoidance or setup costs. This application prioritizes minimizing scrap sheets and overproduction to lower inventory and processing expenses in manufacturing lines.^[27]^[28] The textiles and leather sectors address a more complex two-dimensional irregular variant, where fabric rolls or animal hides are cut into non-rectangular patterns for clothing and upholstery. Irregular shape handling requires nesting algorithms to arrange pieces without overlap, accounting for material defects and grain direction to maximize utilization. This is particularly challenging in make-to-order production, where custom orders demand flexible layouts to avoid excessive offcuts.^[29]^[30] In wood and lumber processing, the problem often involves two-stage cutting: first trimming rough boards into standardized widths and lengths, then subdividing them into final pieces for furniture or construction. This sequential approach handles variable stock dimensions and defects, using guillotine cuts to produce rectangular items while minimizing end waste and offcuts. Two-stage models integrate initial lumber selection with secondary patterning for overall efficiency.^[31]^[32] Across these industries, solving the cutting stock problem yields substantial quantitative impacts, such as waste reductions of 5-15% in paper mills through optimized slitting patterns, enhancing resource efficiency in high-volume operations. Similar savings in material utilization have been reported in wood processing, where algorithmic improvements boost board usage by over 2% compared to traditional methods.^[26]^[33]^[31]

Contemporary Uses and Sustainability

In recent years, the cutting stock problem (CSP) has found applications in additive manufacturing (AM) and 3D printing, where it aids in optimizing the use of materials such as filaments or powders to minimize waste during production planning. Algorithms like the pixel-based AM packing algorithm (PAMPA) address two-dimensional irregular packing constraints in processes such as selective laser melting, enabling efficient arrangement of parts within build volumes while allowing rotations and hole filling to maximize material utilization. This integration often occurs alongside computer-aided design (CAD) systems, where CSP formulations help sequence part placements to reduce makespan and enhance machine efficiency, achieving packing densities up to 0.850 in benchmark instances. Such approaches have demonstrated runtime improvements of up to 164 times compared to prior methods, supporting scalable production in industries transitioning to customized manufacturing.^[34] In the electronics sector, particularly for printed circuit boards (PCBs), CSP variants facilitate panelization by determining optimal layouts to cut multiple boards from larger stock panels, thereby minimizing scrap in high-tech assembly lines. Heuristic-based cutting stock procedures tailored for PCB production incorporate databases of parts and materials, using linear programming for planning to handle constraints like guillotine cuts and defect avoidance, which can reduce material waste by optimizing panel yields. This is especially critical in high-volume electronics manufacturing, where panelization techniques such as routing or laser cutting from arrayed stock directly apply rectangular CSP models to lower production costs and improve throughput. Recent implementations emphasize automated layout optimization to accommodate varying board geometries, ensuring minimal offcuts while maintaining electrical integrity.^[27] Sustainability considerations have elevated the role of CSP in promoting waste minimization and the circular economy, particularly through variants like the cutting stock problem with usable leftovers (CSPUL), which reuses remnants for future demands instead of discarding them. By generating fewer but larger leftovers, CSPUL models can achieve up to 55% less waste than traditional CSP approaches, reducing raw material consumption and environmental impacts in resource-intensive sectors like metalworking and woodworking. This aligns with circular economy principles by extending material lifecycles, lowering recycling energy needs, and decreasing transportation of waste, thereby supporting broader goals of resource efficiency. In the European Union, post-2020 green manufacturing directives, such as the Circular Economy Action Plan (CEAP) of 2020, emphasize sustainable product design and waste reduction, where CSP optimizations contribute to compliance by enabling precise material use in manufacturing processes to cut greenhouse gas emissions and foster eco-friendly supply chains.^[4] Modern integrations of CSP with machine learning (ML) enhance demand forecasting for cutting plans, allowing dynamic adjustments to stock usage amid variable orders. ML models, such as neural networks, predict optimal dual variables in CSP formulations using inputs like item sizes and demands, achieving prediction accuracies (R² up to 0.82) that accelerate column generation solvers and halve solution times for instances with 100 items. In supply chain contexts, particularly e-commerce packaging, CSP-inspired bin packing optimizes box selections and layouts to reduce shipping volumes and costs, integrating with ML-driven forecasts to handle fluctuating order profiles and minimize over-packaging. These advancements enable real-time optimization in fulfillment centers, where algorithms balance item arrangements to cut dimensional weight fees and support just-in-time inventory.^[35] Post-2020 case studies illustrate CSP's application in automotive recycling, where it optimizes cutting of recycled plastics to maximize usable yields from end-of-life vehicles (ELVs). In the EU automotive sector, which uses approximately 5.2 million tons of plastic annually with only 2.9% recycled content reintegrated, CSPUL models address supply chain challenges by processing mixed post-consumer waste into standardized sheets for components like under-hood parts, blending up to 90% recycled material with virgin plastics to meet durability standards. Such implementations highlight CSP's potential to scale recycled content, aiding transitions to electric models with recyclable polypropylene. As of September 2025, the European Parliament has proposed a 20% minimum recycled plastic content target for new vehicles under the ongoing negotiations for the proposed 2023 End-of-Life Vehicles Regulation, to boost circularity and address the approximately 800,000 tons of annual plastic waste from ELVs in Europe.^[36]^[37]^[38]^[39]^[40]

Historical Development

Early Formulations

The cutting stock problem traces its origins to the late 1930s in the Soviet Union, where mathematician Leonid Kantorovich applied emerging mathematical techniques to industrial optimization challenges. In 1939, while consulting for the Plywood Trust in Leningrad, Kantorovich formulated methods for efficiently cutting plywood sheets to meet production demands while minimizing waste, situating the problem within the broader framework of linear programming for economic resource allocation under planned production.^[41]^[42] Kantorovich detailed these ideas in his influential book Mathematical Methods of Organizing and Planning Production, which introduced systematic approaches to production planning, including algorithmic pattern selection for material cutting to optimize resource use in socialist economies.^[43] This work emphasized the economic implications of waste reduction, treating cutting as a linear optimization task amenable to mathematical resolution despite limited computational tools at the time.^[41] Following World War II, the rise of operations research in Western manufacturing sectors brought renewed attention to similar material-cutting inefficiencies, particularly in industries like paper and metals where stock rolls or sheets needed to be trimmed to order specifications. In the 1950s, as integer programming emerged as a tool for discrete decision problems, early formulations of the cutting stock problem began to incorporate integer constraints to account for indivisible cutting patterns, marking its recognition as a core combinatorial optimization challenge.^[44]^[45] A pivotal early publication expanding on Kantorovich's ideas appeared in 1951, when he collaborated with V.A. Zalgaller on Calculation of Rational Cutting of Stock, a comprehensive treatment applying linear programming to practical industrial scenarios such as metal and textile cutting, complete with manual solution procedures and economic analyses.^[46]^[47] This book introduced iterative methods for generating feasible cutting patterns—effectively reducing subproblems to knapsack-like optimizations—predating widespread computer use and influencing subsequent operations research methodologies.^[48] In the West, one of the first explicit formulations came in 1956 from A.E. Paull, who proposed a linear programming model for the "trim problem" in newsprint production, aiming to minimize roll waste by selecting optimal cutting combinations to satisfy customer widths.^[49]^[50] Paull's approach highlighted the problem's practical scale in high-volume manufacturing, demonstrating potential savings through mathematical planning.^[51] Kantorovich's Soviet contributions, though initially isolated due to geopolitical barriers, gradually permeated Western operations research circles, providing foundational concepts for resource allocation that shaped the problem's evolution into a standard optimization benchmark.^[52]

Key Advancements

A pivotal advancement in the 1960s was the introduction of column generation techniques for solving one-dimensional cutting stock problems, pioneered by Gilmore and Gomory. In their seminal work, they formulated the problem as a linear programming relaxation and developed an algorithm that dynamically generates cutting patterns (columns) only as needed, addressing the challenge of an exponentially large number of possible patterns. This approach, detailed in subsequent publications, included a delayed column generation heuristic that iteratively solves the restricted master problem and the knapsack subproblem to identify improving patterns, significantly improving computational efficiency for practical instances.^[53] During the 1970s and 1980s, research extended these methods to two-dimensional variants, particularly those restricted to guillotine cuts, where each cut spans the entire remaining sheet. Christofides and Whitlock proposed a tree-search algorithm that enumerates feasible guillotine patterns while respecting demand constraints, enabling exact solutions for moderate-sized problems in industries like steel and glass manufacturing.^[54] Concurrently, the integration of integer programming solvers, such as branch-and-bound methods, allowed for handling the integrality requirements of pattern multiplicities, with early implementations demonstrating reduced waste in real-world applications compared to manual planning.^[1] Known to be NP-hard since the late 1970s,^[55] the cutting stock problem's computational complexity motivated the rise of metaheuristic integrations in the 1990s to tackle larger, more diverse instances. To address this, metaheuristics like genetic algorithms were adapted, with Hinterding and Khan introducing chromosome representations for patterns that evolve to minimize stock usage, achieving near-optimal solutions faster than traditional column generation for non-guillotine cases.^[56] In the 2000s, milestones included the development of open-source implementations that democratized access to advanced solvers, such as extensions of the LP-based models in tools like GLPK, facilitating experimentation and customization for specific industries.^[57] Additionally, multi-objective formulations emerged to balance waste minimization with production costs, incorporating setup times and material variability; for instance, approaches optimizing both trim loss and pattern diversity reduced overall expenses by up to 15% in textile applications.^[58] Post-2010 developments have focused on hybrid approaches combining optimization with artificial intelligence to enhance scalability for large-scale instances. Machine learning techniques, such as predicting dual variables to stabilize column generation, have accelerated convergence, solving instances with thousands of items in seconds where classical methods took hours. Recent work as of 2025 has further emphasized sustainable variants, such as the cutting stock problem with usable leftovers, and efficient optimization for industries like steel production.^[35]^[4]^[59] Comprehensive surveys have highlighted these hybrids' effectiveness, noting improvements in solution quality and runtime for high-volume problems in sustainable manufacturing, while emphasizing ongoing challenges in multi-dimensional extensions.^[57]

Mathematical Foundations

Integer Linear Programming Model

The integer linear programming (ILP) model provides a formal mathematical framework for the one-dimensional cutting stock problem, where the goal is to minimize the number of stock pieces used to satisfy demands for smaller items while adhering to the fixed stock length. Let I = \{1, \dots, n\} denote the set of item types, each with length w_i > 0 and demand b_i \in \mathbb{Z}_{\geq 0}. The stock length is W > 0. Let J be the (potentially infinite) set of all feasible cutting patterns, where a_{ij} \in \mathbb{Z}_{\geq 0} represents the number of copies of item i in pattern j, ensuring feasibility via \sum_{i \in I} w_i a_{ij} \leq W for all j \in J. The cost c_j \geq 0 is typically set to 1 for each pattern to minimize the total number of stocks used.^[60]^[1] The decision variables are x_j \in \mathbb{Z}_{\geq 0} for j \in J, denoting the number of times pattern j is applied. The ILP formulation is then given by:

\begin{align} \min &\quad \sum_{j \in J} c_j x_j \\ \text{s.t.} &\quad \sum_{j \in J} a_{ij} x_j \geq b_i, \quad \forall i \in I \\ &\quad x_j \in \mathbb{Z}_{\geq 0}, \quad \forall j \in J. \end{align}

This model ensures demand satisfaction while minimizing waste implicitly through the objective. The challenge arises from the vast size of J, which enumerates all possible ways to pack items into a stock of length W.^[60]^[61] To address the pattern set J, feasible patterns are generated by solving a knapsack subproblem, formulated as an integer program for each iteration of a column generation procedure. Given dual prices \pi_i \geq 0 from the Lagrangian dual of the relaxed master problem (one per item type i), the subproblem maximizes the reduced profit:

\begin{align} \max &\quad \sum_{i \in I} \pi_i y_i \\ \text{s.t.} &\quad \sum_{i \in I} w_i y_i \leq W \\ &\quad y_i \in \mathbb{Z}_{\geq 0}, \quad \forall i \in I, \end{align}

where y_i is the number of copies of item i in the new pattern. If the optimal value exceeds 1 (assuming c_j = 1), the resulting pattern (a_{i \cdot}) = (y_i) is added to J as a column in the master problem. This subproblem is a classical unbounded knapsack problem, solvable via dynamic programming in pseudo-polynomial time.^[60]^[1] A common approach to obtain bounds and facilitate solution involves relaxing the integrality constraints on x_j, yielding the linear programming (LP) relaxation:

\begin{align} \min &\quad \sum_{j \in J} c_j x_j \\ \text{s.t.} &\quad \sum_{j \in J} a_{ij} x_j \geq b_i, \quad \forall i \in I \\ &\quad x_j \geq 0, \quad \forall j \in J. \end{align}

The optimal LP value serves as a lower bound on the ILP optimum. The integrality gap, defined as the difference between the ILP and LP optimal values, measures the suboptimality of the relaxation; for cutting stock instances, this gap is often small with an upper bound of 4/3 in the divisible case, though practical instances typically exhibit gaps less than 1%. Techniques like column generation solve the LP iteratively, with subsequent integer rounding or branching to close the gap.^[60]^[62]

Pattern Generation and Column Generation

In the cutting stock problem, pattern generation involves dynamically creating feasible cutting patterns that minimize waste while satisfying demand constraints. Each pattern represents a way to cut a stock item into smaller pieces, formulated as a solution to a knapsack subproblem where the objective is to maximize the value of packed items (pieces) subject to the stock's capacity. The subproblem is solved as an integer linear program: maximize \sum_i \pi_i y_i subject to \sum_i w_i y_i \leq W and y_i \in \mathbb{Z}_{\geq 0}, where w_i is the width of piece type i, W is the stock width, and \pi_i are dual multipliers from the master problem. This pricing problem identifies new columns (patterns) with negative reduced costs, which are then added to the formulation to improve the solution. The column generation algorithm operates within the linear programming (LP) relaxation of the integer linear programming model for the cutting stock problem. It begins by solving a restricted master LP with an initial set of patterns, yielding optimal dual prices \pi_i \geq 0 for the demand constraints \sum_j a_{ij} x_j \geq b_i. A new pattern j is generated if its reduced cost $1 - \sum_i a_{ij} \pi_i < 0, where a_{ij} is the number of pieces of type i in pattern j. The subproblem solution provides the a_{ij} values, and the column is added to the master problem if beneficial. This process iterates—re-solving the master LP and pricing subproblem—until no improving column exists, achieving optimality for the LP relaxation.^[63] To obtain integer solutions efficiently, delayed column generation incorporates the Gilmore-Gomory heuristic, which solves the LP relaxation iteratively without enumerating all patterns upfront and then rounds the fractional solution to a feasible integer one. In this approach, patterns are generated on demand during the LP iterations, and upon convergence, the LP solution's x_j values are rounded up to the nearest integer to form a valid cutting plan, often yielding near-optimal results with minimal waste. This heuristic balances computational tractability and solution quality, as demonstrated in early applications to paper industry instances.^[64]^[65] Column generation can suffer from convergence issues, notably the tail-off effect, where progress slows dramatically near optimality due to primal degeneracy and oscillating dual variables, requiring many iterations with marginal improvements. This is particularly pronounced in large-scale cutting stock instances, leading to excessive master problem sizes. Stabilization techniques mitigate this by smoothing dual prices, such as introducing a proximal penalty term in the dual formulation to bound deviations from a stability center (a reference dual feasible solution), using piecewise-linear functions to control oscillations and accelerate convergence.^[66]^[67] Extensions to two-dimensional cutting stock problems adapt column generation by incorporating geometric constraints in pattern generation, often using solvers that enumerate feasible layouts via dynamic programming or guillotine-cut restrictions to handle rectangular stock and piece placements. In multistage formulations, patterns are generated hierarchically—first for coarse cuts, then refined—ensuring orthogonality and non-overlap while solving knapsack-like subproblems for each stage. This approach, pioneered for higher dimensions, enables exact solutions for complex layouts without exhaustive enumeration.^[17]

Solution Approaches

Exact Methods

Exact methods for the cutting stock problem (CSP) provide algorithms that guarantee optimal integer solutions to the integer linear programming formulation, minimizing the number of stock pieces used while satisfying demand constraints. These approaches address the challenge of the vast number of possible cutting patterns by systematically exploring the solution space, often building on linear programming relaxations solved via column generation as a subroutine. Originating from the seminal work of Gilmore and Gomory, which introduced column generation for the LP relaxation, exact methods extend this to enforce integrality for practical instances. Branch-and-bound techniques apply directly to the CSP's integer formulation, branching on the non-integer variables x_j, which represent the number of times each cutting pattern j is used, or on decisions about pattern inclusion to enforce integrality. In the binary variant of the CSP, where patterns are used at most once (x_j \in \{0,1\}), branch-and-bound proceeds after generating promising columns, using LP bounds to prune suboptimal branches and ensuring the global optimum by exploring the decision tree. This method effectively handles the integrality gap but can suffer from weak bounds without additional cuts. Computational studies show it solves moderate-sized instances, such as those with 50-100 items, within reasonable time by leveraging strong relaxations. Branch-and-price combines branch-and-bound with column generation, dynamically generating patterns at each node of the search tree to manage the exponential number of variables while maintaining tight LP bounds. Branching occurs on fractional variables using specialized rules, such as the Ryan-Foster scheme, which branches on item-pattern assignments to avoid symmetry and ensure compatibility with column generation. For the one-dimensional CSP, two variants—one with binary variables and another with general integers—demonstrate comparable performance, with the general integer version often requiring fewer nodes due to reduced branching overhead. Acceleration techniques, including stabilization via dual fixing to bound dual prices and prevent tailing-off in convergence, enhance efficiency; for instance, dual fixing eliminates columns with negative reduced costs early in the process. This approach solves real-world instances originating from Gilmore-Gomory benchmarks optimally.^[68]^[69] Dynamic programming offers an exact solution for small one-dimensional CSP instances by enumerating all feasible cutting patterns through state-based recursion, typically modeling the knapsack subproblem to build patterns that fill stock lengths without exceeding item demands. For instances with few item types (e.g., up to 10-20 distinct lengths) and small total demand, DP computes the minimum number of stocks by solving a shortest-path formulation over states representing remaining demands, achieving optimality without relaxation. This method's pseudo-polynomial time complexity limits its use to cases where the state space remains manageable.^[70] Modern mixed-integer programming solvers, such as CPLEX and Gurobi, tackle the CSP using compact formulations that avoid explicit pattern enumeration, instead introducing variables for assigning individual items to specific stock pieces (e.g., y_{ik} indicating if item i is cut from stock k). These models, often with additional constraints for pattern feasibility like non-overlap via big-M or clique inequalities, are solved via branch-and-cut, generating cutting planes to tighten bounds. While effective for instances with up to 50-100 items, the exponential growth in variables (proportional to items times stocks) restricts scalability compared to column-based methods. In steel industry applications, such formulations achieve substantial waste reductions, up to 80% on average in a case study.^[71] Performance benchmarks highlight the scalability limits of exact methods, with branch-and-price solving instances up to ~1000 items to optimality in seconds to ~15 minutes on modern hardware, achieving 100% optimality on benchmark sets with 200-800 items. These results underscore the trade-off between optimality guarantees and computational demands for larger problems.^[72]

Heuristic and Approximation Techniques

Heuristic and approximation techniques play a crucial role in solving the cutting stock problem (CSP), particularly for large-scale instances where exact methods are computationally prohibitive, prioritizing efficiency and near-optimal solutions over guaranteed optimality. These approaches draw from the closely related bin packing problem, where the goal is to pack items into bins of fixed capacity to minimize the number of bins used, offering practical speed advantages in industrial applications such as paper manufacturing and metal fabrication.^[73] One of the most foundational heuristics is the first-fit decreasing (FFD) algorithm, which sorts items in non-increasing order of size and then greedily assigns each item to the first feasible cutting pattern (or bin) that can accommodate it without exceeding the stock length. This method ensures a structured packing that reduces fragmentation early on. For the one-dimensional CSP, FFD provides an approximation guarantee, producing a solution whose cost is at most \frac{11}{9} \mathrm{OPT} + 1, where OPT is the optimal number of stock pieces, establishing its bounded performance relative to the optimum.^[74]^[75] Complementing FFD are best-fit decreasing (BFD) and worst-fit (WF) heuristics, which also sort items decreasingly but differ in assignment: BFD places each item into the pattern that minimizes the remaining unused space (tightest fit), while WF maximizes the leftover space to potentially allow larger future items. These variants aim to balance waste distribution across patterns, with BFD often yielding lower overall trim loss in practice compared to FFD, though WF can promote diversity in pattern utilization for diverse item sets. Both share the same asymptotic approximation ratio as FFD, \frac{11}{9} \mathrm{OPT} + 1, making them reliable for quick approximations in one-dimensional CSP.^[58]^[74] Metaheuristics extend these greedy approaches by exploring broader solution spaces through iterative improvement. Genetic algorithms (GAs) treat cutting patterns as chromosomes, evolving populations via selection, crossover, and mutation to optimize pattern combinations that minimize stock usage, particularly effective for generating diverse feasible patterns in multi-objective CSP formulations. Simulated annealing (SA) has been adapted for two-dimensional nesting variants of the CSP, starting from an initial layout and probabilistically accepting worse solutions to escape local optima, gradually cooling to refine nestings with reduced overlap and waste. Tabu search (TS) maintains a short-term memory of recent moves to avoid cycling, applied to one-dimensional CSP by iteratively modifying pattern multiplicities or compositions to lower total stock demand. These methods often outperform pure greedy heuristics on complex instances by incorporating global search elements.^[76]^[77] Local search techniques focus on refining initial solutions generated by heuristics like FFD, defining neighborhoods through operations such as swapping items between patterns, inserting additional items into underutilized spaces, or adjusting pattern frequencies. These moves are evaluated for improvement in total stock usage, with multi-start variants initializing multiple local searches from diverse starting points to enhance solution quality and avoid premature convergence. In two-dimensional CSP, such searches can iteratively reposition rectangles to minimize guillotine cuts or irregular waste, achieving substantial reductions in material loss over baseline heuristics.^[78]^[79] Recent post-2020 developments integrate machine learning (ML) into hybrid heuristics, using deep reinforcement learning to generate high-quality initial patterns, as demonstrated in one-dimensional CSP solvers where neural networks learn demand-aware pattern policies. Recent 2024-2025 works include DRL-based column generation for 2D bounded-size CSP and the OPTICUT heuristic for 1D pattern minimization. Additionally, heuristics for CSP variants, such as those with usable leftovers, provide near-optimal solutions under restricted demand patterns, enabling bounded errors in sustainable manufacturing contexts.^[80]^[81]^[82]^[4]

Modern Computational Tools

Modern computational tools for the cutting stock problem encompass a range of optimization solvers, specialized software, and programming libraries that facilitate efficient modeling and solution of integer linear programming (ILP) formulations, particularly those involving column generation.^[83] Commercial solvers such as IBM ILOG CPLEX and Gurobi Optimizer are widely used for their robust performance in handling large-scale ILP instances of the cutting stock problem, including variants with multiple master rolls and demand constraints.^[84] These solvers employ advanced branch-and-cut-and-price algorithms to achieve optimality or near-optimality, often outperforming open-source alternatives in terms of solution speed and scalability for industrial applications.^[85] Open-source options like SCIP (Solving Constraint Integer Programs) and COIN-OR CBC (Branch and Cut) provide accessible alternatives, supporting column generation and set partitioning models for one- and two-dimensional cutting stock problems without licensing costs.^[86]^[87] Specialized software addresses domain-specific needs, such as heuristic optimization for irregular shapes in two- and three-dimensional settings. OptaPlanner, an open-source constraint solver, applies local search and tabu search heuristics to cutting stock variants, minimizing waste in resource allocation scenarios like paper or metal cutting.^[88] For 2D nesting tasks common in manufacturing, tools like SVGNest and DeepNest offer automated layout generation for CNC and laser cutting, incorporating features such as part-in-part nesting and line merging to reduce material usage.^[89]^[90] Programming libraries enable flexible implementation in modern languages, integrating cutting stock models with broader workflows. In Python, PuLP provides a user-friendly interface for defining ILP models and interfacing with solvers like CPLEX or CBC, as demonstrated in tutorials solving rod-cutting instances with minimal waste.^[85] Google's OR-Tools supports constraint programming and linear optimization for bin-packing approximations of cutting stock, suitable for rapid prototyping in supply chain applications. Julia's JuMP package excels in high-performance computing for column generation, allowing efficient handling of dynamic pattern sets in one-dimensional problems.^[63] Post-2020 advancements include cloud-based deployments and machine learning enhancements for scalability and pattern prediction. Cloud platforms like Gurobi Instant Cloud and SAS Viya enable distributed solving of large-scale cutting stock instances, reducing computation times for problems with thousands of items by leveraging elastic resources. Machine learning integrations, such as neural networks for predicting dual variables in column generation, have improved solution times by up to 50% over traditional methods in benchmark tests.^[35] Deep reinforcement learning approaches generate cutting patterns adaptively, achieving near-optimal results on instances up to 1000 items with training on synthetic data.^[80] Enterprise integrations, such as APIs in SAP Integrated Business Planning, allow embedding cutting stock optimization into inventory management systems for real-time demand fulfillment. Recent 2024-2025 advancements include extended branch-cut-and-price frameworks using Ryan-Foster branching for stronger relaxations.^[91] Benchmarks and accessibility are supported by repositories like BPPLIB, which provides standardized instances for one- and two-dimensional cutting stock problems, enabling comparative evaluation of tools on datasets ranging from small (10-50 items) to large-scale (over 1000 items). These instances highlight computational challenges, where exact methods in solvers like Gurobi can require hours for 1000+ item problems due to exponential pattern growth, underscoring the value of heuristic libraries for practical deployment.^[84]

References

[1]
[PDF] Cutting stock problems and solution procedures
Abstract: This paper discusses some of the basic formulation issues and solution procedures for solving one- and two- dimensional cutting stock problems.Missing: history | Show results with:history
[2]
A Linear Programming Approach to the Cutting-Stock Problem
In this paper, a technique is described for overcoming the difficulty in the linear programming formulation of the problem.
[3]
History – ESICUP – EURO Special Interest Group on Cutting and ...
The first appearance of the cutting stock problem is attributed to Gilmore and Gomory (1961), although I have found citations that attribute the name to ...Missing: key | Show results with:key
[4]
Cutting stock problem with usable leftovers: A review - ScienceDirect
Mar 22, 2025 · This article presents a comprehensive literature review of the Cutting Stock Problem with Usable Leftovers (CSPUL).
[5]
(PDF) Applications of Cutting Stock Problem - ResearchGate
Aug 16, 2025 · It is the problem of filling an order at minimum cost for specified numbers of lengths of material to be cut to given stock lengths of given cost.
[6]
[PDF] One-dimensional Cutting Stock Problem with Divisible Items - arXiv
Abstract. This paper considers the one-dimensional cutting stock problem with divisible items, which is a new problem in the cutting stock literature.
[7]
[PDF] Solving Bin Packing Related Problems Using an Arc Flow Formulation
In principle, the bin packing problem and the cutting stock problem are equivalent. However, the bin packing problem takes a list of items as input, while ...<|control11|><|separator|>
[8]
[PDF] AN ALGORITHM FOR SOLVING THE ONE DIMENSIONAL ...
the one dimensional cutting stock problem often generates cutting patterns that are to be done a fractional number of times. To overcome this, non-integer ...
[9]
Two-dimensional cutting stock problem research - ScienceDirect.com
This paper addresses the problem of sequencing a torch for the cutting of a stock sheet nested with regular or irregular parts. The image of the nesting is ...
[10]
A GRASP meta-heuristic for two-dimensional irregular cutting stock ...
May 9, 2015 · In this paper, two-dimensional irregular cutting stock problem—a nesting problem that differs from other in their irregular shape of the pieces ...
[11]
The Three-Dimensional Bin Packing Problem | Operations Research
The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into the minimum number of three-dimensional ...
[12]
Algorithms for 3D guillotine cutting problems: Unbounded knapsack ...
We present algorithms for the following three-dimensional (3D) guillotine cutting problems: unbounded knapsack, cutting stock and strip packing.
[13]
Exact algorithms for the guillotine strip cutting/packing problem
The strip cutting/packing problem involves cutting a strip into subrectangles, using guillotine cuts, to minimize the length of the strip filled.
[14]
[PDF] Two-Dimensional Cutting Problem - IIASA PURE
In this work we present basic results for two-dimensional cutting problem. This problem consists in cutting a set of pieces from a sheet of material in order ...
[15]
[PDF] Solving the Two-Stage Cutting Stock Problem
GILMORE PC & GOMORY RE (1963) Multistage cutting- stock problems of two and more dimensions. Op.~ Res. The solution time for this problem was less. 11, 94-120.<|control11|><|separator|>
[16]
[PDF] Algorithms for the One-Dimensional Two-Stage Cutting Stock Problem
Cutting stock problems are, in general, defined by column-based formulations in which variables correspond to cutting patterns. To overcome the difficulty ...<|control11|><|separator|>
[17]
On solving the 1.5-dimensional cutting stock problem with ...
On solving the 1.5-dimensional cutting stock problem with heterogeneous slitting lines allocation in the steel industry☆ ... constraints imposed by the slitting ...
[18]
A heuristic algorithm to improving the coil slitting process in the steel ...
Jan 30, 2025 · This particular type of problem is known as the Cutting Stock Problem ... These constraints are specific to each slitting line and also depend on ...<|control11|><|separator|>
[19]
The generalized assortment and best cutting stock length problems
Aug 7, 2025 · This paper introduces two new one-dimensional cutting stock models: the generalized assortment problem (GAP) and the best cutting stock ...
[20]
[PDF] Roll Assortment Optimization in a Paper Mill - Cirrelt
This approach is very cost effective as inventory costs are minimal and trim costs can be minimized using an appropriate two-phase cutting stock problem ...
[21]
Vector Packing - Arc-flow VPSolver
By means of reductions to vector packing, several cutting & packing problems, including the one-dimensional bin packing and cutting stock problems, can be ...
[22]
A hierarchical approach for one-dimensional cutting stock problems ...
Overgrading is defined as using a higher quality metallurgical grade than the grade originally specified by a customer to fill an order (or part of an order).<|control11|><|separator|>
[23]
Robust stock assortment and cutting under defects in automotive ...
Jul 23, 2022 · We develop a formally rigorous framework to address the problem when stock sheets can be affected by faults, providing and testing mathematical ...
[24]
[PDF] A Linear Programming Approach to the Cutting Stock Problem
The paper describes a new and faster knapsack method, formulation changes, and experiments such as one giving waste as a function of stock length. The methods ...
[25]
Solving real-world cutting stock-problems in the paper industry
We discuss cutting stock problems (CSPs) from the perspective of the paper industry and the financial impact they make. Exact solution approaches and ...Missing: savings | Show results with:savings
[26]
Cutting Stock Problems in the Paper and Sheet Metal Industries
The problems of cutting the available jumbo rolls into rolls of smaller widths, or master sheets of sheet-metal into components of specified dimensions as ...Missing: automotive | Show results with:automotive
[27]
The integrated lot sizing and cutting stock problem in an automotive ...
In this paper, a manufacturer of automotive springs is studied in order to reduce inventory costs and losses in the steel bar cutting process.
[28]
[PDF] Minimizing waste in the 2-dimensional cutting stock problem
Aug 6, 2002 · cutting stock problem. This problem is applicable to industries including leather, glass, and sheet-metal cutting and garment manufacturing.
[29]
New constructive algorithms for leather nesting in the automotive ...
The Leather Nesting Problem (LNP) is a two-dimensional cutting stock problem that consists in finding the best layouts for a set of irregular shapes within the ...Missing: upholstery | Show results with:upholstery
[30]
Solution to Solid Wood Board Cutting Stock Problem - MDPI
This paper investigates the solid wood board cutting stock problem (CSP) and establishes an optimization model, with the goal of the highest possible ...
[31]
A cutting stock problem in the wood products industry: a two‐stage ...
Apr 26, 2020 · In this study, a cutting stock problem is addressed to determine the width/length of the wooden boards and select lumber in standard lengths ...
[32]
Smart Cuts, Less Scrap: A 1D Cutting Stock Problem - Nightingale HQ
Aug 21, 2025 · Industry averages suggest scrap rates around 2.5%, but in some regions they are reported to be 8% and higher. This scale of inefficiency ...
[33]
Leonid Vital'evich Kantorovich (1912 - 1986) - Biography - MacTutor
In 1938-1939, L V Kantorovich, a Leningrad mathematician, worked in consultation with a research laboratory of the plywood industry on the problem of ...<|control11|><|separator|>
[34]
Leonid Vitalievich Kantorovich - Econlib
The technique he developed is now known as linear programming. In The Mathematical Method of Production Planning and Organization (1939), Kantorovich showed ...Missing: cutting | Show results with:cutting
[35]
[PDF] Mathematical Methods of Organizing and Planning Production
The author of the work "Mathematical Methods of Organizing and Planning. Production", Professor L. V. Kantorovich, is an eminent authority in the field of ...
[36]
[PDF] Operations Research Time Line
1955 Hungarian Method for Transportation Problem, H. Kuhn, E. Egerváry. 1956 Trim (cutting stock) Problem, A. E. Paull. 1956 PERT/CPM/MPM, J. Kelley, Jr., W ...Missing: early 1950s
[37]
[PDF] On the history of combinatorial optimization (till 1960) - CWI
Only in the 1950's, when the unifying tool of linear and integer programming became available and the area of operations research got intensive attention, ...
[38]
L. V. Kantorovich and Cutting-Packing Problems: New Approaches ...
Zalgaller suggested to solve problems of economical use of material at the cutting stage with the help of linear programming. This led to the continuous ...
[39]
[PDF] arXiv:2401.17937v2 [math.OC] 2 Feb 2024
Feb 2, 2024 · The method has recently been found to date back to works by Kantorovich and Zalgaller in. 1951 [13,23], and was independently developed by ...<|control11|><|separator|>
[40]
[PDF] The 0-th Column Generation Algorithm - GERAD
May 19, 2023 · We do know that Kantorovich applied his technique to the problem of cutting metal for tanks, and to the problem of laying mine fields.” “As ...
[41]
C | SpringerLink
Paull, A.E. (1956), “Linear Programming: A Key to Optimum Newsprint Production,” Paper Magazine of Canada, 57, 85 - 90. Google Scholar. Pierce, J. F. (1964) ...
[42]
Knowledge based approach to the cutting stock problem
2. A.E. Paull. Linear programming: A key to optimum newsprint production. Pulp. Pap. Mag. Can., 57 (1956), ... cutting stock problem for cutting rolls.
[43]
Fifty years of operational research in forestry - Wiley Online Library
May 18, 2023 · Paull, A.E., 1956. Linear programming: a key to optimum newsprint production. Pulp and Paper Magazine of Canada 57, 145–150. Google Scholar.
[44]
[PDF] Programming the USSR: Leonid V. Kantorovich in context
In. 1938, engineers from the lab of the Plywood Trust asked him to solve a maximization problem regarding veneer-cutting machines of different productivities ...
[45]
A Linear Programming Approach to the Cutting Stock Problem—Part II
The paper describes a new and faster knapsack method, experiments, and formulation changes. The experiments include ones used to evaluate speed-up devices.
[46]
An Algorithm for Two-Dimensional Cutting Problems - PubsOnLine
Published Online:February 01, 1977. © 1977 INFORMS. Cite as. Nicos Christofides, Charles Whitlock, (1977) An Algorithm for Two-Dimensional Cutting Problems.
[47]
Genetic algorithms for cutting stock problems: With and without ...
This paper describes research involving cutting stock problems. Results show that the mapping that is used affects the solution in terms of both quality of the ...
[48]
(PDF) Cutting Stock Problems - ResearchGate
Column generation has been proposed by Gilmore and Gomory to solve cutting stock problem, independently of Dantzig-Wolfe decomposition.
[49]
The cutting stock problem with mixed objectives: Two heuristics ...
Cutting problems are NP-hard (see 5, 7, 8). Thus, only small size problems can be solved optimally. These problems are solved using either integer linear ...
[50]
Machine Learning–Supported Prediction of Dual Variables for the ...
Mar 29, 2023 · This article presents a prediction model of the optimal dual variables for the cutting stock problem.Missing: forecasting | Show results with:forecasting
[51]
A Linear Programming Approach to the Cutting-Stock Problem - jstor
generalization of the knapsack problem, it can be solved by dynamic pro- ... 3, 74-92 (1956). 7. R. E. GOMORY, "An Algorithm for Integer Solutions to ...
[52]
A Linear Programming Approach to the Cutting Stock Problem I
Aug 4, 2025 · In this paper, a technique is described for overcoming the difficulty in the linear programming formulation of the problem.
[53]
[PDF] A Note on the Integrality Gap of Cutting and Skiving Stock Instances
Formally, the gap is defined as the difference between the optimal values of the ILP and its LP relaxation. For both, the CSP and the SSP, this gap is known to ...
[54]
Column generation - JuMP-dev
The cutting stock problem is about cutting large rolls of paper into smaller pieces. We denote the set of possible sized pieces that a roll can be cut into ...Mathematical formulation · Column generation theory · Choosing new columns
[55]
[PDF] A faster variant of the Gilmore and Gomory technique for cutting ...
In 1961 Gilmore and Gomory porposed the delayed column generation technique for the resolution of cutting stock problems. Since then, it has been widely used, ...
[56]
[PDF] AIMMS Modeling Guide - Cutting Stock Problem
The cutting stock problem involves cutting long rolls (raws) into smaller portions (finals) to meet demand, using cutting patterns to determine how many finals ...
[57]
[PDF] Stabilization in Column Generation - UNIPI
However, pure proximal approaches may suffer from tailing-off effects; if early stopping is possible, better performances are to be expected, as observed ...
[58]
On the choice of explicit stabilizing terms in column generation
It is well-known that primal degeneracy may cause a “tail-off” effect in column generation. Moreover, instability in the behavior of dual variables are more ...
[59]
Branch-and-Price: Column Generation for Solving Huge Integer ...
We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of ...<|control11|><|separator|>
[60]
Branch-and-Price Algorithms for the One-Dimensional Cutting Stock ...
We compare two branch-and-price approaches for the cutting stock problem. Each algorithm is based on a different integer programming formulation of the col.Missing: method | Show results with:method
[61]
[PDF] 1 The One-Dimensional Cutting Stock Problem
If we drop the “integer-valued” requirement in (4), we get an LP relaxation of the original problem which we can solve to get a lower bound for the IP.
[62]
A Mixed-Integer Linear Programming Model for the Cutting Stock ...
Aug 7, 2025 · A mixed-integer linear programming (MILP) model is proposed for solving a one dimension cutting stock problem (1D-CSP) in the steel industry ...Missing: compact | Show results with:compact
[63]
None
Summary of each segment:
[64]
Bin packing problem - Wikipedia
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, ...
[65]
Fast pattern-based algorithms for cutting stock - ScienceDirect.com
We present pattern-based methods that overcome the main problems of conventional heuristics in cutting stock problems by representing the solution in a much ...
[66]
[PDF] APPROXIMATION ALGORITHMS FOR BIN PACKING: A SURVEY
It is shown in [CGJ87] that, so long as L is weakly divisible, First Fit Decreasing always produces optimal packings, and if L is strongly divisible, then First ...
[67]
Tight absolute bound for First Fit Decreasing bin-packing: FFD(L) 11 ...
First Fit Decreasing is a classical bin-packing algorithm: the items are ordered by non-increasing size, and then in this order the next item is always ...
[68]
An application of simulated annealing to the cutting stock problem
We solve a two-dimensional cutting stock problem by applying a general global optimization algorithm, the simulated annealing. Our algorithms applied to the ...
[69]
[PDF] Solving an one-dimensional cutting stock problem by simulated ...
Oct 4, 2012 · In this paper, two meta-heuristic algorithms, namely simulated annealing (SA) and tabu search (TS), are proposed and developed for this type of ...Missing: integration | Show results with:integration
[70]
Local Search Algorithms for the Two-Dimensional Cutting Stock ...
In this process, to generate a cutting pattern, it is required to place all the given products (rectangles) into the stock sheet (two-dimensional area) without ...Missing: geometric | Show results with:geometric<|control11|><|separator|>
[71]
[PDF] Heuristics for Two-Dimensional Knapsack and Cutting Stock ...
We also solve the Cutting. Stock problem with items of irregular shape, by combining this last heuristic with a column generation algorithm. The algorithms ...
[72]
Solving One-Dimensional Cutting Stock Problems with the Deep ...
Feb 17, 2023 · Previous research showed that the 1DCSP belongs to class of NP-hard problems [7], which are problems in which an exact solution cannot be ...
[73]
Cutting stock problems - IBM
Describes examples that involve cutting larger-sized objects such as sheets, rolls, or boards, into smaller ones to meet a demand. Cutting stock problems ...
[74]
Cutting Stock Problem with Multiple Master Rolls - Gurobi Optimization
This cutting stock problem with multiple master rolls is an example of combinatorial optimization problems that cannot be attacked with machine learning ...Missing: forecasting | Show results with:forecasting
[75]
Optimization Modeling in Python: PuLP, Gurobi, and CPLEX - Medium
Oct 10, 2018 · Here I've selected CPLEX and Gurobi, since they are among the leading commercial solvers, and PuLP, which is a powerful open-source modeling ...
[76]
Bin packing and cutting stock problems — Mathematical Optimization
This chapter deals with two classic problem: the bin packing problem and the cutting stock problem. Let us start with some definitions and examples.
[77]
Optimization with PuLP - COIN-OR Documentation
PuLP is an linear and mixed integer programming modeler written in Python. With PuLP, it is simple to create MILP optimisation problems and solve them.A Blending Problem · Installing PuLP at Home · A Transportation Problem · ReadmeMissing: cutting stock<|separator|>
[78]
OptaPlanner User Guide
OptaPlanner is a lightweight, embeddable constraint satisfaction engine which optimizes planning problems. It solves use cases such as: Employee shift rostering ...
[79]
SVGnest - Free and Open Source nesting for CNC machines, lasers ...
A completely free and open source application for automatic nesting. Comes with advanced features like part-in-part nesting and concave area detection.
[80]
Deepnest - open source nesting software
Deepnest packs your parts into a compact area to save material and time. It automatically merges common lines so the laser doesn't cut the same path twice.