Neural-Driven heuristic for strip packing trained with Black-Box optimization - Mariusz Kaleta; Tomasz Śliwiński (International Journal of Electronics and Telecommunications)
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-ofthe- 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