不完美才是完美：用于分支定价切割的学习型列预填充

arXiv:2610.21001v1 公告类型：新 摘要：列生成领域的经验法则警告说，初始列会带来负面影响：热启动可能使对偶解产生偏差，并拖慢分支定价切割的根节点求解。我们表明，只要列以恰当的方式保持不完美，情况恰恰相反。预先加载最优根节点 LP 的支撑集——也就是人们能够提前知晓的最佳列——在我们最困难的一半实例上无法完成求解；而一个由普通路径组成的列池无需包含任何最优解中的路径，将其置于主问题之外，并依据当前平滑对偶解进行定价，反而能够加速根节点求解。由于这些列不必是最优的，生成它们便成为一个学习任务：神经网络边评分器引导一个构造式生成器，在数秒内构建列池。另一个网络根据实例文件预测 Wentges 平滑的初始中心，以及平滑定价查询的方向；求解器自身的更新过程保持不变。有了预填充列和初始中心后，精确定价占据了根节点定价的大部分时间，因此我们围绕其支配性检验重新构建了适用于 GPU 的桶图标记算法，并在 CPU 上进行验证。在电容车辆路径问题的最先进精确求解器 RouteOpt 中，该流程在包含 300 至 1000 个客户的 95 个实例上，仅用 RouteOpt 原版根节点定价时间的 13.2% 就达到了相同的可认证根节点界；仅使用预填充时为 26.1%，最佳情况下速度提升了 17.5 倍。在非相关并行机调度的精确分支定价切割求解器中，结合平滑和学习得到的中心进行预填充，能够认证全部 25 个基准实例，比求解器自身的列生成快 12 倍；后者只能认证其中 20 个实例。