Neural-Driven heuristic for strip packing trained with Black-Box optimization

• Autorzy: Kaleta Mariusz , Śliwiński Tomasz

Identyfikatory

DOI

10.24425/ijet.2025.153584

• Języki publikacji: EN

Abstrakty

EN

We address the well-known NP-hard problem of packing rectangular items into a strip, a problem of significant importance in electronics (e.g., packing components on printed circuit boards and macro-cell placement in Very-Large-Scale Integration design) and telecommunications (e.g., allocating data packets over transmission channels). Traditional heuristics and metaheuristics struggle with generalization, efficiency, and adaptability, as they rely on predefined rules or require extensive computational effort for each new problem instance. In this paper, we propose a neural-driven constructive heuristic that leverages a lightware neural network trained via black-box optimization to dynamically evaluate item placement decisions. Instead of relying on static heuristic rules, our approach adapts to the characteristics of each problem instance, enabling more efficient and effective packing strategies. To train the neural network, we employ the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), a state-of-the-art derivative-free optimization method. Our method learns decision policies by optimizing fill factor improvements over a large dataset of problem instances. Unlike conventional heuristics, our approach dynamically adapts placement decisions based on a broad set of features describing the current partial solution and remaining items. Through extensive computational experiments, we compare our method against well-known strip packing heuristics, including MaxRects and Skyline-based algorithms. The results demonstrate that our approach consistently outperforms the best traditional heuristics, achieving up to 6.74 percentage points of improvement in packing efficiency. Furthermore, our method improves 87.87% of tested instances. Our study highlights the potential of machine learning-driven heuristics in combinatorial optimization and opens avenues for further research into adaptive decision-making strategies in packing and scheduling problems.

Słowa kluczowe

EN

strip packing problem; algorithm selection problem; heuristics; neural networks; reinforcement learning

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2025
• Tom: Vol. 71, No. 2
• Strony: 387--396
• Opis fizyczny: Bibliogr. 30 poz., rys., tab.

Twórcy

autor

Kaleta Mariusz

• Warsaw University of Technology, Warsaw, Poland

• https://orcid.org/0000-0002-2225-8956

autor

Śliwiński Tomasz

• Warsaw University of Technology, Warsaw, Poland

Bibliografia

