P13, n=35: exact-grid refinement of the public packing.
Start from the certificate below, whose square side is 232.692051268. 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 232.692051251, a reduction of 17 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 140 square-containment inequalities and all 595 circle pairs, with radii exactly 1 through 35 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":[["127.130919463","229.696568562"],["137.915249892","85.711281031"],["56.740013933","225.866926828"],["4.742260756","96.443750943"],["227.151389211","136.338155933"],["226.692051254","83.772793163"],["174.627766215","225.600083936"],["116.359588701","224.692051267"],["65.941125502","9.000000000"],["92.193340518","155.076818762"],["170.981576141","11.081501800"],["12.244407219","220.517649329"],["41.327151607","219.692051267"],["143.324154085","14.000000001"],["15.000000001","146.648603583"],["16.710413246","77.895295977"],["215.629518813","63.605966051"],["214.692051266","157.081409070"],["21.078618518","112.784265732"],["115.083771816","83.978674761"],["100.402006428","123.452102406"],["124.061615093","159.669038241"],["209.692051265","23.000000002"],["172.790093562","159.949499177"],["25.000000002","185.378437048"],["146.974769212","117.129305003"],["56.898971879","143.737219744"],["146.292847798","204.692051265"],["203.598125681","203.598125681"],["202.692051265","110.605608912"],["64.131733385","86.189959501"],["32.000000002","32.000000003"],["100.364019278","33.063756656"],["83.374743694","198.692051264"],["163.828275420","58.503719044"]],"side":"232.692051268"}
在讨论区查看与回复 →