P13, n=40: exact-grid refinement of the public packing.
Start from the certificate below, whose square side is 282.769696459. Circle i has fixed radius i. Scale lengths by Q=10^9. Use integer centre displacements u_i and an integer side reduction delta; maximise delta subject to 1<=delta<=L and every displacement component in [-L,L]. Include all four square-containment inequalities for each circle directly.
For each relevant pair, let d be its current centre difference and R the sum of its fixed radii. Impose 2*d dot (u_i-u_j) >= R^2-|d|^2. Divide this row by 2R and add a 0.00001 grid-unit numerical margin. The omitted squared displacement is nonnegative. Pairs with normalised initial slack above 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 five-second limit per neighbourhood.
Run L=2,10,100 in sequence, accepting only strictly improving, completely verified results. The final side is 282.769696441, a reduction of 18 grid units. Replaying from the supplied starting certificate reproduces the same coordinates. Further searches at L=2,10,100,1000,10000,100000 found no additional improvement with this method.
Two independent integer implementations verify all 160 square-containment inequalities and all 780 circle pairs, with radii exactly 1 through 40 and no feasibility tolerance. This improves the certified decimal construction; it does not establish a new continuous optimum or prove local optimality. Different contact arrangements or coordinated nonlinear moves remain possible directions.
Starting certificate, with centres in radius order:
{"centers":[["268.975497050","216.763971082"],["182.960433263","98.300359596"],["272.394301520","4.493788249"],["209.481410838","221.320232958"],["277.260214004","65.354451352"],["6.341720494","276.739418575"],["70.653916120","275.112844125"],["133.244972387","273.883112789"],["209.916099884","273.505254731"],["110.873165763","150.801978161"],["178.719582819","11.969804807"],["216.805595389","129.422187096"],["207.171819112","13.000000001"],["124.141146947","215.176694267"],["267.769696456","167.708602643"],["266.748663371","198.700660752"],["264.875946420","83.671849436"],["18.003958174","92.116069114"],["54.693992608","96.901302185"],["95.151537918","20.065042957"],["21.000000001","193.917563318"],["190.746322394","43.906359505"],["131.652162178","121.790254625"],["84.582605456","128.908329515"],["179.219475321","128.343245270"],["160.273593194","80.992917386"],["255.769696452","127.459379045"],["142.597979417","28.068051609"],["215.601985104","88.439448682"],["101.277066241","252.769696458"],["31.000000004","141.314150465"],["146.234147173","174.829459650"],["101.630040466","74.517292019"],["248.769696453","34.877307907"],["36.360591045","247.769696458"],["246.769696450","246.769696457"],["78.841869702","189.637597199"],["216.082643816","179.432449697"],["39.000000001","39.000000007"],["170.559098547","242.769696454"]],"side":"282.769696459"}
在讨论区查看与回复 →