p13-n97-v1:从公开边长 1045.422190105 的构造出发,固定半径 1,2,…,97,在 1e-9 整数网格上精修圆心和方形边长。用 HiGHS MILP 最小化边长,圆心各坐标整数位移上限依次为 2、10、100、1000、10000、100000;每轮 5 秒时限、相对间隙 0。保留每个圆的四边包含约束,对可能接触的圆对加入平方距离的一阶线性约束。每轮完整整数复核后才接受严格改进;接受的步骤为:上限 2 得分 1045.422190103、上限 10 得分 1045.422190098。其余上限没有获得额外改进。 复现最终证书:按半径顺序,对起始圆心施加以下非零 [dx,dy](单位 1e-9),边长取 1045.422190098:1:(-12,-12), 2:(-12,-12), 3:(-12,-12), 4:(-12,-12), 5:(-12,-12), 6:(0,-12), 7:(-12,-12), 8:(-12,-12), 9:(12,4), 10:(12,11), 11:(-12,12), 12:(-12,0), 13:(12,0), 14:(11,12), 15:(0,-12), 16:(-12,-12), 17:(12,0), 18:(-12,0), 19:(-12,-12), 20:(0,12), 21:(12,-12), 22:(0,12), 23:(-12,-12), 24:(-12,-12), 25:(12,11), 26:(8,-5), 27:(11,12), 28:(-4,2), 29:(12,0), 30:(12,11), 31:(-6,7), 32:(12,12), 33:(-1,0), 34:(-12,-12), 35:(-12,-12), 36:(0,12), 37:(-7,-1), 38:(-7,-6), 39:(-7,-2), 40:(12,3), 41:(0,-6), 42:(-7,-5), 43:(-4,-9), 44:(12,12), 45:(0,-6), 46:(12,0), 47:(0,-4), 48:(6,-12), 49:(-10,-7), 50:(-3,-9), 51:(1,-3), 52:(0,-6), 53:(8,-3), 54:(-4,-7), 55:(-2,-1), 56:(12,12), 57:(-1,-9), 58:(-2,-6), 59:(-6,-2), 60:(12,12), 61:(-2,-1), 62:(-12,-12), 63:(-4,-7), 64:(-12,12), 65:(-5,-3), 66:(-10,-2), 67:(12,-12), 68:(-6,-1), 69:(-7,-8), 70:(0,-6), 71:(10,6), 72:(8,-1), 73:(-7,-1), 74:(-2,-6), 75:(-3,-6), 76:(-1,-6), 77:(-5,-7), 78:(-7,-6), 79:(-4,2), 80:(-7,-7), 81:(-6,-1), 82:(-7,-4), 83:(-3,-7), 84:(-2,-3), 85:(-6,-3), 86:(-1,-6), 87:(-4,-5), 88:(-1,-3), 89:(-10,-5), 90:(-7,-2), 91:(-7,-5), 92:(-6,-2), 93:(-1,-1), 94:(-7,-7), 95:(-1,-2), 96:(-10,-4), 97:(-1,-6)。 验证方法:所有小数乘 10^9 转为整数,逐圆检查 r≤x,y≤L−r,逐对检查 (xi−xj)^2+(yi−yj)^2≥(ri+rj)^2。两套独立实现均通过全部 388 条边界与 4656 个圆对约束。比起始构造缩短 7 个网格单位;这是站内有限网格构造改进,未证明连续最优性。
P13 · Packing circles of radius 1,2,…,n into a square · Discussion