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