Opticut: A new heuristic algorithm for the one-dimensional cutting stock problem with pattern minimisation

The one-dimensional cutting stock problem (1DCSP) is a well-known combinatorial optimization challenge encountered across various industrial sectors, including paper, steel, and plastic film production. The primary objective of 1DCSP is to efficiently cut larger stock materials into smaller pieces to meet specific demands while minimizing waste and production costs. In real-world applications, additional considerations such as setup costs—arising from transitions between cutting patterns—further complicate the problem. The variant addressed in this dissertation, known as the 1DCSP with pattern minimization, seeks to balance waste reduction with the minimization of the number of distinct cutting patterns, as fewer patterns typically reduce setup costs and improve operational efficiency. Classified as NP-hard, this problem exhibits exponential computational complexity as its size increases, necessitating heuristic approaches to achieve practical solutions within acceptable timeframes. This dissertation introduces OPTICUT, a novel heuristic algorithm designed to address the 1DCSP with pattern minimization. OPTICUT aims to outperform existing state-of-the-art methods by reducing both total costs and the number of cutting patterns, offering a robust and efficient solution for both academic research and industrial applications. The study builds on an extensive literature review, comprehensive computational experiments, and sensitivity analyses to validate the algorithm's effectiveness. The dissertation provides a thorough review of the 1DCSP literature, analyzing 169 publications from the Web of Science database spanning 1983 to 2025, with a total of 2,695 citations. The analysis reveals that material waste minimization is the most common research objective (42.28%), followed by cost optimization (12.08%). Pattern minimization, though less frequently studied, is critical in practical settings due to its impact on setup costs. Existing solution methods include heuristic approaches (e.g., Haessler's Sequential Heuristic Procedure, 1975), metaheuristics (e.g., genetic algorithms), and exact methods (e.g., integer linear programming, ILP). However, these approaches often struggle to simultaneously optimize waste and pattern usage, particularly in large-scale or complex scenarios, highlighting a gap that OPTICUT seeks to address. OPTICUT employs a three-stage hybrid methodology to tackle the 1DCSP with pattern minimization: Initial solution generation (using column generation approach): Drawing from Gilmore and Gomory (1963), this stage uses column generation to produce an initial feasible solution. While mostly effective at minimizing waste, it often generates a large number of patterns, necessitating further refinement. Alternative solutions generation (using pattern generation approach): Two distinct algorithms, Algorithm A and Algorithm B, create a pool of alternative cutting patterns. Algorithm A prioritizes items based on their length and residual value, iterating over 20 generations with varying priority coefficients. Algorithm B adjusts allowable waste incrementally across 50 iterations, ensuring diversity in pattern selection. These mechanisms enhance the exploration of the solution space. Final optimization (using integer linear programming approach): The pattern pool from the previous stages is optimized using ILP within a 45-second time limit, selecting the solution with the lowest total cost, which includes stock costs, setup costs, and waste-related expenses. The algorithm incorporates dynamic parameters—such as item value V(i), priority Pr(i), and allowable waste increase to generate high-quality cutting patterns tailored to challenging problem instances. pseudocode and flowcharts detail the implementation, ensuring transparency and reproducibility. OPTICUT's performance was rigorously evaluated using 1,840 benchmark instances from two datasets: CUTGEN1 (Gau & Wäscher, 1995) and Umetani (2003, 2018). Experiments were conducted on an Intel Core i7-1165G7 processor with 16 GB RAM, implemented in Python using the PULP-CBC-CMD solver, with an average computation time of 165 seconds per instance. CUTGEN1 results: Across 18 problem classes grouped by order variety and stock length ratios, OPTICUT reduced total costs by 0.0013% and pattern usage by 0.6% compared to state-of-the-art algorithms (e.g., CUI, MSHP, YL). It achieved dominance in 83% of classes for stock usage, 50% for pattern count, and 67% for total cost, outperforming competitors in overall efficiency. Umetani results: In 40 real-world fiber cutting instances, OPTICUT demonstrated superior performance, particularly with large stock lengths (e.g., 9080 mm). For stock cost = stock length and setup cost = 100, it achieved up to 0.51% cost reduction and 0.82% pattern reduction compared to MSHP and CUI, excelling in scenarios with diverse item sizes. An illustrative example, "Fiber29_9080," showed OPTICUT utilizing 35 stock rolls with 6 patterns and 550 mm waste, compared to CUI's 7 patterns for the same waste level, underscoring its pattern minimization capability. A sensitivity analysis on 150 CUTGEN1 instances assessed OPTICUT's robustness against parameter variations (Vi, Pri, and waste increase). Results indicated consistent stock usage across trials, with pattern count decreasing as parameter ranges widened, albeit with minimal impact. This stability enhances OPTICUT's reliability across diverse problem configurations, with computation time increasing by approximately 0.5 seconds per additional trial. OPTICUT offers several key contributions: Superior performance: It outperforms existing methods in diverse scenarios, including small and large item types relative to stock length, as evidenced by CUTGEN1 groups 1 and 3, and real-world fiber examples. Cost and pattern reduction: The algorithm achieves measurable reductions in total cost and pattern count, enhancing operational efficiency. Flexibility: Users can adjust stock and setup costs, as well as trial numbers, for tailored optimization. Innovative features: Dynamic variables and a hybrid approach enable high-quality pattern generation, surpassing documented solutions in the literature. Practical applicability: With reasonable computation times, OPTICUT is viable for real-world cutting operations. Future enhancements could include: Commercial solver integration: Incorporating solvers like Gurobi could reduce ILP computation time and improve solution quality. Parallel computing: Simultaneous execution of Algorithm A and B could cut processing time by up to 50%. Post-Pattern reduction: Additional algorithms could further minimize patterns without increasing waste. Multiple stock lengths: Extending OPTICUT to handle varied stock lengths would broaden its applicability. This dissertation demonstrates that OPTICUT is an effective and innovative solution for the 1DCSP with pattern minimization, validated by empirical results showing significant advantages over existing methodologies. OPTICUT represents a significant advancement in the field of 1DCSP, bridging theoretical insights with practical utility. By addressing both cost and pattern minimization, it offers a promising framework for future research and industrial adoption, contributing to resource efficiency and cost savings in cutting stock operations.