Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion
Vincenzo Di Vito, Mehdi Taghizadeh, Deepjyoti Deka, Kaarthik Sundar, Ferdinando Fioretto
cs.LG
2026-08-13
图扩散只学MINLP离散决策,每步投影进组合可行集再解连续子问题。输电切换比Gurobi最快快425倍,9节点目标间隙0.01%。
混合整数非线性规划(MINLP)把两件难事绑在一起:二进制变量 \(z\) 的搜索空间是 \(2^m\),目标函数和约束还可以是非凸的。电网调度里切哪条输电线路、投资组合里选哪组资产,都长成这个样子。\(z\) 一旦固定,剩下的连续变量 \(x\) 可以用现成的非线性求解器处理;\(z\) 错一条,下游连续问题可能直接没有可行解。IEEE 9 节点系统里,负荷母线 4 的三条出线全断开,功率平衡方程当场无解。
学习加速优化的两条老路都没把这块拆干净。嵌进 branch-and-bound 的策略(Neural Branching、Neural Diving)仍然要在线搜离散树;直接回归一个解的代理一次只吐一个点,多个近优离散模式会被抹平,连续松弛再取整还可能越出组合约束。DIFUSCO 这类图扩散已经能在组合空间里采样,但约束多半靠软惩罚或事后修补,中间噪声轨迹并不保证可行。
弗吉尼亚大学、MIT 与洛斯阿拉莫斯国家实验室提出 Constrained Graph Diffusion(CGD):只学离散块在实例参数 \(\xi\) 上的条件分布,连续块交给求解器。训练标签是成对的 \((\xi, z^\star)\),\(z^\star\) 来自精确求解器给出的参考二进制解,不必是全局最优。
生成走四步:
每步都投影,不是只修终点。\(C\xi\) 凸时,投影是到可行松弛点的最小欧氏修正;对应的反向转移在 2-Wasserstein 距离下,也是固定方差核里离可行端点最近的那一个。这不保证整条噪声轨迹都落在可行集里,更不保证采到的是约束数据分布,只保证每一步局部改进。实验里逐步投影的下游目标,稳定好过无投影和只修终点。
训练目标是去噪分数匹配,加上可行性正则:对同一 \((\xi, z^\star, t)\) 抽 \(K\) 个噪声,对松弛预测取均值,再把均值的投影当 stop-gradient 目标。去噪项防止模型塌到任意可行点;可行性项把均值往 \(C\xi\) 推。硬取整不反传。电网任务 \(T=100\)、\(K=20\);投资组合 \(T=30\)、训练约束惩罚 \(K=8\)。
投影算子按问题写。输电切换要求每个带负荷的连通分量连到足够有功和无功容量的发电机,投影本身是一个最小化 Hamming 编辑的 MILP,允许无负荷孤岛。投资组合投到二次约束 \(z^\top P z \le \rho\) 的松弛集。两者都只约束离散结构,都不是下游可行性的充分条件。
两个任务:带线路开断的交流最优潮流,以及带二次组合约束的 Markowitz 投资组合。对照包括去掉投影的 CGD、只在最后一步投影、MLP、GNN、DIFUSCO,以及带可微整数修正层的 LTO-MIP。电网参考解来自 Gurobi v13,时限在 9、197、500 节点上分别是 60、3600、3600 秒,MIP gap 容差 \(10^{-4}\);组合参考解来自 ECOS 分支定界。每张电网 10000 条实例、测试 1000 条;组合 \(n=50\) 共 12000 条、测试 1200 条。
| 网络 | 方法 | Hamming↓ | 精确还原↑ | 下游不可行↓ | 目标间隙↓ |
| 9-bus | CGD | 0.57% | 79.43% | 0% | 0.01% |
| 9-bus | 无投影 | 3.86% | 55.59% | 7.55% | 0.55% |
| 9-bus | 终点投影 | 1.29% | 67.51% | 0% | 0.61% |
| 9-bus | DIFUSCO | 5.36% | 41.03% | 15.63% | 0.58% |
| 197-bus | CGD | 0.14% | 51.20% | 0% | 1.76% |
| 197-bus | MLP | 24.55% | 0% | 100% | 无可行解 |
| 500-bus | CGD | 2.05% | 33.24% | 0% | 0.20% |
| 500-bus | DIFUSCO | 10.36% | 11.03% | 21.18% | 0.78% |
9 节点 12 个二进制、172 个连续变量;500 节点已经是 597 个二进制、8651 个连续变量。MLP 在 197 和 500 节点上全部下游不可行。逐步投影比只修终点更准:9 节点精确还原从 67.51% 提到 79.43%,目标间隙从 0.61% 掉到 0.01%。197 节点上相对无投影,精确还原从 37.17% 提到 51.20%,下游不可行从 4.53% 清零,目标间隙从 2.99% 降到 1.76%。
端到端时间对比 Gurobi 联合 MINLP:
| 网络 | Gurobi | CGD采样 | 连续OPF | 端到端 | 加速比 |
| 9-bus | 140.32 s | 0.03 s | 0.30 s | 0.33 s | 425.2× |
| 197-bus | 1741 s | 0.16 s | 79.09 s | 79.25 s | 22.0× |
| 500-bus | 1204.12 s | 0.11 s | 30.02 s | 30.13 s | 40.0× |
大网上采样几乎不占时间,瓶颈在连续 AC-OPF。Gurobi 在 9 节点要把 MIP gap 收到 CGD 那个 0.01% 水平,平均还要 30.02 秒,相对仍是 91 倍。
投资组合 \(n=50\) 时,CGD 的 Hamming 8.21%、精确还原 54.31%、二次约束零违反、目标间隙 4.92%;无投影间隙 8.43%,最大违反 16.72。\(n=150\) 时 GNN 的 Hamming(12.18%)和精确还原(47.82%)更高,但有约束违反,间隙 13.53%;CGD 零违反、间隙 6.56%,比只修终点的 10.39% 再低一截。端到端 0.020 s / 0.025 s,相对联合 MIQP 分别快 4.6 倍和 48.5 倍。组合规模从 50 涨到 150,CGD 几乎不减速,联合求解器慢了一个数量级。
拿 CGD 的可行解去热启动 Gurobi,认证最优的时间几乎不动:9 节点 140.32 s 变 98.60 s,197 节点 1741 s 变 1783.54 s,500 节点 1204.12 s 变 1213.45 s。瓶颈在证明最优。
对要反复解同一族 MINLP 的人(电网调度、实时组合),这是把组合搜索摊销掉、把连续非凸留给求解器的一条路。扩散能给出多个近优离散模式;逐步投影比事后修拓扑更值钱:同一套可行约束,轨迹里修和终点修,下游目标差一截。9 节点上终点投影已经 0% 不可行,间隙仍有 0.61%,逐步投影收到 0.01%。
它是渐进改进,不是通用求解器替代品。投影算子要按问题写,训练要有求解器标号,连续子问题仍然非凸。大电网 40 倍加速主要来自不再分支离散变量,连续 AC-OPF 自己还要几十秒。热启动帮不上认证,这套方法适合要可行近优、能接受没有最优性证明的场景。
连通性加容量对交流潮流只是必要不充分,下游 AC 可行性靠实验观察,没有证明。松弛点投影后再 0.5 取整,并不自动落回离散可行集:贴着边界时 slack 可能吞不下舍入位移,投资组合附录把这个写成显式充分条件。CGD 本身不给原问题的全局最优证书;参考解也只是时限内求解器返回的最好可行解。
投影在训练里 stop-gradient,非凸或近似修正没有命题 1 的几何保证。只测了两个应用,图结构和约束类型差很远;没有便宜投影的组合约束,整套接口要重做。外层「不可行就再采样」画在总览图里,主实验没有报告平均重试次数。
425.2 倍对比的是 Gurobi 跑到终止(含认证),不是找到同等质量可行解的时间。论文另外给了 9 节点收到同一 0.01% 的 91 倍对照,引用时不要混。