AAAI 2026 自动驾驶最小费用流对偶预测 ε-relaxation 学习增强算法芯片布线交通网络

Minimum-Cost Network Flow with Dual Predictions¶

会议: AAAI 2026
arXiv: 2601.20203
代码: 暂无
领域: 自动驾驶 / 组合优化 / 学习增强算法
关键词: 最小费用流, 对偶预测, ε-relaxation, 学习增强算法, 芯片布线, 交通网络

一句话总结¶

首次提出基于对偶预测的最小费用网络流算法，在经典ε-relaxation上通过机器学习的对偶初始解实现warm-start，理论上将时间复杂度与预测误差的∞范数挂钩（一致且鲁棒），在交通网络和芯片逃逸布线上分别实现12.74×和1.64×的平均加速。

研究背景与动机¶

领域现状：最小费用网络流(MCF)是组合优化的核心问题，广泛应用于交通网络路由、芯片设计自动化(EDA)、计算机视觉(多目标跟踪)等领域。经典算法包括Network Simplex、连续最短路(SSP)、ε-relaxation等。

核心痛点：大规模MCF实例（百万级节点/边）求解耗时巨大。传统最坏情况分析过于悲观——如SSP理论需指数级迭代，但实际常快速收敛。

学习增强算法兴起：近年"algorithms with predictions"框架在匹配(Dinitz et al. 2021)、最大流(Davies et al. 2023)、最小割等问题上取得成果，但MCF领域尚属空白。

为什么选ε-relaxation：(a)对偶算法，预测仅需n个变量（vs原问题m个）；(b)天然适合并行化（节点迭代解耦）；(c)理论分析清晰，不像NS复杂度未知。

核心idea：学习MCF的对偶最优解预测 \(\hat{p}\)，warm-start ε-relaxation，使复杂度从 \(O(n^3\log(nC))\) 降至 \(O(n^3\log\|\hat{p}-p^*\|_\infty)\)。

方法详解¶

整体框架¶

给定网络 \(G=(V,E)\)（n节点、m条边，边权 \(a_{ij}\)，容量 \([b_{ij}, c_{ij}]\)，节点供给 \(s_i\)）和对偶预测 \(\hat{p}\) → 预处理（平移使 \(\min_i \hat{p}_i=0\)，再clip到 \([0,(n-1)C]\)）→ warm-start ε-relaxation求解最优流。结合cost-scaling技巧实现多尺度迭代收敛。

核心思想：ε-relaxation维护满足ε-complementary slackness的(x,p)对，迭代消减每个节点的surplus \(g_i\) 至零使x成为可行流。对偶预测提供更好的初始p，减少迭代次数。

关键设计一：Warm-start ε-relaxation（Algorithm 1）¶

利用对偶平移不变性（Fact 1）归一化预测
Clip到合法范围（Lemma 1：存在最优对偶解在 \([0,(n-1)C]\) 内）
核心引理 (Lemma 2)：\(\beta(\hat{p}) \leq 2\|\hat{p}-p^*\|_\infty\)，即warm-start的reduced cost length上界与预测误差的∞范数线性相关
Theorem 1（vanilla版）：复杂度 \(O(\min\{n^3\|\hat{p}-p^*\|_\infty, n^4C\})\)；0/1流实例为 \(O(\min\{mn\|\hat{p}-p^*\|_\infty, mn^2C\})\)

关键设计二：Cost-scaling版（Algorithm 2）¶

将边权按比例 \((n+1)/c^T\) 缩放，从粗到精迭代 \(T=\log\|\hat{p}-p^*\|_\infty\) 轮
每轮ε-relaxation复杂度 \(O(n^3)\)（因前一轮解提供良好初始化）
Theorem 2：\(O(\min\{n^3\log\|\hat{p}-p^*\|_\infty, n^3\log(nC)\})\)
鲁棒性保证：预测完全错误时退化到经典 \(O(n^3\log(nC))\) bound

关键设计三：两种预测学习方式¶

固定预测（交通网络）：网络拓扑固定、边权随机波动，通过最小化 \(\min_{\hat{p}} \frac{1}{k}\sum_i \log\|\hat{p}-p^{(i)}+\Delta_i\|_\infty\) 学习期望对偶解（凸优化，Frank-Wolfe求解），PAC样本复杂度 \(\tilde{O}(n/\varepsilon^2)\)（Theorem 3）
特征预测（逃逸布线）：UNet风格CNN从3通道特征图（障碍物、到pin距离、到边界距离）预测对偶解，MSE损失训练，样本复杂度 \(O(n \cdot d_{NN} \cdot \log(nC)/\varepsilon^2)\)（Theorem 4）

