A Multi-label Transformation Framework for the Rectangular 2D Strip-Packing Problem

• Autorzy: Alvaro Neuenfeldt Júnior , Matheus Francescatto , Gabriel Stieler , David Disconzi
• Języki publikacji: EN

Abstrakty

EN

The present paper describes a methodological framework developed to select a multi-label dataset transformation method in the context of supervised machine learning techniques. We explore the rectangular 2D strip-packing problem (2D-SPP), widely applied in industrial processes to cut sheet metals and paper rolls, where high-quality solutions can be found for more than one improvement heuristic, generating instances with multi-label behavior. To obtain single-label datasets, a total of five multi-label transformation methods are explored. 1000 instances were generated to represent different 2D-SPP variations found in real-world applications, labels for each instance represented by improvement heuristics were calculated, along with 19 predictors provided by problem characteristics. Finally, classification models were fitted to verify the accuracy of each multi-label transformation method. For the 2D-SPP, the single-label obtained using the exclusion method fit more accurate classification models compared to the other four multi-label transformation methods adopted. (original abstract)

Słowa kluczowe

EN

Machine learning; Industry; Databases

PL

Uczenie maszynowe; Przemysł; Bazy danych

• Czasopismo: Management and Production Engineering Review
• Rocznik: 2021
• Tom: 12
• Numer: nr 4
• Strony: 27--37

Twórcy

autor

Alvaro Neuenfeldt Júnior

• Federal University of Santa Maria, Brazil

autor

Matheus Francescatto

• Federal University of Santa Maria, Brazil

autor

Gabriel Stieler

• Federal University of Santa Maria, Brazil

autor

David Disconzi

• Federal University of Santa Maria, Brazil

Bibliografia

