The best known solutions of the circular open dimension problem (CODP)

Last update: 01-Nov-2012

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
length
of the strip
width
of the strip (fixed)
ratio
aspect ratio = length / width
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 length width ratio density contactsloose reference
SY1 30    17.039663    9.5    1.793649    0.853892056372 41 10 [9]
SY2 20    14.397059    8.5    1.693772    0.844619731312 27 7 [9]
SY3 25    14.326620    9.0    1.591847    0.853909681827 41 5 [10]
SY4 35    23.285708    11.0    2.116883    0.854915094732 59 6 [7]
SY5 100    35.722300    15.0    2.381487    0.875706296924 174 13 [10]
SY6 100    36.182710    19.0    1.904353    0.878442877222 151 25 [10]
SY12 50    29.583500    9.5    3.114053    0.859603050638 0 50 [9]
SY13 55    30.353400    9.5    3.195095    0.861182691569 89 11 [10]
SY14 65    37.554743    11.0    3.414068    0.864690792376 111 10 [7]
SY23 45    27.573166    9.0    3.063685    0.860188006756 61 15 [8]
SY24 55    34.010900    11.0    3.091900    0.861599067978 78 16 [10]
SY34 60    34.543629    11.0    3.140330    0.866053746510 83 18 [10]
SY56 200    63.915100    19.0    3.363953    0.883687288144 325 38 [10]
SY123 75    42.847130    9.5    4.510224    0.863997825463 119 16 [10]
SY124 85    48.441309    11.0    4.403755    0.864337500810 122 23 [9]
SY134 90    49.046868    11.0    4.458806    0.866162931849 130 25 [9]
SY234 80    45.344850    11.0    4.122259    0.866979108695 127 17 [10]
SY1234 110    59.620120    11.0    5.420011    0.870159058544 169 26 [10]
SY36 125    42.598440    19.0    2.242023    0.882249966609 196 27 [10]
SY125 150    40.234200    20.0    2.011710    0.883352220303 270 15 [10]
SY1236 175    54.135040    20.0    2.706752    0.882645194371 304 22 [10]
SY356 225    70.293370    19.0    3.699651    0.885984875770 376 36 [10]
SY1256 250    78.134710    19.0    4.112353    0.885610995364 429 35 [10]
SY12356 275    72.910410    22.0    3.314110    0.888318145506 502 22 [10]
SY565 300    69.452780    25.0    2.778111    0.888329381641 541 29 [10]
KBG1 25    33.323652    10.0    3.332365    0.836832107698 43 4 [9]
KBG2 25    21.940872    10.0    2.194087    0.789208970574 45 3 [9]
KBG3 25    27.281212    10.0    2.728121    0.843078646455 43 4 [9]
KBG4 25    13.275753    10.0    1.327575    0.845443006720 43 4 [9]
KBG5 25    6.493628    10.0    0.649363    0.832077667878 47 1 [9]
KBG6 25    25.192679    10.0    2.519268    0.836835709790 29 11 [9]
KBG7 25    4.990629    10.0    0.499063    0.847383147565 43 4 [9]
KBG8 25    3.705960    10.0    0.370596    0.838759826207 41 5 [9]
KBG9 25    36.164433    10.0    3.616443    0.822248306086 41 5 [9]
KBG10 25    20.694451    10.0    2.069445    0.803722211825 43 4 [9]
KBG11 25    26.733582    10.0    2.673358    0.837339828192 47 2 [9]
KBG12 25    11.083842    10.0    1.108384    0.846936436031 39 6 [9]
KBG13 25    6.006472    10.0    0.600647    0.831273702409 43 4 [9]
KBG14 25    21.495996    10.0    2.149600    0.829157166398 24 13 [9]
KBG15 25    9.170743    10.0    0.917074    0.852194630858 35 8 [9]
KBG16 25    3.638368    10.0    0.363837    0.837086682999 33 9 [9]
KBG17 25    44.502437    10.0    4.450244    0.773066093935 3 23 [9]
KBG18 25    20.143491    10.0    2.014349    0.800227285398 47 2 [9]
KBG19 25    23.615638    10.0    2.361564    0.818705757960 31 10 [9]
KBG20 25    12.977752    10.0    1.297775    0.831574826295 45 3 [9]
KBG21 25    5.029868    10.0    0.502987    0.816845334390 43 4 [9]
KBG22 25    31.603345    10.0    3.160334    0.814520507211 41 5 [9]
KBG23 25    8.520484    10.0    0.852048    0.834730644085 45 3 [9]
KBG24 25    2.255643    10.0    0.225564    0.798806822085 45 3 [9]
KBG25 25    28.870452    10.0    2.887045    0.794770739569 42 3 [10]
KBG26 25    26.578405    10.0    2.657840    0.754995294322 51 0 [9]
KBG27 25    12.945579    10.0    1.294558    0.784053577062 47 2 [9]
KBG28 25    13.041602    10.0    1.304160    0.794075053526 45 3 [9]
KBG29 25    5.195416    10.0    0.519542    0.789450151961 47 2 [9]
KBG30 25    4.338971    10.0    0.433897    0.792739937375 43 4 [9]
KBG31 25    18.965489    10.0    1.896549    0.792529804167 43 4 [9]
KBG32 25    1.421286    10.0    0.142129    0.781505096566 56 0 [9]
KBG33 50    72.840349    10.0    7.284035    0.823610488491 89 6 [9]
KBG34 50    40.833876    10.0    4.083388    0.814141696273 93 4 [10]
KBG35 50    53.231191    10.0    5.323119    0.850211173812 79 11 [10]
KBG36 50    25.881809    10.0    2.588181    0.858906742966 77 12 [10]
KBG37 50    12.573884    10.0    1.257388    0.850500991710 85 8 [9]
KBG38 50    52.416790    10.0    5.241679    0.851559356075 79 11 [10]
KBG39 50    19.484262    10.0    1.948426    0.868620819785 81 10 [10]
KBG40 50    8.349900    10.0    0.834990    0.865363265726 83 9 [10]
KBG41 50    74.859650    10.0    7.485965    0.817178662475 93 4 [9]
KBG42 50    41.545007    10.0    4.154501    0.809587145802 92 3 [9]
KBG43 50    47.772390    10.0    4.777239    0.849870998188 79 11 [10]
KBG44 50    30.179100    10.0    3.017910    0.854609104680 83 9 [10]
KBG45 50    11.654510    10.0    1.165451    0.847547829611 97 2 [10]
KBG46 50    39.178703    10.0    3.917870    0.854764179167 85 8 [10]
KBG47 50    22.227784    10.0    2.222778    0.855850381701 77 12 [10]
KBG48 50    8.291032    10.0    0.829103    0.860117667480 81 10 [9]
KBG49 50    62.730663    10.0    6.273066    0.827466785075 83 9 [9]
KBG50 50    39.393632    10.0    3.939363    0.821849215000 89 6 [9]
KBG51 50    47.483410    10.0    4.748341    0.843957216858 71 15 [10]
KBG52 50    24.208974    10.0    2.420897    0.845145225300 81 8 [9]
KBG53 50    12.250765    10.0    1.225076    0.847691115305 89 6 [9]
KBG54 50    48.007131    10.0    4.800713    0.844408674992 58 21 [9]
KBG55 50    12.193825    10.0    1.219383    0.855287375408 77 12 [9]
KBG56 50    7.821252    10.0    0.782125    0.853075087442 87 7 [9]
KBG57 50    99.631481    10.0    9.963148    0.778107500259 89 6 [9]
KBG58 50    44.075363    10.0    4.407536    0.791073395770 93 4 [9]
KBG59 50    40.246630    10.0    4.024663    0.843642150163 84 8 [9]
KBG60 50    25.560381    10.0    2.556038    0.843036935643 86 7 [9]
KBG61 50    10.305060    10.0    1.030506    0.836809864918 93 4 [10]
KBG62 50    55.721872    10.0    5.572187    0.792663403840 53 24 [9]
KBG63 50    22.274092    10.0    2.227409    0.845975826231 87 7 [10]
KBG64 50    10.736768    10.0    1.073677    0.843528119020 85 8 [9]
KBG65 75    96.048486    10.0    9.604849    0.838115891282 117 17 [9]
KBG66 75    61.686433    10.0    6.168643    0.815474394125 131 10 [9]
KBG67 75    74.396790    10.0    7.439679    0.854973134878 106 22 [10]
KBG68 75    38.937510    10.0    3.893751    0.861460179180 139 6 [10]
KBG69 75    17.341530    10.0    1.734153    0.856245846817 140 5 [10]
KBG70 75    66.331820    10.0    6.633182    0.861122316585 113 19 [10]
KBG71 75    33.337143    10.0    3.333714    0.868055266625 119 16 [10]
KBG72 75    12.760900    10.0    1.276090    0.870196733874 129 11 [10]
KBG73 75    92.700487    10.0    9.270049    0.840326651363 129 11 [9]
KBG74 75    60.393365    10.0    6.039337    0.821474743309 135 7 [9]
KBG75 75    80.659970    10.0    8.065997    0.848025597849 113 19 [10]
KBG76 75    42.502300    10.0    4.250230    0.859099193216 137 7 [10]
KBG77 75    18.422180    10.0    1.842218    0.856652127043 131 10 [10]
KBG78 75    61.230730    10.0    6.123073    0.863919831506 94 28 [10]
KBG79 75    25.367582    10.0    2.536758    0.870929294448 110 20 [10]
KBG80 75    13.154030    10.0    1.315403    0.865801510058 120 15 [10]
KBG81 75    93.734637    10.0    9.373464    0.839683672520 117 17 [9]
KBG82 75    63.310296    10.0    6.331030    0.809760632203 137 6 [9]
KBG83 75    79.491410    10.0    7.949141    0.833177058608 90 30 [10]
KBG84 75    49.168482    10.0    4.916848    0.851405001770 133 9 [9]
KBG85 75    16.928140    10.0    1.692814    0.849538408144 141 5 [10]
KBG86 75    70.023340    10.0    7.002334    0.843816415677 81 35 [10]
KBG87 75    31.355060    10.0    3.135506    0.866618798657 112 19 [10]
KBG88 75    11.090300    10.0    1.109030    0.859108177672 123 14 [10]
KBG89 75    96.432903    10.0    9.643290    0.833202856367 117 17 [9]
KBG90 75    54.174851    10.0    5.417485    0.839169938458 134 7 [9]
KBG91 75    83.418750    10.0    8.341875    0.828642500163 115 18 [10]
KBG92 75    45.587587    10.0    4.558759    0.841488635734 139 6 [9]
KBG93 75    18.382540    10.0    1.838254    0.844004369936 128 11 [10]
KBG94 75    105.241974    10.0    10.524197    0.815794223828 136 7 [9]
KBG95 75    41.789987    10.0    4.178999    0.844727615712 104 23 [10]
KBG96 75    9.541484    10.0    0.954148    0.856004484997 123 14 [10]
KBG97 100    136.334680    10.0    13.633468    0.830733123546 171 15 [10]
KBG98 100    80.398310    10.0    8.039831    0.823263831067 180 10 [10]
KBG99 100    109.530880    10.0    10.953088    0.853247173360 149 26 [10]
KBG100 100    53.541130    10.0    5.354113    0.864067422834 159 21 [10]
KBG101 100    24.609510    10.0    2.460951    0.857000397547 179 11 [10]
KBG102 100    96.311020    10.0    9.631102    0.862646496759 131 34 [10]
KBG103 100    41.667050    10.0    4.166705    0.873768652378 172 14 [10]
KBG104 100    17.722912    10.0    1.772291    0.875978230169 177 12 [10]
KBG105 100    143.457324    10.0    14.345732    0.821699378985 176 10 [9]
KBG106 100    79.786590    10.0    7.978659    0.824330289747 173 12 [10]
KBG107 100    103.475091    10.0    10.347509    0.854108966505 166 17 [10]
KBG108 100    51.930270    10.0    5.193027    0.861562577373 170 15 [10]
KBG109 100    24.630520    10.0    2.463052    0.854169680564 188 6 [10]
KBG110 100    81.765690    10.0    8.176569    0.865428548677 101 50 [10]
KBG111 100    36.668656    10.0    3.666866    0.874405434917 159 21 [10]
KBG112 100    18.293880    10.0    1.829388    0.872045741064 176 12 [10]
KBG113 100    158.244480    10.0    15.824448    0.800848825672 167 16 [10]
KBG114 100    83.930680    10.0    8.393068    0.817315764790 180 10 [10]
KBG115 100    79.858010    10.0    7.985801    0.851632718967 159 21 [10]
KBG116 100    46.510580    10.0    4.651058    0.858440920502 179 11 [10]
KBG117 100    25.238600    10.0    2.523860    0.856896701432 178 11 [10]
KBG118 100    99.987614    10.0    9.998761    0.849542974788 125 38 [10]
KBG119 100    44.024270    10.0    4.402427    0.858501850011 177 12 [10]
KBG120 100    16.368840    10.0    1.636884    0.866612083205 166 17 [10]
KBG121 100    105.173481    10.0    10.517348    0.832277493964 178 11 [9]
KBG122 100    75.374766    10.0    7.537477    0.825973191416 176 12 [9]
KBG123 100    96.619210    10.0    9.661921    0.844481527202 155 23 [10]
KBG124 100    55.715600    10.0    5.571560    0.849038135545 165 18 [10]
KBG125 100    25.155100    10.0    2.515510    0.855837606458 182 8 [10]
KBG126 100    57.076750    10.0    5.707675    0.870242512761 119 41 [10]
KBG127 100    60.550340    10.0    6.055034    0.850051463797 146 26 [10]
KBG128 100    21.255770    10.0    2.125577    0.858681102578 176 12 [10]



