Perturbation-Based Thresholding Search for Packing Equal Circles and Spheres.

This article focuses on a perturbation-based thresholding search (PBTS) algorithm developed to address two NP-hard packing problems: packing N identical circles in a square (PECS) and packing N identical spheres in a cube (PESC). The algorithm transforms the constrained optimization problems into a series of unconstrained subproblems using a penalty function approach and employs a two-phase search strategy combining local optimization, adaptive perturbations (uniformly random and sequential random perturbations), and container size adjustment. Extensive computational experiments on benchmark instances demonstrate that PBTS outperforms state-of-the-art methods by improving 156 best-known results for PECS (2 ≤ N ≤ 400) and 66 for PESC (2 ≤ N ≤ 200), while matching many others. The study also analyzes the effectiveness of the hybrid perturbation strategy and the two-phase search design, highlighting their roles in enhancing solution quality and search efficiency.