• Alvarez-Valdés R., Parreno F. and Tamarit J.M. (2008). Reactive GRASP for the strip-packing problem, Computers & Operations Research, vol. 35, no. 4, pp. 1065-1083. DOI: 10.1016/j.cor.2006.07.004.
• Baker B.S., Coffman E.G. and Rivest R.L. (1980). Orthogonal packings in two dimensions, SIAM Jorunal on Computing, vol. 9, no. 4, pp. 846-855. DOI: 10.1137/0209064.
• Boutell M.R., Luo J., Shen X. and Brown C.M. (2004). Learning multi-label scene classification, Pattern Recognition, vol. 37, no. 9, pp. 1757-1771. DOI: 10.1016/j.patcog.2004.03.009.
• Brazdil P., Carrier C.G., Soares C. and Vilalta R. (2008). Metalearning: Applications to data mining. Springer Science & Business Media, Germany.
• Breiman L. (2001). Random forests, Machine Learning, vol. 45, no. 1, pp. 5-32. DOI: 10.1023/A:1010 933404324.
• Chen F.-C. (1990). Back-propagation neural networks for nonlinear self-tuning adaptive control, IEEE Control Systems Magazine, vol. 10, no. 3, pp. 44-48. DOI: 10.1109/37.55123.
• Chen, Tianqi, Tong He, Michael Benesty, Vadim Khotilovich, Yuan Tang, Hyunsu Cho, Kailong Chen (2019). xgboost: Extreme Gradient Boosting. https://CRAN.R-project.org/package=xgboost.
• Chun H. and Kele§ S. (2010). Sparse partial least squares regression for simultaneous dimension reduction and variable selection, Journal of the Royal Statistical Society, vol. 72, no. 1, pp. 3-25. DOI: 10.1111 j. 1467-9868.2009.00723.x.
• Dantas A. and Pozo A. (2018). Selecting Algorithms for the Quadratic Assignment Problem with a Multi-label Meta-Learning Approach. In 2018 7th Brazilian Conference on Intelligent Systems (BRACIS). pp. 175-180. DOI: 10.1109/BRACIS.2018.00038.
• Friedman J.H. (2002). Stochastic gradient boosting, Computational Statistics & Data Analysis, vol. 38, no. 4, pp. 367-378. DOI: 10.1016/S0167-9473(01) 00065-2.
• Glinka K., Wosiak A. and Zakrzewska D. (2016). Improving children diagnostics by efficient multi-label classification method. In Conference of Information Technologies in Biomedicine, pp. 253-266. DOI: 10.1007/ 978-3-319-39796-2_21.
• Glover F. (1986). Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, vol. 13, no. 5, pp. 533-549. DOI: 10.1016/0305-0548(86)90048-1.
• Hartmann S. (1998). A competitive genetic algorithm for resource-constrained project scheduling, Naval Research Logistics, vol. 45, no. 7, pp. 733-750. DOI: 10.1002/(SICI)1520-6750(199810)45:7<733::AID-NAV5>3.0.CO;2-C.
• Heberle H., Meirelles G.V., da Silva F.R., Telles, G.P. and Minghim R. (2015). InteractiVenn: a web-based tool for the analysis of sets through Venn diagrams, BMC bioinformatics, vol. 16, no. 1, p. 169. DOI: 10.1186/s12859-015-0611-3.
• Horvath M. and Vircikova E. (2012). Data mining model for quality control of primary aluminum production process, Management and Production Engineering Review, vol. 3, no. 1, pp. 47-53. DOI: 10.2478/ v10270-012-0033-x.
• Hopper E. and Turton B.C.H. (2001). An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research, vol. 128, no. 1, pp. 34-57. DOI: 10.1016/S0377-2217(99)00357-4.
• Kanda J., Carvalho A., Hruschka E. and Soares C. (2011). Selection of algorithms to solve traveling salesman problems using meta-learning, International Journal of Hybrid Intelligent Systems, vol. 8, no. 3, pp. 117-128. DOI: 10.3233/HIS-2011-0133.
• Kuhn M. (2008). Caret package, Journal of Statistical Software, vol. 28, no. 5, pp. 1-26. DOI: 10.18637/jss. v028.i05.
• Martello S., Monaci M. and Vigo D. (2003). An exact approach to the strip-packing problem, INFORMS Journal on Computing, vol. 15, no. 3, pp. 310-319. DOI: 10.1287/ijoc.15.3.310.16082.
• Ntene N. and Vuuren J.H. (2009). A survey and comparison of guillotine heuristics for the 2D oriented offline strip packing problem, Discrete Optimization, vol. 6, no. 2, pp. 174-188. DOI: 10.1016/j.disopt.2008.11.002.
• Neuenfeldt A.J., Silva E., Gomes A.M. and Oliveira J.F. (2017). The two-dimensional strip packing problem: What matters? In Congress of APDIO, the Portuguese Operational Research Society, pp. 151-164. DOI: 10.1007/978-3-319-71583-4_11.
• Neuenfeldt A.J., Silva E., Gomes A.M., Soares C. and Oliveira J.F (2019). Data mining based framework to assess solution quality for the rectangular 2D strip-packing problem, Expert Systems with Applications, vol. 118, no. 1, pp. 365-380. DOI: 10.1016/j.eswa.2018.10.006.
• Neuenfeldt A., Silva E., Francescatto M., Rosa C.B. and Siluk J. (2022). The rectangular two-dimensional strip packing problem real-life practical constraints: A bibliometric overview, Computers & Operations Research, vol. 157, no. 105521. DOI: 10.1016/j.cor. 2021.105521.
• Oliveira J.F., Neuenfeldt A.J., Silva E. and Carravilla M.A (2016). A survey on heuristics for the two-dimensional rectangular strip packing problem, Pesquisa Operacional, vol. 36, no. 2, pp. 197-226. DOI: 10.1590/0101-7438.2016.036.02.0197.
• Rogalewicz M. and Sika R. (2016). Methodologies of knowledge discovery from data and data mining methods in mechanical engineering, Management and Production Engineering Review, vol. 7, no. 4, pp. 97108. DOI: 10.1515/mper-2016-0040.
• Silva E., Oliveira J.F. and Wäscher G. (2014). 2DC- PackGen: A problem generator for two-dimensional rectangular cutting and packing problems, European Journal of Operational Research, vol. 237, no. 3, pp. 846-856. DOI: 10.1016/j.ejor.2014.02.059.
• Suykens J.A.K. and Vandewalle J. (1999). Least squares support vector machine classifiers, Neural Processing Letters, vol. 9, no. 3, pp. 293-300. DOI: 10.1023/ A:1018628609742.
• Tsoumakas G. and Katakis I. (2007). Multi-label classification: An overview, International Journal of Data Warehousing and Mining, vol. 3, no. 3, pp. 1-13. DOI: 10.4018/jdwm.2007070101.
• Wäscher G., Haußner H. and Schumann H. (2007). An improved typology of cutting and packing problems, European Journal of Operational Research, vol. 183, no. 3, pp. 1109-1130. DOI: 10.1016/ j.ejor.2005.12.047.

Identyfikatory

DOI

0.24425/mper.2021.139992