Updates

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

29-May-2012: First presentation of the instances SY1, SY2, SY3, SY4, SY5, SY6, SY14 and SY23.
These are some of the famous benchmark instances by Stoyan and Yaskov, see [1] and [4]. Please note that the numbering of the circles doesn't correspond with the original numbering; the circles are numbered here always in ascending order by size.
Thanks to Hakim Akeb who supports this work. The data from [6] can be found here.
30-May-2012: Zhanghua Fu sent me twelve new records for the remaining instances SY1, SY3, SY12, SY13, SY24, SY34, SY56, SY123, SY124, SY134, SY234 and SY1234 [9].
30-May-2012: There are lots of other challenging instances, KBG1–KBG128, with varying aspect ratios by Kubach/Bortfeldt/Gehring [6] for which their solutions are shown here.
04-Jun-2012: Since all original record packings consist only of rattlers it is clear that they may be compressed. I have done this for the SY instances without changing the arrangement significantly. So the credits should remain to the authors. A comparison of the previous/compressed packings can be viewed here.
21-Aug-2012: Yu. Stoyan and G. Yaskov wrote an article [10] in which nearly all previous record packings were beaten. Packomania now shows these new records. Additionally, they created seven new benchmark instances named SY36, SY125, SY1236, SY356, SY1256, SY12356 and SY565 with more circles in the range N = 125–300.
25-Sep-2012: One improvement for SY12 and a belated record for KBG110 by Yu. Stoyan and G. Yaskov [10].
25-Sep-2012: 72(!) new improvements for KBG1–24, KBG26–33, KBG37, KBG40–42, KBG44–45, KBG48–50, KBG52–62, KBG64–66, KBG72–74, KBG76, KBG81–82, KBG84–85, KBG88–90, KBG92, KBG94, KBG100, KBG105 and KBG121–122 by Zhanghua Fu et al. [9].
27-Sep-2012: Further improvements for SY1, SY2, SY124 and SY134 by Zhanghua Fu et al. [9].
01-Nov-2012: Nine more records for KBG40, KBG44, KBG45, KBG61, KBG72, KBG76, KBG85, KBG88 and KBG100 by Yu. Stoyan and G. Yaskov [10].

