Cutting Smart: A CP Approach to the Two-Dimensional Two-Stage Cutting Stock Problem

Abstract: This blog presents a constraint programming (CP) approach to the Two-Dimensional Two-Stage Cutting Stock Problem with Flexible Length and Flexible Demand (2SCSP-FF), motivated by industrial cutting applications. The model minimizes material waste and the number of stock sheets used, accounting for flexible item lengths and stock sizes. It improves upon a recent CP formulation, highlighting the effectiveness of specialized optimization techniques in manufacturing settings.

Introduction

Cutting large sheets of material into smaller, usable items may seem simple—especially if material were unlimited. But in the real world, the challenge lies not in making cuts, but in minimizing material usage and waste. Raw materials like glass, metal, or wood come at a cost, and any unused portion after cutting directly impacts profitability. The cutting stock problem (CSP) addresses exactly this: how to meet demand using the least amount of stock material.

In this post, we explore a two-dimensional, two-stage version of this problem that uses guillotine cuts, where each cut must go fully across the sheet in one direction. Uniquely, this problem variant features flexible-length demand—a setting where items of a given width must be cut in required quantities, but their lengths can be chosen from an interval. This added flexibility introduces rich modeling opportunities but also increases the complexity of optimization. Our approach is inspired by the work addressed in [1] introduced by Luo and Beck, which proposes a constraint-based solution to this challenging problem.

Motivation

Modern manufacturing environments, particularly those involving metal processing, textiles, or packaging materials, demand cutting solutions that are not only precise but also highly adaptable to customer-specific requirements. Traditional cutting stock models often assume fixed item dimensions and rigid demand fulfillment, but real-world operations are rarely so straightforward. This motivated the development of the Two-Stage Cutting Stock Problem with Flexible Length and Flexible Demand (2SCSP-FF) - a complex and realistic generalization of the classical cutting stock problem. This problem reflects the practical challenges faced in industrial settings where:

1. Items can vary in length within customer-specified intervals,
2. Order fulfillment can tolerate controlled deviations from requested areas,
3. Stocks come in limited quantities with varied widths,
4. Each cutting machine can perform only a limited number of cuts per level.

The 2SCSP-FF is not just theoretically richer; it mirrors the needs of actual production lines where constraints are driven by downstream processes, machine capacities, and operational efficiency. For instance, items are often rolled into coils whose dimensions must meet mounting requirements — making length flexibility a crucial aspect of feasibility. Luo and Beck’s key contribution was modeling this complex setting using constraint programming (CP), applying scheduling techniques to manage item placement and level assignments efficiently. Their model marked a significant advancement in solving industrial-sized instances within reasonable memory and time limits.

Our work builds upon this foundation and goes a step further. By developing a new CP model that solves 2SCSP-FF instances more efficiently than the existing CP formulation, we demonstrate that it is possible to push the computational boundaries even further. Our approach maintains the flexibility and richness of the original problem while delivering faster solutions. This makes the 2SCSP-FF not only a fertile ground for optimization research but also a powerful example of how customized mathematical modeling can directly enhance industrial productivity. Efficient solutions reduce material waste, optimize stock usage, and streamline manufacturing processes — all while respecting complex, real-world constraints.

The Problem at a Glance

This problem focuses on cutting large rectangular sheets, or stocks, into smaller rectangles, or items, to satisfy specific customer orders. To ensure both practicality and alignment with industrial standards, the cutting process is restricted to guillotine cuts—straight cuts that extend from one edge of the sheet to the opposite edge, either horizontally or vertically. These are favored in real-world settings because they suit the capabilities of cutting machines and enhance operational efficiency. The problem adopts a two-stage guillotine cutting approach: first, horizontal cuts are made across the width of the stock to divide it into horizontal strips, or levels; then, within each level, vertical cuts are applied to extract the required rectangular items. What makes the problem especially interesting is that the length of the stock is flexible, allowing for optimization. The objective is to minimize the total unused material across all the stocks used.

Key Constraints in the Model

The problem incorporates several constraints to ensure the solution is both feasible and efficient.

Level Width Constraint

This constraint ensures that each level within a stock can accommodate the width of all items assigned to it without exceeding the stock’s total width. The constraint is only active for levels that have items allocated, ensuring that material usage is limited to what's needed for active levels and avoiding unnecessary use of stock width.

Stock Length Constraint

This constraint guarantees that the sum of lengths of all levels within a stock remains within the stock’s overall length. It’s applied only to stocks that are in use, making sure that material is efficiently allocated and that unused stock remains unaffected, thus optimizing space.

Stock Area Constraint

This constraint controls the total area of each order placed within a stock, ensuring that the area assigned meets each order’s area requirements range. It enforces efficient use of stock by balancing order needs with stock capacity, reducing waste while fully satisfying each order’s area specifications.

Level Length Constraint

The length of each level within a stock must be appropriately sized to fit the items allocated to it. This is achieved by enforcing a range bounds on the level's length. Each level in a stock must be at least as long as the largest or the minimum required length of each order. Similarly, each level in a stock must be at most as long as the smallest of the maximum required length of each order.

Optimization Goals

The cutting stock problem is primarily driven by two key optimization goals, each aimed at promoting efficiency, cost-effectiveness, and sustainability. The first and foremost goal is to minimize material waste. Specifically, the objective is to reduce the unused area within each stock sheet that is cut. Effective minimization of waste ensures that the maximum possible area of each sheet is utilized to produce order items. This leads directly to cost savings by lowering the amount of raw material needed and supports environmental sustainability by reducing industrial waste.

