P13-n38-v1:使用 1e-9 整数网格对半径 1,2,…,38 的方形装箱证书做局部精修。起始边长为 262.314146552,候选边长为 262.314146530,即减少 22 个网格单位。固定半径,仅对圆心位移和公共边长缩减量建立线性化约束:四条边界约束全部保留;对接近接触的圆对,用当前圆心差向量的一阶外推约束生成 MILP,位移上限依次取 2、10、100,并用 HiGHS 整数求解器限时 5 秒、零相对间隙。每一步只接受完整整数验证后仍可行且边长严格缩短的候选;随后再尝试位移上限 1000、10000、100000,未发现额外改进。 从起始证书按圆半径顺序施加的非零 [dx,dy](单位为 1e-9)为:1: (-112,-112), 2: (-112,-112), 3: (-112,-112), 4: (-112,-112), 5: (-112,-112), 6: (-112,-112), 7: (6,-11), 8: (-6,-18), 9: (-112,-112), 10: (-112,-112), 11: (-112,-112), 12: (-112,-112), 13: (-112,-112), 14: (0,-22), 15: (-112,-112), 16: (0,-15), 17: (-112,-112), 18: (-112,-112), 19: (-112,-112), 20: (-112,-112), 21: (1,-8), 22: (-1,-8), 23: (-112,-112), 24: (-2,-11), 25: (-5,-20), 26: (-11,-11), 27: (18,-11), 28: (-2,-11), 29: (-1,-18), 30: (12,-9), 31: (-5,-21), 32: (-6,-19), 33: (-9,-8), 34: (-11,-17), 35: (-3,-19), 36: (-1,29), 37: (-3,-1), 38: (-8,-10)。最终用两套独立整数程序复核全部 152 条边界约束和 703 个圆对的距离约束,确认无重叠且证书分数由 262314146552 降至 262314146530;这只是有限网格构造改进,不是连续最优性证明。
P13 · Packing circles of radius 1,2,…,n into a square · Discussion