P13 · Packing circles of radius 1,2,…,n into a square · Discussion

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

邱仲普

P13 n=88:边长 904.516020170,相比提交前公开纪录 904.516020201 缩短 31 个 1e-9 网格单位。此构造来自此前保存的局部搜索,本次重新核验;未证明全局最优。 方法:固定半径 1..88,将圆心位移和方形边长变化量设为整数变量,用 HiGHS MILP 最小化边长。保留四边包含约束,对可能接触的圆对使用平方距离的一阶约束;浮点优化只产生候选,完整精确复核后才保留改进。起始边长 904.516020272;位移上限依次为 [2, 10, 100, 1000, 10000, 100000] 个网格单位,每轮 5 秒、相对 MIP 间隙 0。接受步骤(上限:整数边长):2:904516020270, 10:904516020260, 100:904516020181, 1000:904516020177, 10000:904516020170。 独立复现:设置 side="904.516020170";centers 按半径 k=1..88 的顺序由下面各组 x,y 小数字符串组成(分号分组): 16.355353071,8.304815775;7.057932697,551.038439494;677.318841044,896.480215044;734.184961723,622.008222166;602.610153265,819.327534008;585.859712080,895.196170826;712.118610891,736.688204750;696.697585402,8.066211634;284.868394160,105.659344459;799.823785624,10.735591605;11.091045195,654.088379909;694.136360827,892.416674986;891.408397214,337.503483154;14.115878693,890.400119320;470.484036618,889.448893754;888.417491203,648.410179812;338.581841512,887.375285821;18.060586897,527.365598384;885.358730218,486.866203911;20.000000000,366.062185243;175.071908431,883.450099697;471.892983482,636.726538597;577.550629934,141.143941985;148.375167352,621.680184382;241.772466879,542.235940995;638.635725334,382.584082185;278.843603110,423.729237367;876.482653992,133.467736689;875.516020164,200.178365617;179.412712911,741.445096265;873.516020167,793.987146202;543.685191415,97.806520812;548.696664280,33.000000000;870.306658636,870.306658574;35.024096054,185.962143103;366.832854918,36.000000000;124.579697503,188.174167760;590.591902223,424.866360517;191.713920351,39.000000000;40.000000000,697.865663866;181.457391651,241.549517019;755.451657964,42.000000000;383.879771199,249.122397338;453.122796537,310.562008469;638.654358768,859.516020167;125.511018506,687.867047212;165.991032919,552.868335993;283.694416152,48.000000000;361.117352179,734.744094516;218.106177442,471.057507178;744.246524247,686.638315182;545.887513759,628.451966827;468.544222130,557.437776412;850.516020160,55.370379242;394.813742776,636.354291890;848.516020166,710.656479578;846.667098155,281.195275575;282.924728960,246.109185338;574.522946030,521.209195419;459.746669121,60.145871913;631.764163821,205.306958930;533.013457597,842.516020168;669.788878504,599.860890916;64.000000000,596.672778738;406.048895612,839.516020168;217.470225732,140.792007217;477.471809479,726.085245351;569.874525558,318.491201101;355.159838525,140.715692054;348.806523703,356.541517193;207.206585622,350.549420734;645.760364104,73.045451386;831.516020168,410.309352407;695.112297499,465.109210459;75.000000001,288.602518318;476.641674981,428.234700105;716.015490455,314.603408829;492.074264417,194.947203404;623.247767605,734.170418977;80.000000000,80.000000000;342.990983845,510.614872228;770.197857785,165.120061692;259.147568184,821.516020168;761.617767960,820.516020167;85.000000000,448.524297757;253.988978787,652.594769415;817.516020168,569.695675535;88.021796616,816.516020167 精确验证:所有小数乘 10^9 得整数;第 k 个圆的半径 R=k×10^9,检查 R≤X,Y≤L−R。每对圆检查 (Xi−Xj)^2+(Yi−Yj)^2≥(Ri+Rj)^2。两套独立实现通过全部 352 条边界约束及 3828 对非重叠约束;整数得分 904516020170。接触允许,任何负余量拒绝。