• [1] A. Lodi, S. Martello, and M. Monaci, “Two-dimensional packing problems: A survey,” European Journal of Operational Research, vol. 141, no. 2, pp. 241-252, 2002. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0377221702001236
• [2] X. Zhao, Y. Rao, and J. Fang, “A reinforcement learning algorithm for the 2d-rectangular strip packing problem,” Journal of Physics: Conference Series, vol. 2181, no. 1, p. 012002, jan 2022. [Online]. Available: https://dx.doi.org/10.1088/1742-6596/2181/1/012002
• [3] J. Oliveira, A. Neuenfeldt Júnior, E. Silva, and M. Carravilla, “A survey on heuristics for the two-dimensional rectangular strip packing problem,” Pesquisa Operacional, vol. 36, pp. 197-226, 08 2016.
• [4] E. K. Burke, G. Kendall, and G. Whitwell, “A new placement heuristic for the orthogonal stock-cutting problem,” Operations Research, vol. 52, no. 4, pp. 655-671, 2004. [Online]. Available: http://www.jstor.org/stable/30036614
• [5] J. Jylänki, “A thousand ways to pack the bin-a practical approach to two-dimensional rectangle bin packing,” retrived from http://clb. demon. fi/files/RectangleBinPack. pdf, 2010.
• [6] J. L. da Silveira, F. K. Miyazawa, and E. C. Xavier, “Heuristics for the strip packing problem with unloading constraints,” Computers& Operations Research, vol. 40, no. 4, pp. 991-1003, 2013. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0305054812002353
• [7] L. Wei, A. Lim, and W. Zhu, “A skyline-based heuristic for the 2d rectangular strip packing problem,” in Modern Approaches in Applied Intelligence, K. G. Mehrotra, C. K. Mohan, J. C. Oh, P. K. Varshney, and M. Ali, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 286-295.
• [8] S. Martello, D. Pisinger, and D. Vigo, “The three-dimensional bin packing problem,” Operations Research, vol. 48, no. 2, pp. 256-267, 2000. [Online]. Available: http://www.jstor.org/stable/223143
• [9] T. G. Crainic, G. Perboli, and R. Tadei, “Extreme point-based heuristics for three-dimensional bin packing,” INFORMS Journal on Computing, vol. 20, no. 3, pp. 368-384, 2008. [Online]. Available: https://doi.org/10.1287/ijoc.1070.0250
• [10] A. Neuenfeldt Júnior, E. Silva, M. Francescatto, C. B. Rosa, and J. Siluk, “The rectangular two-dimensional strip packing problem real-life practical constraints: A bibliometric overview,” Computers & Operations Research, vol. 137, p. 105521, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0305054821002616
• [11] J. R. Rice, “The algorithm selection problem,” ser. Advances in Computers, M. Rubinoff and M. C. Yovits, Eds. Elsevier, 1976,vol. 15, pp. 65-118. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0065245808605203
• [12] J. Huang, “Optimal linear combination of heuristic strategies for 2d rectangular bin packing algorithms,” in 2024 IEEE 2nd International Conference on Image Processing and Computer Applications (ICIPCA), 2024, pp. 1867-1876.
• [13] R. Rakotonirainy, “A machine learning approach for automated strip packing algorithm selection,” ORiON, vol. 36, pp. 73-, 02 2021.
• [14] M. Beyaz, T. Dokeroglu, and A. Cosar, “Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2d bin packing problems,” Applied Soft Computing, vol. 36, pp. 236-245, 2015.
• [15] Progress in Polish Artificial Intelligence Research 5, 1st ed. PL: Warsaw University of Technology, 2024. [Online]. Available: https://doi.org/10.17388/WUT.2024.0002.MiNI
• [16] J. Fan, “A review for deep reinforcement learning in atari: Benchmarks, challenges and solutions,” EasyChair Preprint 6985, EasyChair, 2023.
• [17] J. Fang, Y. Rao, and M. Shi, “A deep reinforcement learning algorithm for the rectangular strip packing problem,” PLOS ONE, vol. 18, no. 3, pp. 1-20, 03 2023. [Online]. Available: https: //doi.org/10.1371/journal.pone.0282598
• [18] Y. Xu and Z. Yang, “Graphpack: A reinforcement learning algorithm for strip packing problem using graph neural network,” Journal of Circuits, Systems and Computers, vol. 33, no. 08, p. 2450139, 2024. [Online]. Available: https://doi.org/10.1142/S0218126624501391
• [19] K. Zhu, N. Ji, and X. D. Li, “Hybrid heuristic algorithm based on improved rules & reinforcement learning for 2d strip packing problem,” IEEE Access, vol. 8, pp. 226 784-226 796, 2020.
• [20] A. Neuenfeldt Júnior, J. Siluk, M. Francescatto, G. Stieler, and D. Disconzi, “A framework to select heuristics for the rectangular two-dimensional strip packing problem,” Expert Systems with Applications, vol. 213, p. 119202, 2023. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0957417422022205
• [21] Chazelle, “The bottomn-left bin-packing heuristic: An efficient implementation,” IEEE Transactions on Computers, vol. C-32, no. 8, pp. 697-707, 1983.
• [22] E. den Boef, J. Korst, S. Martello, D. Pisinger, and D. Vigo, “Erratum to ”the three-dimensional bin packing problem”: Robot-packable and orthogonal variants of packing problems,” Oper. Res., vol. 53, no. 4, p. 735-736, Jul. 2005. [Online]. Available: https://doi.org/10.1287/opre.1050.0210
• [23] J. Arabas and D. Jagodziński, “Toward a matrix-free covariance matrix adaptation evolution strategy,” IEEE Transactions on Evolutionary Computation, vol. 24, no. 1, pp. 84-98, 2020.
• [24] P. Carvalho, N. Lourenc¸o, and P. Machado, “How to improve neural network training using evolutionary algorithms,” SN Computer Science, vol. 5, no. 6, p. 664, Jun 2024. [Online]. Available: https://doi.org/10.1007/s42979-024-02972-5
• [25] D. Jagodziński, Ł. Neumann, and P. Zawistowski, “Deep neuroevolution: Training neural networks using a matrix-free evolution strategy,” in Neural Information Processing, T. Mantoro, M. Lee, M. A. Ayu, K. W. Wong, and A. N. Hidayanto, Eds. Cham: Springer International Publishing, 2021, pp. 524-536.
• [26] N. Hansen and A. Ostermeier, “Completely derandomized self-adaptation in evolution strategies,” Evolutionary Computation, vol. 9, no. 2, pp. 159-195, 2001.
• [27] M. Hüttenrauch and G. Neumann, “Robust black-box optimization for stochastic search and episodic reinforcement learning,” Journal of Machine Learning Research, vol. 25, no. 153, pp. 1-44, 2024. [Online]. Available: http://jmlr.org/papers/v25/22-0564.html
• [28] E. Silva, J. F. Oliveira, and G. W¨ascher, “2dcpackgen: A problem generator for two-dimensional rectangular cutting and packing problems,” European Journal of Operational Research, vol. 237, no. 3, pp. 846-856, 2014. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0377221714002112
• [29] G. Wäscher, H. Haußner, and H. Schumann, “An improved typology of cutting and packing problems,” European Journal of Operational Research, vol. 183, no. 3, pp. 1109-1130, 2007. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S037722170600292X
• [30] R. Ros and N. Hansen, “A simple modification in cma-es achieving linear time and space complexity,” in Parallel Problem Solving from Nature - PPSN X, G. Rudolph, T. Jansen, N. Beume, S. Lucas, and C. Poloni, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 296-305.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).