The best known solutions of benchmark instances for the unequal circle packing problem

Last update: 02-Jun-2024

Download    Results    History of updates    References

Download

You may download ASCII files which contain all the values of length, width etc. by using the links given in the table header below.
All coordinates of all packings are packed as ASCII files here.
All packings are stored as nice PDF files here.

Results

The table below summarizes the current status of the search.
Please use the links in the following table to view a picture for a certain configuration.

Legend:
instance
the abbreviation for instance's name
N
the number of circles
radius
radius of the largest circle within a container circle of radius 1
ratio
radius of the container circle when all objects have their original size
density
ratio of total area occupied by the circles to container area
contacts
number of contacts between circles and container and between the circles themselves, respectively
loose
number of circles that have still degrees of freedom for a movement inside the container (so called "rattlers")
reference
for the best known packing so far

     
instance N radius ratio density contactsloose reference
NR10_1 10    0.500575276658282831123691166791    99.8850768935047619002583302144    0.812867271059319189223953397538 12 4 [7]
NR11_1 11    0.411794035572689716841714424571    60.7099613893922222609114593032    0.818517644238273158121494827184 14 4 [7]
NR12_1 12    0.338334415974407580819413951441    65.0244224686386391054964917463    0.806494429094328948130880866893 16 4 [12]
NR14_1 14    0.352240540258337900635664113302    113.5587629142956332906421157001    0.822063808958719110540649931624 24 2 [9]
NR15_1 15    0.385491273513703240348852371757    38.9113866658431320267249116672    0.833830873193160716724800779939 24 3 [12]
NR15_2 15    0.386219726423057712445676696713    38.8379955082079014895321489365    0.822068620342639618860726645082 14 8 [7]
NR16_1 16    0.439392496786422260765863671931    143.3797810858448261036194214461    0.846006501967883203514548890837 30 1 [12]
NR16_2 16    0.281915529056846455414097648556    127.6978253749931996947327500171    0.817821613132781053812063860071 28 2 [13]
NR17_1 17    0.508261211299433517777398103754    49.1873065349298744228796667392    0.836987446873478394820256716690 22 6 [12]
NR18_1 18    0.360437883078841795412133991207    196.9826240058943422947081409954    0.841087323791813818759802447070 24 6 [13]
NR20_1 20    0.335683774638203635767197094004    125.1177541877534848567011048301    0.845765770063982014147188268277 26 7 [12]
NR20_2 20    0.361281416100700528024441633366    121.7887166046088900694986270127    0.851171902349721008978630379968 34 3 [13]
NR21_1 21    0.303855341025243064201712233895    148.0967879260071432291079605994    0.845132381947994803699947626921 34 4 [13]
NR23_1 23    0.292527568748034604029932763446    174.3425422030163853739583152280    0.853058901017541997869122408637 38 4 [13]
NR24_1 24    0.595242191116413139162951392165    137.7590520695516966479128683812    0.870133099771376594859478981072 36 6 [13]
NR25_1 25    0.291438918281222276539500748430    188.7187899418706744813240516086    0.847765971829432056338166210978 36 7 [15]
NR26_1 26    0.228969292822898645070725489577    244.5742802870707925874252083093    0.846939112941585187630044419971 40 6 [13]
NR26_2 26    0.219807244156169759339932213528    300.2630793783483639639118216139    0.841645444587429250043991966739 42 5 [13]
NR27_1 27    0.285507624853394186628720635603    220.6596059644641049800553224121    0.854291121622762267520963516927 42 6 [15]
NR30_1 30    0.338641613892    2.9529743510    0.868814350806 48 6 [16]
NR30_2 30    0.307222248044    3.2549726016    0.868084600543 38 11 [16]
NR40_1 40    0.198733318337    5.0318688802    0.865180812501 72 4 [16]
NR50_1 50    0.228793127904    4.3707606481    0.875328296460 88 6 [16]
NR60_1 60    0.194515757325    5.1409716814    0.873755519822 92 14 [16]
IN9_1 9    0.414213562373095048801688724210    24.1421356237309504880168872421    0.833432589707730701745350122802 8 5 [5]
IN10_1 10    0.505891451471227574340407006391    98.8354317009915616475890587438    0.781828828235870642345434153500 10 5 [11]
IN10_2 10    0.500575276658282831123691166791    99.8850768935047619002583302144    0.812867271059319189223953397537 12 4 [5]
IN11_1 11    0.350973246552205528770261745742    56.9844003680351722966167046585    0.796065095427741803695129843311 18 2 [11]
IN11_2 11    0.411794035572689716841714424571    60.7099613893922222609114593032    0.818517644238273158121494827185 14 4 [8]
IN12_1 12    0.464101615137754587054892683012    215.4700538379251529018297561003    0.869378035329003335880913800170 6 9 [2]
IN14_1 14    0.352240540258337900635664113302    113.5587629142956332906421157001    0.822063808958719110540649931625 24 2 [8]
IN15_1 15    0.386219726423057712445676696713    38.8379955082079014895321489365    0.822068620342639618860726645080 14 8 [8]
IN16_1 16    0.281915529056846455414097648556    127.6978253749931996947327500173    0.817821613132781053812063860069 28 2 [31]
IN17_1 17    0.508261211299433517777398103754    49.1873065349298744228796667392    0.836987446873478394820256716689 22 6 [8]
IN17_2 17    0.414213562373095048801688724210    241.4213562373095048801688724208    0.888335909788949870512269339308 8 13 [1]
IN25_1 25    0.464101615137754587054892683012    21.5470053837925152901829756100    0.903765121881482226023004642884 6 22 [8]
IN28_1 28    0.464101615137754587054892683012    21.5470053837925152901829756100    0.917028109716011829248465377230 6 25 [8]
IN162_1 162    0.157871839056461018551944304456    11.4016534599071277840587116445    0.856207445309453576728887587033 290 17 [31]



