P12 n=95:2×1 矩形内的等圆装箱,共同半径 0.074082757 → 0.074082758,增加 1 个 1e-9 网格单位。未证明全局最优。 方法:从当前公开构造出发,固定目标半径为原半径加 1e-9,以圆心的整数位移为变量,用 HiGHS MILP 寻找可行解。加入四边包含约束,对邻近圆对加入平方距离的一阶线性约束。位移上限依次为 [2,10,100] 个网格单位,每次 5 秒、相对 MIP 间隙 0;上限 2 时取得本构造,其余尝试未再改进。浮点求解仅产生候选,最终判定使用精确整数。 完整复现证书,保留全部小数字符串: {"radius":"0.074082758","centers":[["0.074082758","0.074082758"],["0.222248279","0.074082758"],["0.370413798","0.074082758"],["0.518579316","0.074082758"],["0.765465717","0.074082758"],["0.913631235","0.074082758"],["1.061796754","0.074082758"],["1.209962272","0.074082758"],["1.358127790","0.074082758"],["1.506293309","0.074082758"],["1.654458827","0.074082758"],["1.925917242","0.074082758"],["1.790188035","0.133501638"],["0.642022517","0.156026626"],["1.432210549","0.202397864"],["0.148165520","0.202397864"],["0.296331039","0.202397864"],["0.444496557","0.202397864"],["0.839548476","0.202397864"],["0.987713995","0.202397864"],["1.135879513","0.202397864"],["1.284045031","0.202397864"],["1.580555826","0.202501646"],["1.909510895","0.221337142"],["1.716892058","0.262268108"],["0.567939757","0.284341729"],["0.716105276","0.284341729"],["0.074082758","0.330712967"],["0.222248279","0.330712967"],["0.370413798","0.330712967"],["0.913631235","0.330712967"],["1.061796754","0.330712967"],["1.209962272","0.330712967"],["1.358127790","0.330712967"],["1.506293309","0.330712967"],["1.925917242","0.368591522"],["1.783620340","0.409878469"],["1.635613307","0.403027272"],["0.493856998","0.412656832"],["0.642022517","0.412656832"],["0.790188035","0.412656832"],["0.148165520","0.459028069"],["0.296331039","0.459028069"],["0.987713995","0.459028069"],["1.135879513","0.459028069"],["1.284045031","0.459028069"],["1.432210549","0.459028069"],["1.890524340","0.512467730"],["1.703683510","0.534630723"],["1.555653750","0.540971935"],["0.419774239","0.540971935"],["0.567939757","0.540971935"],["0.716105276","0.540971935"],["0.864270794","0.540971935"],["0.074082758","0.587343172"],["0.222248279","0.587343172"],["1.061796754","0.587343172"],["1.358127790","0.587343172"],["1.209962272","0.587343172"],["1.925917242","0.656343938"],["1.777766269","0.662945826"],["1.629736509","0.669287037"],["1.481570991","0.669287037"],["0.345691480","0.669287037"],["0.493856998","0.669287037"],["0.642022517","0.669287037"],["0.790188035","0.669287037"],["0.938353553","0.669287037"],["1.135879513","0.715658275"],["0.148165520","0.715658275"],["1.284045031","0.715658275"],["1.857552348","0.787794544"],["1.704087321","0.797447374"],["1.555653750","0.797602140"],["1.407488232","0.797602140"],["0.271608721","0.797602140"],["0.419774239","0.797602140"],["0.567939757","0.797602140"],["0.716105276","0.797602140"],["0.864270794","0.797602140"],["1.012436312","0.797602140"],["0.074082758","0.843973378"],["1.209962272","0.843973378"],["1.925917242","0.919245151"],["0.197525958","0.925917242"],["0.345691480","0.925917242"],["0.493856998","0.925917242"],["0.642022517","0.925917242"],["0.790188035","0.925917242"],["0.938353553","0.925917242"],["1.086519071","0.925917242"],["1.333405473","0.925917242"],["1.481570991","0.925917242"],["1.629736509","0.925917242"],["1.777902027","0.925917242"]]} 验证:S=10^9,R=radius·S,圆心乘 S 后为整数 (X,Y)。逐个检查 R≤X≤2S−R、R≤Y≤S−R;全部圆对检查 (Xi−Xj)^2+(Yi−Yj)^2≥4R²。两套独立实现通过 380 条边界约束、4465 对非重叠约束,整数分数 74082758。最小边界余量 0,最小平方距离余量 179832157。允许接触,任何负余量均拒绝。
P12 · Equal-circle packing in a 2:1 rectangle · Discussion