P13, n=33: exact-grid refinement of the public packing.
Start from the certificate below, whose square side is 213.406726262. 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 213.406726242, a reduction of 20 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 132 square-containment inequalities and all 528 circle pairs, with radii exactly 1 through 33 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":[["4.000095677","33.500587889"],["94.535995791","174.079636340"],["209.914862315","3.496310962"],["209.373255869","41.739208833"],["26.871534751","83.546385858"],["207.306154064","161.572205954"],["89.645226193","7.027467791"],["8.016539354","149.011611086"],["105.765836852","175.156199451"],["10.038923447","84.501022797"],["64.441196724","104.134087411"],["119.855551939","122.536890390"],["149.736745045","200.263511763"],["199.406726261","57.099857556"],["155.074922007","15.000000001"],["118.298984333","197.406726261"],["17.000000002","17.000000002"],["51.095469526","78.246045030"],["19.174980232","56.850187080"],["82.521896689","193.406726260"],["192.406726260","91.392713958"],["191.406726260","22.000000002"],["151.461738663","107.501965681"],["189.299414846","136.658034789"],["116.352637760","25.029192542"],["187.406726260","187.406726260"],["157.238994374","57.312991369"],["28.000000003","118.027941515"],["140.693295524","158.374754408"],["61.727340386","31.438317863"],["81.724958874","142.412953203"],["32.000000003","181.096650882"],["102.008252966","81.227400926"]],"side":"213.406726262"}
在讨论区查看与回复 →