Augmented Lagrangian-based hybrid subgradient method for one-dimensional cutting stock problem
Optimization Eruditorum, Volume 2, Issue 1, April 2025, Pages 70–85
BANU ICMEN ERDEM
Department of Industrial Engineering, Faculty of Engineering, Eskisehir Technical University, Eskisehir 26555, Turkey
REFAIL KASIMBEYLI
UNEC Mathematical Modeling and Optimization Research Center, Azerbaijan State University of Economics (UNEC), Istiqlaliyyat Str. 6, Baku, 1001, Azerbaijan
Abstract
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.
Cite this Article as
Banu Icmen Erdem and Refail Kasimbeyli, Augmented Lagrangian-based hybrid subgradient method for one-dimensional cutting stock problem, Optimization Eruditorum, 2(1), 70–85, 2025