损失函数¶

固定预测：最小化代理损失 \(\sum_i \log\|\hat{p}-p^{(i)}+\Delta_i\|_\infty\)（凸优化，Frank-Wolfe求解）
CNN预测：MSE损失（\(l_2\) 范数），因 \(l_\infty\) 训练困难。UNet架构含2个下采样+2个上采样模块，每模块2层3×3卷积+GroupNorm，残差连接。Adam优化器，lr=1e-3，epoch 15处降10倍，batch=16
理论证明了端到端算法性能的伪维度bound（Lemma 3/4），保证泛化

实验¶

主实验一：交通网络（DIMACS道路网络 benchmark）¶

实例组	节点数	ε-R(带预测)	ε-R(无预测)	Network Simplex	SSP
paths_04_NV	261K	1.50s	24.25s	19.29s	11.68s
flow_04_NV	261K	18.21s	112.93s	20.22s	51.21s
paths_05_WI	519K	3.88s	58.84s	61.41s	73.49s
flow_06_FL	1049K	45.95s	630.73s	271.13s	1769.58s
paths_07_TX	2074K	25.87s	323.85s	694.12s	2113.63s
flow_07_TX	2074K	238.41s	2247.67s	1127.91s	极慢
平均加速	—	1.00×	12.74×	12.08×	38.19×

主实验二：芯片逃逸布线¶

实例	板尺寸	Pin数	ε-R(带预测)	ε-R(无预测)	NS	SSP
1	296×277	710	2.10s	3.30s	11.75s	11.55s
5	635×572	1366	45.24s	70.18s	453.92s	280.03s
10	1205×1374	1985	630.49s	955.19s	极慢	2592.41s
平均加速	—	1.00×	1.64×	11.19×	7.53×

关键发现¶

交通网络加速最显著：对偶预测使ε-relaxation相比无预测版提速6.2~21.4倍，0/1流实例（paths_*）甚至超越Network Simplex
CNN跨尺度泛化强：板尺寸从300×300到1000×1000变化巨大，单一CNN模型即可泛化
理论与实验一致：合成实验中运行时间随预测误差增长符合理论曲线，且大误差时退化到经典复杂度
并行化潜力大：道路网络为平面图（4-可着色），理论可再加速n/4倍
Cost-scaling分步分析：每步running time逐步递减（如paths_04从2.96s到<0.4s），说明理论分析过于保守
固定预测学习简单高效：仅需10个样本即可学到有效对偶预测（高斯扰动边权，凸优化求解）
CNN训练收敛快：仅80个实例训练、40个epoch即收敛，验证了对偶解空间的结构性

亮点¶

首个最小费用流的学习增强算法，理论完备（一致性+鲁棒性+PAC样本复杂度）
复杂度与∞范数挂钩（而非0范数），不需要精确预测每个分量，更实用
两种学习范式（固定预测/CNN预测）覆盖固定/变化拓扑两类场景
大规模真实道路网络（200万节点）验证有效，加速12.74×
0/1流实例上带预测的ε-relaxation甚至优于Network Simplex（实际最流行的MCF算法）
理论与实验吻合度高：合成实验中运行时间随预测误差的增长曲线与理论bound一致

局限性¶

Cost-scaling参数T需调优：理论可猜测但有额外开销，实验中手动设T=T̂+2
CNN用MSE而非∞范数损失：代理损失与理论bound的gap未被量化
未实施并行化：虽然ε-relaxation天然适合并行（道路网络4-可着色），但实验未做并行对比
仅整数假设：要求容量和供给为整数，非整数场景推广待探索
逃逸布线加速有限：仅1.64×，可能因CNN预测精度不够或问题结构差异
未与最新SOTA对比：Brand et al.(2023)几乎线性时间算法虽为纯理论，但未讨论实际可行性

评分¶

⭐⭐⭐⭐ — 理论工作扎实，一致性+鲁棒性复杂度bound优雅。交通网络加速非常显著（12.74×），逃逸布线适中（1.64×）。将学习增强算法扩展到MCF这一核心优化问题，兼具理论深度和实践价值。注意本文虽归入autonomous_driving但更偏运筹优化/交通优化。