Updates

Please note that the results are taken from a running search. For updates look at the list below.

28-Jul-2013: First presentation of all 24 NR instances and all 14 IN instances. Many thanks to Tao Ye who sent me the coordinates for the large NR instances.
These are the famous benchmark instances by Huang et al, see [4]. Please note that the numbering of the circles may not correspond with the original numbering; the circles are numbered here always in ascending order by size.
29-Jul-2013: The prior packing for the IN162-1 instance wasn't a record, now it is a best known [31].
30-Jul-2013: Tao Ye [13] provides the wonderful packings which could be improved by me by swapping of some objects [14].
22-Apr-2014: Zhizhong Zeng, Kun He, Xinguo Yu, Wenqi Huang and Zhanghua Fu obtained new candidates for optima for instances NR40_1, NR50_1 and NR60_1 [15].
17-Jul-2014: Four new candidates for NR25-1, NR27-1, NR30-1 and NR30-2 by Zhizhong Zeng, Kun He, Xinguo Yu, Wenqi Huang and Zhanghua Fu (their work is partly inspired by Tao Ye et al.) [15].
02-Jun-2024: Significant improvements for NR30-1, NR30-2, NR40-1, NR50-1, and NR60-1 by Jianrong Zhou, Jiyao He, and Kun He [16].

References

[1]   Wenqi Huang, Ruchu Xu, Two personification strategies for solving circles packing problem, Science in China (Series E) 42 (1999), 595–602.
[2]   Huaiqing Wang, Wenqi Huang, Quan Zhang, Dongmin Xu, An improved algorithm for the packing of unequal circles within a larger containing circle, European Journal of Operational Research 141 (2002), 440–453.
[3]   Wenqi Huang, Yan Kang, A Short Note on a Simple Search Heuristic for the Diskspacking Problem, Annals of Operations Research 131 (2004), 101–108.
[4]   Wen Qi Huang, Yu Li, Chu Min Li, Ru Chu Xu, New heuristics for packing unequal circles into a circular container, Computers & Operations Research 33 (2006) 2125–2142.
[5]   Mhand Hifi, Rym M'Hallah, A dynamic adaptive local search algorithm for the circular packing problem, European Journal of Operational Research 183 (2007) 1280–1294.
[6]   I. Castillo, F.J. Kampas, J.D. Printer, Solving circle packing problems by global optimization: numerical results and industrial applications, European Journal of Operational Research 191 (2008) 1, 786–802.
[7]   Hakim Akeb, Mhand Hifi, Rym M'Hallah, A beam search algorithm for the circular packing problem, Computers & Operations Research 36 (2009) 1, 1513–1528.
[8]   Jingfa Liu, Shengjun Xue, Zhaoxia Liu, Danhua Xu, An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle, Computers & Industrial Engineering 57 (2009) 1144–1149.
[9]   Hakim Akeb, Mhand Hifi, Rym M'Hallah, Adaptive beam search lookahead algorithms for the circular packing problem, Intl. Trans. in Op. Res. 17 (2010) 1, 553–575.
[10]   A. Grosso, A. R. M. J. U. Jamali, M. Locatelli, F. Schoen, Solving the problem of packing equal and unequal circles in a circular container, J. Glob. Optim. 47 (2010) 1, 63–81.
[11]   WenQi Huang, ZhangHua Fu, RuChu Xu, Tabu search algorithm combined with global pertubation for packing arbitrary sized circles into a circular container, Sci China Inf Sci, doi (2011).
[12]   Wenqi Huang, Zhizhong Zeng, Ruchu Xu, Zhanghua Fu, Using iterated local search for efficiently packing unequal disks in a larger circle, Advanced Materials Research 430–432 (2012) 1477–1481.
[13]   , Iterated Tabu Search Algorithm for Packing Unequal Circles in a Circle, (in press).
[14]   private collaboration between Tao Ye and Eckard Specht, July 2013.
[15]   Zhizhong Zeng, Kun He, Xinguo Yu, Wenqi Huang, Zhanghua Fu, private communication, April–July 2014.
[16]   , Solution-Hashing Search Based on Layout-Graph Transformation for Unequal Circle Packing, submitted to European Journal of Operational Research, under review, May 2024.
[31]   , program cci, 2005–2014.
Datenschutzerklärung der Otto-von-Guericke-Universität Magdeburg nach DSGVO

©  E. Specht    02-Jun-2024