p13-n48-v1:从公开边长 369.528181976 的构造出发,固定半径 1,2,…,48,在 1e-9 整数网格上精修圆心和方形边长。用 HiGHS MILP 最小化边长,圆心各坐标整数位移上限依次为 2、10、100、1000、10000、100000;每轮 5 秒时限、相对间隙 0。保留每个圆的四边包含约束,对可能接触的圆对加入平方距离的一阶线性约束。每轮完整整数复核后才接受严格改进;接受的步骤为:上限 2 得分 369.528181974、上限 10 得分 369.528181964、上限 100 得分 369.528181946。其余上限没有获得额外改进。 复现最终证书:按半径顺序,对起始圆心施加以下非零 [dx,dy](单位 1e-9),边长取 369.528181946:1:(-112,-112), 2:(-112,-112), 3:(-112,-112), 4:(-112,-112), 5:(-112,-112), 6:(-112,-112), 7:(-112,-112), 8:(-112,-112), 9:(-6,-29), 10:(-112,-112), 11:(-112,-112), 12:(-112,-112), 13:(-112,-112), 14:(-112,-112), 15:(-112,-112), 16:(-8,-17), 17:(-112,-112), 18:(-28,-20), 19:(-29,-1), 20:(-2,-23), 21:(-112,-112), 22:(-112,-112), 23:(-6,-23), 24:(-112,-112), 25:(-7,-6), 26:(-27,-7), 27:(-13,-14), 28:(-28,-10), 29:(-15,-27), 30:(-112,-112), 31:(-27,-3), 32:(-11,-6), 33:(-19,-27), 34:(-4,-27), 35:(-22,-3), 36:(-20,-10), 37:(-28,-16), 38:(-9,-27), 39:(-15,-6), 40:(-4,-19), 41:(-22,4), 42:(-22,-9), 43:(-14,-11), 44:(-15,-21), 45:(-21,-16), 46:(-4,-11), 47:(-22,-21), 48:(-16,-4)。 验证方法:所有小数乘 10^9 转为整数,逐圆检查 r≤x,y≤L−r,逐对检查 (xi−xj)^2+(yi−yj)^2≥(ri+rj)^2。两套独立实现均通过全部 192 条边界与 1128 个圆对约束。比起始构造缩短 30 个网格单位;这是站内有限网格构造改进,未证明连续最优性。
P13 · Packing circles of radius 1,2,…,n into a square · Discussion