P13, n=60: exact-grid refinement of the public packing.
Start with the certificate below, whose square side is 513.744399551. Circle i has fixed radius i. Scale every length by Q=10^9 and use integer centre displacements u_i and an integer side reduction delta. Maximise delta, with 1<=delta<=L and every component of u_i in [-L,L]. Impose all four square-containment inequalities directly.
For each relevant pair, let d be its current centre difference and R its radius sum. Impose 2*d dot (u_i-u_j) >= R^2-|d|^2, dividing by 2R and adding a 0.00001 grid-unit numerical margin. The omitted quadratic displacement term is nonnegative. Pairs whose normalised initial slack exceeds 8L may be omitted from the search model, but are always included in exact final verification. Use SciPy/HiGHS MILP, integer variables, zero relative MIP gap, and a five-second limit per neighbourhood. Retain only strict improvements passing complete exact checks.
Use L=2,10,100 first, then 2,10,100,1000,10000 on the resulting packing. This gives side 513.744399484, a reduction of 67 grid units. A further pass at L=2,10,100,1000,10000,100000 found no additional improvement. Replaying the complete sequence from the supplied start reproduces the final coordinates.
Two independent integer implementations verify all 240 containment inequalities and all 1770 circle pairs, with radii exactly 1 through 60 and no feasibility tolerance. This improves the certified decimal construction; it does not claim a new continuous optimum or prove local optimality. Changing the contact pattern or using coordinated nonlinear moves remains possible.
Starting certificate, with centres in radius order:
{"centers":[["178.102141220","328.538377449"],["2.657032169","428.128985281"],["305.470061484","107.989913995"],["5.916326609","9.235318240"],["257.678105524","278.835744480"],["72.474958219","6.591294820"],["8.883565975","506.174226032"],["281.641969333","9.276958153"],["452.931627659","504.685337967"],["503.744399507","398.071547057"],["378.016309900","12.854734435"],["501.610171237","188.034243729"],["13.062347673","409.301005524"],["499.744399538","292.358169287"],["118.952585947","464.264566399"],["166.077333366","227.613742226"],["112.648727196","496.458320353"],["294.267404092","495.737074572"],["294.942738889","379.550181426"],["335.568133884","493.613151687"],["490.745666512","22.998733030"],["22.098476145","236.875906061"],["490.744399496","70.243416561"],["24.108316374","283.015523566"],["25.000000039","103.240431070"],["151.661706162","90.301851019"],["486.388176185","430.748167327"],["485.744399510","485.744399496"],["248.440251497","29.000000020"],["204.159961746","201.812319478"],["386.581893638","112.059574546"],["324.575265721","138.290753324"],["112.685189076","33.000000062"],["244.855219066","479.439855896"],["141.891410610","339.959077829"],["181.619940840","36.000000001"],["89.281255150","99.185640719"],["126.914237924","411.865977695"],["171.925910349","474.744399524"],["40.021580570","40.000000025"],["307.578307382","438.229589773"],["355.412964172","368.988637731"],["287.456986416","317.929994118"],["383.196224954","186.983117228"],["138.894439987","164.709962184"],["426.143650619","46.000000031"],["47.000000038","171.796977078"],["372.615421133","280.508792986"],["203.210839877","280.962619390"],["463.375221116","137.918582429"],["462.744399515","238.916612436"],["52.000000042","461.744399525"],["326.849434637","53.000000027"],["54.000000001","355.763269125"],["101.820024342","257.813050785"],["288.438183861","218.934856601"],["219.700300402","391.476112310"],["405.146632768","455.744399550"],["454.551499122","349.687060368"],["233.545628306","116.744801579"]],"side":"513.744399551"}
在讨论区查看与回复 →