  We address the NP-hard problem of finding a non-overlapping dense packing
pattern for n Unequal Circle items in a two-dimensional Square Container
(PUC-SC) such that the size of the container is minimized. Based on our
previous work on an Action Space based Global Optimization (ASGO) that
approximates each circle item as a square item to efficiently find the large
unoccupied spaces, we propose an optimization algorithm based on the
Partitioned Action Space and Partitioned Circle Items (PAS-PCI). The PAS is to
partition the narrow action space on the long side to find two equal action
spaces to fully utilize the unoccupied spaces. The PCI is to partition the
circle items into four groups based on size for the basin hopping strategy.
Experiments on two sets of benchmark instances show the effectiveness of the
proposed method. In comparison with our previous algorithm ASGO on the 68
tested instances that ASGO published, PAS-PCI not only gains smaller containers
in 64 instances and matches the other 4 but also runs faster in most instances.
In comparison with the best record of the Packomania website on a total of 98
instances, PAS-PCI finds smaller containers on 82 and matches the other 16.
Note that we updated 19 records for (47-48, 51-54, 57, 61-72) that had been
kept unchanged since 2013.
