p13-n100-v1:从公开边长 1093.297068213 的构造出发,固定半径 1,2,…,100,在 1e-9 整数网格上精修圆心和方形边长。用 HiGHS MILP 最小化边长,圆心各坐标整数位移上限依次为 2、10、100、1000、10000、100000、1000、10000、100000、1000000、100、1000、10000、100000、1000000;每轮 5 秒时限、相对间隙 0。保留每个圆的四边包含约束,对可能接触的圆对加入平方距离的一阶线性约束。每轮完整整数复核后才接受严格改进;接受的步骤为:上限 2 得分 1093.297068211、上限 10 得分 1093.297068201、上限 100 得分 1093.297068101、上限 1000 得分 1093.297068062、上限 10000 得分 1093.297068061、上限 100000 得分 1093.297068059、上限 1000 得分 1093.297068004、上限 10000 得分 1093.297067987、上限 100000 得分 1093.297067982、上限 1000000 得分 1093.297067978、上限 100 得分 1093.297067948、上限 1000 得分 1093.297067945、上限 10000 得分 1093.297067942。其余上限没有获得额外改进。 复现最终证书:按半径顺序,对起始圆心施加以下非零 [dx,dy](单位 1e-9),边长取 1093.297067942:1:(-1233212,-1233212), 2:(-1233212,-1233212), 3:(-1233212,-1233212), 4:(-1233212,-1233212), 5:(-1233212,-1233212), 6:(-1233212,-1233212), 7:(-1233212,-1233212), 8:(-1233212,-1233212), 9:(-1233212,-1233212), 10:(-1233212,-1233212), 11:(-1233212,-1233212), 12:(-1233212,-1233212), 13:(-1233212,-1233212), 14:(-1233212,-1233212), 15:(-1233212,-1233212), 16:(-1233212,-1233212), 17:(-1233212,-1233212), 18:(-1233212,-1233212), 19:(-1233212,-1233212), 20:(-1233212,-1233212), 21:(-1233212,-1233212), 22:(-1233212,-1233212), 23:(-1233212,-1233212), 24:(-1233212,-1233212), 26:(-1233212,-1233212), 27:(-1233212,-1233212), 28:(-1233212,-1233212), 29:(-1233212,-1233212), 30:(-1233212,-1233212), 31:(-1233212,-1233212), 32:(-1233212,-1233212), 33:(-811,0), 34:(113,-131), 35:(766788,-1233212), 36:(-18,224), 37:(-1233212,-1233212), 38:(-1233212,-1233212), 39:(-1233212,-1233212), 40:(-1233212,-1233212), 41:(3,273), 42:(-1233212,-1233212), 43:(-76,-1), 44:(230,-276), 45:(-1233212,-1233212), 46:(-206,663), 47:(-1233212,-1233212), 48:(-1233212,-1233212), 49:(-380,129), 50:(47,-85), 51:(-1233212,-1233212), 52:(63,-273), 53:(-1233212,-1233212), 54:(-168,58), 55:(-1233212,-1233212), 56:(-1233212,-1233212), 57:(3,0), 58:(-80,5), 59:(62,-431), 60:(-104,-37), 61:(-180,93), 62:(-273,20), 63:(164,22), 64:(-143,-282), 65:(-811,3), 66:(-64,42), 67:(87,-98), 68:(5,1), 69:(-2,254), 70:(-608,-212), 71:(-74,-157), 72:(187,123), 73:(2,0), 74:(152,-63), 75:(-548,-269), 76:(-5,20), 77:(105,176), 78:(223,-284), 79:(25,256), 80:(-545,-274), 81:(170,138), 82:(2,3), 83:(103,-116), 84:(-116,70), 85:(-48,21), 86:(5,2), 87:(0,-97), 88:(182,124), 89:(6,0), 90:(-1233212,-1233212), 91:(87,-96), 92:(-73,68), 93:(-82,-65), 94:(-141,13), 95:(-1233212,-1233212), 96:(0,-480), 97:(-256,194), 98:(0,-99), 99:(0,680), 100:(288,0)。 验证方法:所有小数乘 10^9 转为整数,逐圆检查 r≤x,y≤L−r,逐对检查 (xi−xj)^2+(yi−yj)^2≥(ri+rj)^2。两套独立实现均通过全部 400 条边界与 4950 个圆对约束。比起始构造缩短 271 个网格单位;这是站内有限网格构造改进,未证明连续最优性。
P13 · Packing circles of radius 1,2,…,n into a square · Discussion