References

[1]   Yu. G. Stoyan, G. N. Yaskov, Mathematical Model and Solution Method of Optimization Problem of Placement of Rectangles and Circles Taking into Account Special Constraints, Int. Trans. Opl Res. 5 (1998) 1, 45–57.
[2]   Mhand Hifi, Rym M'Hallah, A best-local position procedure-based heuristic for the two-dimensional layout problems, Studia Informatica Universalis 2 (2003) 1, 33–56.
[3]   Mhand Hifi, Rym M'Hallah, Approximate algorithms for constrained circular cutting problems, Computers & Operational Research 31 (2004) 5, 675–694.
[4]   Yu. G. Stoyan, G. Yas'kov, A mathematical model and a solution method for the problem of placing various-sized circles into a strip, European Journal of Operational Research 156 (2004) 3, 590–600.
[5]   WQ Huang, Y Li, H Akeb, CM Li, Greedy algorithms for packing unequal circles into a rectangular container, Journal of the Operational Research Society 56 (2005) 5, 539–548.
[6]   , Parallel greedy algorithms for packing unequal circles into a strip or a rectangle, Central European Journal of Operational Research 17 (2009) 4, 461–477.
[7]   , An Adaptive Look-Ahead Strategy-Based Algorithm for the Circular Open Dimension Problem, ADAPTIVE 2010: The Second International Conference on Adaptive and Self-Adaptive Systems and Applications (2010) 158–163.
[8]   , An augmented beam search-based algorithm for the circular open dimension problem, Computers & Industrial Engineering 61 (2011) 2, 373–381.
[9]   , Iterated tabu search for the circular open dimension problem, European Journal of Operational Research (to appear).
[10]   , Packing unequal circles into a strip of minimal length with a jump algorithm, Central European Journal of Operations Research (to appear) and private communication 2012.
Datenschutzerklärung der Otto-von-Guericke-Universität Magdeburg nach DSGVO

©  E. Specht    21-Jun-2018