The second, closely related goal is to minimize the number of stock sheets used in fulfilling the demand. Efficient cutting patterns naturally result in fewer sheets being required. Reducing the number of sheets not only saves on material costs but also lessens associated handling, storage, and transportation expenses. Moreover, optimal sheet utilization contributes to a more streamlined production process and a smaller environmental footprint. Balancing these objectives is crucial because minimizing waste on individual sheets is important, but achieving it across the overall set of stock sheets ensures the most economical and sustainable operation.

Symmetry in CP Models and We Break It

In constraint programming, symmetry can cause a solver to waste time exploring multiple equivalent solutions. For example, if two items or levels are interchangeable in function, the solver might explore both orderings separately—even though they represent the same solution in practice.
    
To reduce this redundancy and speed up the search process, we can consider symmetry-breaking constraints. These constraints limit the solution space to one representative of each group of equivalent configurations, allowing the solver to converge faster on optimal solutions. In our cutting stock model, symmetry breaking is particularly useful when multiple levels or partitions have identical structural roles.

Mathematical Formulation

We now present the mathematical formulation of the problem using a Constraint Programming (CP) approach. This formulation introduces decision variables to describe how items are placed within each stock and how space is allocated while respecting the structure of the cutting process. It incorporates constraints to ensure feasible placement of items based on their dimensions and the overall configuration of the stocks. The CP model provides a flexible framework for expressing the spatial and logical conditions required by the problem. In the following, we define the decision variables and constraints that govern the solution space.

Let the set of stocks be K, with each rectangle k ∈ K has width W_k, H be the set characterized by the dimensions of each stock, and K_h be the stocks having similar dimension h ∈ H. The set of orders be N, in which for each i∈N is a collection of items having width w_i and has area falling in the interval [q_i^min, q_i^max]. Thus, the length of each item i ∈ N falls in the interval [l_i^min, l_i^max]. Since all stocks have the same length, a stock can take at most 

cuts, and we denote the set of possible numbers of levels on any stock by 

Also, the maximum partition allowed to any level is P = {0, 1, ..., η} where

The main decision variables set to the model are the following:

• x_ijk : (integer) defines the number of partitions on level of stock assigned to order .
  
• y_jk^int : (integer) length of level of stock  magnified by a large number.
• y_jk : (float) length of level of stock .

The objective is to minimize the waste and the constraints ensure the basic requirements of the problem demand which is given follows:

We also incorporate a symmetry-breaking constraint to eliminate redundant configurations that arise due to interchangeable levels within the same stock. This improves computational efficiency by guiding the solver to consider only distinct arrangements.

Analysis of Comparative Results

The figure demonstrates how symmetry-breaking constraints enhance both solver efficiency and solution clarity in cutting stock problems. Without these constraints, the solver explores numerous equivalent solutions that differ only in superficial ways—such as the order of levels or the assignment of identical items to interchangeable stock positions. This leads to unnecessary branching and disorganized outputs. By enforcing symmetry-breaking constraints—like lexicographic ordering on level configurations or item placements—we guide the solver to consider only one representative from each group of equivalent solutions. As seen in the figure, this yields cleaner, more structured layouts with consistent item arrangements across stocks. This leads to a smaller search space, quicker solution times, and more readable output layouts.

To assess the effectiveness of our proposed model, we conducted a comparative analysis against the CP model addressed by Luo and Beck in [1], using randomly generated instances of varying sizes. Each instance was evaluated over 200 random seeds to ensure statistical robustness, with fixed time limits per run depending on instance size. For smaller instances (3 stocks and 4 orders), our model outperformed the CP baseline in 73.5% of the 200 runs, clearly demonstrating its advantage in simpler settings. For larger and more challenging instances (10 stocks and 15 orders), the results were more balanced. Our model produced better solutions in 52.5% of the cases, compared to 47.5% for the CP model, under a 200-second time limit. While this difference is modest, it still suggests a slight performance edge for the proposed model on complex instances. However, these results indicate that performance gains should be interpreted with tempered expectations, particularly for large-scale scenarios.

Importantly, the strength of our approach lies not only in runtime improvements but also in model formulation and solver efficiency. Our model departs from Luo and Beck’s approach by using floating-point decision variables in its initial formulation. This enables a simpler, more expressive model, avoiding the cluttered integer-only structure that relies on indexing tricks like scaling by a large number for pattern decomposition. This hybrid design contributes to better solver behavior and ease of implementation. Overall, while the quantitative edge of our model is moderate for large instances, its qualitative advantages—such as clarity, scalability, and maintainability—make it a strong candidate for real-world applications in two-stage cutting stock problems with flexible length and demand.

Implementation

The full implementation of the model, including the CP formulation and sample instances, is available on GitHub at this repository .

Conclusion

In this article, we explored the Two-Dimensional Two-Stage Cutting Stock Problem with Flexible Length and Flexible Demand (2SCSP-FF) through the lens of constraint programming. By extending and improving upon the CP-based model introduced by Luo and Beck, we demonstrated how complex industrial constraints can be effectively captured and optimized in a computational framework. We proposed improvements to the CP model’s constraint structure to guide the solver (IBM ILOG CP Optimizer) more effectively in constructing valid and efficient cutting patterns. Computational experiments on benchmark instances indicate that our enhanced model performs well in terms of both material utilization and solver efficiency. Notably, it achieves reductions in the number of rolls used and material waste, while also solving many instances in shorter runtimes compared to the original model. These results highlight the practical potential of constraint programming in solving complex cutting stock problems, especially when the problem involves multiple stages and added flexibility in requirements.

References

1. Yiqing L. Luo and J. Christopher Beck. Packing by Scheduling: Using Constraint Programming to Solve a Complex 2D Cutting Stock Problem, International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research,  Springer International Publishing, 2022.