基于迭代重加权最小二乘的固定费用网络流支撑发现方法
arXiv cs.AI · · 发布于 2026-09-11 · 4 分钟阅读
针对大规模单商品固定费用网络流问题，本文提出一种可扩展的连续优化算法。该方法以迭代重加权最小二乘框架为基础，用平滑非凸的 Lasry-Lions 替代函数替换不连续的固定费用与线性弧成本目标，进而求解一系列加权二次流子问题；每个子问题采用热启动的对偶半光滑牛顿法求解，其牛顿系统具有加权图拉普拉斯结构，可借助现代拉普拉斯求解器高效处理。为进一步改善组合问题的弧支撑发现效果，作者还提出引入目标驱动扰动重启与锚点并集受限搜索的算法变体，联合利用迭代重加权最小二乘与互补固定费用网络流启发式所发现的支撑。在 410 个基准、合成及大规模实例上的计算实验表明，该方法在所评估的可扩展算法中取得最佳目标质量，相对限时混合整数线性规划参考解的平均差距为 1.316%，在非混合整数线性规划方法中获胜或持平率达 90.0%。
当前来源仅提供摘要，以下要点基于摘要生成；可通过官方原文查看完整信息。问题定位
固定费用网络流问题（FCNFP）将连续流量分配与离散弧激活决策耦合，是网络设计与资源分配中的经典模型，但计算上具有挑战性。
精确方法的局限
精确混合整数线性规划（MILP）建模能忠实刻画固定费用结构，但在大规模网络上往往难以求解。
算法框架
论文基于迭代重加权最小二乘（IRLS）框架，提出面向大规模单商品 FCNFP 的可扩展连续优化算法。
目标替代
方法用光滑非凸的 Lasry--Lions 代理函数替代不连续的固定费用与线性弧成本目标，并依次求解一系列加权二次流量子问题。
子问题求解
每个子问题由热启动的对偶半光滑牛顿法求解，其牛顿系统具有加权图拉普拉斯结构，因而可使用现代拉普拉斯求解器。
支撑集增强变体
作者开发了一种算法变体，引入目标驱动的扰动重启与锚并集受限搜索，联合利用 IRLS 与互补 FCNFP 启发式发现的支撑集。
实验结果
在 410 个基准、合成与大规模实例上，该方法在评估的可扩展 FCNFP 算法中目标质量最佳，相对限时 MILP 参考的平均差距为 1.316%。
对比表现
在非 MILP 方法之间比较时，该方法的胜或平率达到 90.0%。
总体结论
结果表明，把光滑连续优化与支撑级搜索相结合，是产出大规模 FCNFP 高质量可行解的有效策略。