Augmented Lagrangian-based hybrid subgradient method for one-dimensional cutting stock problem

This study proposes an enhanced version of the feasible value-based modified subgradient algorithm incorporating two novel placement heuristics for the one-dimensional cutting problem.These heuristics, the Sequential, Controlled, and Pre-Processed Placement heuristic and the Dynamic Placement heuristic are integrated within the algorithm to improve its performance.Additionally, the approach is further refined by combining it with simulated annealing in a hybrid framework.We evaluate the effectiveness of the proposed approach through computational experiments on benchmark problems.The results show that the feasible value-based modified subgradient algorithm, which integrates the Sequential, Controlled, and Pre-Processed Placement heuristic and the Dynamic Placement heuristic, successfully obtains solutions for all test problems.The algorithm achieves optimal solutions using the Dynamic Placement heuristic and outperforms the Sequential, Controlled, and Pre-Processed Placement heuristic in both solution quality and computational efficiency.While the Sequential, Controlled, and Pre-Processed Placement heuristic fails to reach optimal solutions, it enables reasonable runtimes.Conversely, the Dynamic Placement heuristic leads the algorithm to optimal solutions, though it requires longer computation times with the initial parameter settings.This study shows how adaptable and successful the hybrid method and placement heuristics are at handling complex optimization problems.It also shows how well they can solve the one-dimensional cutting problem.