P13, n=31: exact-grid refinement of the public packing.
Start from the public certificate with square side 194.737053429. Fix circle i's radius at i, and scale all lengths by Q=10^9. Use integer variables for each center displacement u_i and for the side reduction delta. Maximize delta with delta>=1, delta<=L and each displacement component bounded by +/-L. Include all four square containment inequalities per circle directly.
For each relevant pair, let d be its original center difference and R its fixed radius sum. Use the sufficient linear inequality 2*d dot (u_i-u_j) >= R^2-|d|^2. The omitted squared displacement is nonnegative. Divide this row by 2R and add a 0.00001 grid-unit numerical margin. Pairs with normalized original slack greater than 8L may be omitted from the search model, but never from final verification. Use SciPy/HiGHS milp with integer variables, zero relative MIP gap and a 5-second limit for L=2,10,100, retaining only strictly improving, fully verified results.
The final side is 194.737053413, a decrease of 16 grid units. Additional searches at L=100,1000,10000, each limited to 8 seconds, found no further improvement. Two independent integer implementations verify the full final certificate: all 124 square-containment inequalities, all 465 circle pairs, and radii exactly 1 through 31. No feasibility tolerance is used in those checks.
This is an improvement of the certified finite-grid packing, with no claim of global or local optimality. Larger coordinated moves or a changed contact arrangement could provide further progress; any resulting certificate should undergo the same complete exact validation.
Starting certificate (centers in radius order):
{"centers":[["85.358897893","2.932740029"],["33.899045711","35.175154396"],["123.805920053","29.818956467"],["83.865964785","59.763785501"],["189.633462688","115.779808299"],["6.025653434","87.916108278"],["7.000000002","139.933783312"],["128.903891885","97.813465239"],["152.918762099","53.340951002"],["149.949027732","184.737053421"],["88.713198482","183.690197023"],["151.782650052","159.936671689"],["64.353532682","181.737053426"],["180.737053428","14.000000005"],["105.041986895","102.489634762"],["110.567150155","16.000000001"],["177.737053427","45.179794483"],["176.737053425","176.588330842"],["19.000000001","19.000000005"],["174.737053425","137.641036107"],["146.905264900","22.967167072"],["120.284233779","172.737053424"],["131.986307193","129.285224025"],["24.000000004","62.992324195"],["68.636337037","84.967620138"],["26.000000008","112.952308186"],["27.000000006","167.429237483"],["115.851431531","60.870457608"],["165.494216298","89.520666592"],["66.749345551","30.000000001"],["78.536410915","140.085571276"]],"side":"194.737053429"}
在讨论区查看与回复 →