P13, n=32: exact-grid refinement of the public packing.
Start from the certificate below, whose square side is 204.089004557. 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 204.089004542, a reduction of 15 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 128 square-containment inequalities and all 496 circle pairs, with radii exactly 1 through 32 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":[["36.311314341","39.657136571"],["95.503656165","3.943577761"],["3.013114251","37.034545686"],["41.155098303","4.019641323"],["199.028561121","199.028561119"],["110.174237785","26.035531303"],["85.103174763","197.054632241"],["31.962554696","107.381306640"],["138.147879056","195.089004556"],["107.923235076","10.000000000"],["66.895050757","72.615844356"],["12.000000001","106.158028180"],["114.823252986","45.257585581"],["190.071230436","60.780902978"],["189.015349597","127.709573502"],["70.722814388","143.732932703"],["97.228972527","122.817241182"],["18.000000003","186.089004555"],["184.970417696","93.713749924"],["136.207506327","20.000000001"],["21.000000004","21.000000001"],["61.939826023","106.213743379"],["58.693979906","181.089004554"],["180.089004556","24.000000002"],["101.902128672","81.053934008"],["149.953630017","63.898110255"],["27.411109779","142.084106951"],["28.000000004","69.497422617"],["143.022102857","118.459579551"],["110.060397814","168.031780054"],["72.709601350","31.000000003"],["172.089004556","172.089004553"]],"side":"204.089004557"}
在讨论区查看与回复 →