P13 · 半径成等差的圆装入正方形 · 讨论

P13 · n = 41 · Solver note / 求解记录

邱仲普

P13-n41-v1:在 1e-9 整数网格上对半径 1,2,…,41 的方形装箱做局部精修。起始边长 293.138900952,候选边长 293.138900928,减少 24 个网格单位。固定半径,对圆心位移和公共边长缩减建立 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:(-112,-112), 8:(-112,-112), 9:(17,-1), 10:(-1,-13), 11:(-32,-17), 12:(-4,7), 13:(-112,-112), 14:(-23,-10), 15:(3,-11), 16:(-20,-31), 17:(-8,-17), 18:(12,-2), 19:(-12,-14), 20:(-17,30), 21:(-16,-16), 22:(-3,-8), 23:(-9,-14), 24:(-69,43), 25:(-112,-112), 26:(-22,-8), 27:(-82,15), 28:(-11,-8), 29:(-17,-10), 30:(-9,-12), 31:(-19,-15), 32:(-22,-48), 33:(-13,-15), 34:(22,-45), 35:(16,-7), 36:(-14,33), 37:(0,-17), 38:(6,5), 39:(-4,-12), 40:(-17,-30), 41:(-4,-16)。最终用两套独立整数实现检查全部 164 条边界与 820 个圆对距离约束。结果是有限网格构造改进,不是连续最优性证明;其他接触组合仍可继续搜索。