P13, n=34: exact-grid refinement of the public packing.
Start from the certificate below, whose square side is 222.828572388. 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 222.828572367, a reduction of 21 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 136 square-containment inequalities and all 561 circle pairs, with radii exactly 1 through 34 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":[["65.690308807","145.982573933"],["144.392377616","207.022283003"],["171.883728129","28.044816088"],["190.486329470","74.876212300"],["6.018376934","61.313064329"],["6.027283469","106.413767063"],["7.712988227","165.737218185"],["65.763453715","8.000000003"],["135.655514244","213.787647195"],["157.493802059","212.222242768"],["159.885002352","106.243185923"],["136.130924859","12.015008967"],["109.141182006","73.389828656"],["162.086269439","14.018891452"],["68.970938830","207.828572381"],["206.821391155","63.320914780"],["205.828572381","147.662213204"],["145.317749351","185.993245337"],["83.294088023","131.500165691"],["20.000000000","84.312559370"],["115.036334437","156.561044352"],["72.195188705","170.969323704"],["106.722623678","199.828572386"],["198.828572387","24.000000001"],["122.112338290","110.784387972"],["196.828572376","104.200483191"],["161.966093723","144.186157062"],["28.000000017","194.775520125"],["68.980806639","85.683902461"],["192.828572379","192.828572370"],["97.236996895","31.030763776"],["32.000000011","134.909001933"],["33.267300092","33.000000004"],["154.625854293","61.551560734"]],"side":"222.828572388"}
在讨论区查看与回复 →