1. A framework to select heuristics for the rectangular two-dimensional strip packing problem.
- Author
-
Neuenfeldt Júnior, Alvaro, Siluk, Julio, Francescatto, Matheus, Stieler, Gabriel, and Disconzi, David
- Subjects
- *
HEURISTIC , *CUTTING stock problem , *BENCHMARK problems (Computer science) , *COMBINATORIAL optimization , *SUPERVISED learning - Abstract
• A framework to select improvement heuristics for the rectangular 2D-SPP; • Classification models fitted with supervised machine learning techniques; • 15,666 instances were used to represent the rectangular 2D-SPP characteristics; • The predictions can reduce the computational processing time to solve instances; • Framework is consistent and can be applied for other problems. Defining the algorithm capable of best fit the characteristics observed for a problem is a complex task in the context of combinatorial optimization problems. As a decision-making process, one of the most practical and useful ways to treat and solve algorithm selection problems is using supervised machine learning techniques to search for patterns between explanatory variables characteristics of the problem and the algorithms available to be selected. The present article deals with the development of a framework to fit classification models based on supervised machine learning techniques to select improvement heuristics for the rectangular 2D strip packing problem (2D-SPP) with 90-degrees rotation. Classification models were fitted to predict the best improvement heuristic for constructive heuristics bottom-left, bottom-left-fill, best-fit, best-fit with bottom-left-fill, fast-heuristic, and fast-heuristic with bottom-left-fill, using 19 features provided by problem characteristics. A total of 15,666 benchmark problem instances from the literature were used to represent the rectangular 2D-SPP characteristics variations found in real-world applications to train and test the fitted classification models. The framework proved to be consistent to predict improvement heuristics with acceptable accuracy, being able to be applied for the prediction of other cutting and packing problems algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF