EnerGNN: Learning Optimization-Compatible Energy Functions for Exact Constrained Combinatorial Inference¶

会议: NeurIPS 2026
arXiv: 2610.33930
代码: https://github.com/nikitrian/EnerGNN
领域: 优化/理论
关键词: 组合优化, 基于能量的模型, 混合整数规划, 图神经网络, 零样本约束注入

一句话总结¶

EnerGNN 提出将组合配置的偏好函数学习为可混合整数线性规划（MIP）精确编码的分段线性能量函数，结合图神经网络编码器与紧凑非线性 ReLU 头部，实现了显式硬约束下的精确全局能量极小化与 100% 可行解推断。

研究背景与动机¶

组合优化问题广泛存在于工业制造、物流调度与供应链设计等实际运筹系统中。传统神经组合优化方法通常尝试直接端到端输出离散决策、基于预测概率贪心解码或通过学习到的变量边际分布构造启发式搜索邻域（如 Neural Diving、ConPaS 等）。然而，在面对严格的物理容量、逻辑互斥或时间窗硬约束时，纯神经网络生成往往极易产生不可行解；而一旦测试环境发生约束变更或受到外界扰动，依赖变量分布裁剪搜索空间的先验启发式方法将不可避免地导致可行性崩塌或严重退化。

基于能量的模型（Energy-Based Models, EBMs）天然能够为完整的输出构型打分并建模变量间的强耦合协同效应，但传统的表达型神经能量函数由于高度非凸与离散搜索空间的组合爆炸，其推断过程大多受限于连续松弛、朗之万采样或梯度下降等近似求解机制，无法保证满足显式硬约束，更无法提供确定性的最优性保证。与之相对，混合整数规划（MIP）求解器能够保证在显式硬约束域内进行全局寻优，但其对目标函数的数学形式有着极其严苛的规范要求，传统深度神经网络很难直接嵌入到求解器内精确极小化。

针对这一学习与精确优化之间的接口割裂，本文的核心视角是将“主观质量偏好”与“显式可行约束”彻底解耦：神经网络不直接做动作决策，而是学习一个能精确转化为 MIP 等价表述的离散配置能量景观，由成熟求解器在部署期强行施加硬约束进行极小化。核心 idea：将二值离散配置的能量函数分解为离线只算一次的二部图神经网络编码器、仿射等价的构型感知 Readout 与分段线性 ReLU 头部，使非线性能量可在显式硬约束下无损编译为标准 MIP 并由求解器精确全局极小化，同时支持测试期零样本约束注入。

方法详解¶

整体框架¶

EnerGNN 的核心计算流由“离线图实例编码”、“构型感知仿射读出（Readout）”、“分段线性 ReLU 能量头”以及“求解器内在线神经 MIP 精确推断”四个阶段构成。输入为特定优化实例的二部图结构与二值决策变量向量 $\mathbf{y} \in \{0,1\}^n$，输出为使得学习能量最小化且完全落入显式约束多面体内部的严格可行解 $\mathbf{y}^\star$。

在离线阶段，二部消息传递图神经网络（Bipartite MPNN）首先对问题实例中的变量与约束节点进行多轮特征传播，抽取静态图嵌入与节点隐向量，该过程在优化求解前仅执行一次并作为常数固定。在推断求解阶段，MIP 求解器维护决策向量 $\mathbf{y}$，通过紧凑的仿射或精确线性化运算构造输入向量 $\mathbf{z}^0(\mathbf{y})$，并通过 Big-M 表述将单隐层 ReLU 能量头精确转化为混合整数线性约束。由于部署期所施加的硬约束 $\mathbf{A}_y \mathbf{y} \le \mathbf{b}_y$ 与网络参数完全独立，模型能够在不重训的前提下即插即用地适配各种外部场景约束变更。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：问题图结构 G + 二值决策变量 y"] --> B["阶段 1：二部图编码与构型感知 Readout<br/>静态 GNN 实例嵌入 + 仿射决策池化 z0(y)"]
    B --> C["阶段 2：ReLU 能量头的精确 MIP 编译<br/>IBP 紧致界传播 + Big-M 线性化表述"]
    C --> D["阶段 3：最优性感知对比学习与能量景观校准<br/>KL 排序对齐 + 动态尺度 Huber 差距校准"]
    D -->|施加部署期显式硬约束 Ay y <= by| E["阶段 4：求解器全局极小化与零样本约束注入<br/>无损 MIP 推断输出 100% 可行解 y*"]

关键设计¶

1. 构型感知 Readout：在仿射兼容约束下保留高阶组合信息 要将深度神经网络输出的能量无损嵌入标准混合整数线性规划模型，能量头输入 $\mathbf{z}^0(\mathbf{y})$ 必须是二值决策变量 $\mathbf{y}$ 的仿射变换或能通过辅助变量无缝线性化的逻辑映射。传统方法若直接将数千维的原始二值向量输入全连接层，将导致后续 MIP 编译引入巨量的二进制松弛变量与 Big-M 约束，摧毁求解器分支定界效率。

EnerGNN 针对这一痛点设计了结构化 Readout：首先利用静态 GNN 编码器抽取的节点特征 $\mathbf{h}_v$ 与全局特征 $\mathbf{h}_{\mathcal{G}}$，将决策向量表示为选中变量的加权和 $\sum_{v} y_v \mathbf{h}_v$。针对具体运筹结构，Readout 进一步引入仿射辅助项 $\mathbf{z}_{\mathrm{lin}}(\mathbf{y})$：在二次背包问题（QKP）中引入未选中变量池 $\sum_{i}(1-y_i)\mathbf{h}_i$、选中比率与总容量占用率；在组合拍卖（CA）中引入物品被覆盖指示变量 $u_c = \mathbb{I}[\sum_{b: c \in \mathcal{N}(b)} y_b \ge 1]$；在细胞治疗供应链（CART）中引入临床需求点被覆盖指示变量 $q_c$。以 CA 为例，逻辑析取关系通过双向不等式实现严密线性化： $$u_c \le \sum_{b:\, c \in \mathcal{N}(b)} y_b, \quad u_c \ge y_b \quad (\forall b \text{ s.t. } c \in \mathcal{N}(b))$$ 该设计保证了读出层不仅满足维度紧凑性，而且在数学上严格保持线性规划兼容性。

2. ReLU 能量头的精确 MIP 编译与区间界传播剪枝 若仅采用线性加权作为能量函数，能量模型退化为可分离的独立单变量打分，数学上无法表达二值变量之间的任何非零二次协同交互。EnerGNN 在理论上证明：一个单隐层 ReLU 能量头通过恒等式 $y_i y_j = \max(0, y_i + y_j - 1)$，仅需至多 $|\mathcal{E}|$ 个 ReLU 神经元即可无损表达任意成对二次协同项。

为了将该 ReLU 能量头转化为高效的混合整数规划形式，EnerGNN 为每个具有有限前激活界 $[\underline{a}_j^l, \overline{a}_j^l]$ 的神经元引入二值激活指示变量 $z_j^l \in \{0,1\}$，构建标准精确紧致 Big-M 约束： $$h_j^l \ge a_j^l, \quad h_j^l \ge 0, \quad h_j^l \le a_j^l - \underline{a}_j^l(1 - z_j^l), \quad h_j^l \le \overline{a}_j^l z_j^l$$ 求解瓶颈取决于 Big-M 约束的松紧程度及二值激活变量的数量。EnerGNN 结合区间界传播（Interval Bound Propagation, IBP）与运筹域特定边界（如 QKP 分数背包松弛上界、CART 设施容量上下界），在前向逐层推导最紧激活上下界。一旦发现神经元在可行域内恒正（$\underline{a}_j^l \ge 0$）或恒负（$\overline{a}_j^l \le 0$），便直接固化为线性等式或零值剪枝，彻底消除对应的二值变量 $z_j^l$，从而在保持非线性表达力的同时极大压缩了 MIP 求解搜索树规模。

3. 最优性感知对比学习与能量景观校准 学习目标的核心难点在于如何引导连续能量标量自洽地反映离散可行解的原目标相对优劣（Primal Gap），同时避免对不可行解产生错误的低能量诱导。如果单纯强行拉大所有可行解与不可行解的绝对能量间距，往往会破坏可行域内部精细的梯度结构。EnerGNN 提出了包含三项协同优化的复合训练准则： $$\mathcal{L} = \mathcal{L}_{\mathrm{con}} + \lambda_{\mathrm{cal}}\mathcal{L}_{\mathrm{cal}} + \lambda_{\mathrm{inf}}\mathcal{L}_{\mathrm{inf}}$$ 其中，最优性感知对比损失 $\mathcal{L}_{\mathrm{con}} = \mathrm{KL}(p^\star \,\|\, p_\theta)$ 强制预测能量 Softmax 分布逼近由真实最优相对差距 $g_i$ 构造的锐化玻尔兹曼分布 $p^\star_i \propto \exp(-g_i / \tau_{\mathrm{rank}})$（对不可行样本置零质量）。为了进一步将抽象能量绝对数值映射到有界物理指标上，校准损失 $\mathcal{L}_{\mathrm{cal}}$ 对可行解实施自适应尺度 Huber 回归： $$\mathcal{L}_{\mathrm{cal}} = \frac{1}{|\mathcal{F}|} \sum_{i \in \mathcal{F}} H_{\delta_{\mathcal{F}}}\!\left(E_{\theta}(\mathcal{G},\mathbf{y}_i) - g_i\right)$$ 其转折阈值 $\delta_{\mathcal{F}}$ 随着当前候选池内可行差距跨度动态缩放；辅助不可行损失 $\mathcal{L}_{\mathrm{inf}}$ 则将越界解对齐至对数违约幅度 $\log(1 + \nu_k)$，在保证学习景观平滑的同时，将不可行解的物理规避交由推断期的 MIP 求解器执行。

一个完整示例¶

以具备 16 个候选制造基地的 CAR T 细胞治疗供应链（CART）层级规划为例： 1. 实例输入：各临床采血点的患者动态到达时序、各候选基地的产能上限与建造固定成本，构建为完备二部图 $\mathcal{G}_{\mathrm{CART}}$。 2. 离线表征：通过 2 轮 MPNN 提取各节点特征，静态计算完成后锁定常量。 3. 神经 MIP 求解：MIP 求解器维护 16 个一阶段基地选址二值变量 $\mathbf{y} \in \{0,1\}^{16}$。求解器在满足至少满足峰值总需求容量硬约束 $\sum_m \kappa_m y_m \ge \kappa_{\mathrm{ref}}$ 及最大选址数量 $\sum_m y_m \le B$ 的约束空间内，极小化 MIP 编码的 EnerGNN 能量。Gurobi 仅用 1.46 秒即返回全局能量极小解（平均激活 3.21 个核心基地）。 4. 下游调度：固定选定的 3 个基地后，二阶段下游具体患者排程与冷链物流调度的决策变量与约束规约缩减达 77%，下游大规模线性流网络由 Gurobi 快速解出全局最优调度，全流程总时间由全量单体 MIP 的 3728.82 秒锐减至 214.03 秒，且原最优差距仅为 0.05%。

损失函数 / 训练策略¶

模型采用 Adam 优化器在离线采样的解构型池 $\mathcal{Y} = \mathcal{F} \cup \mathcal{I}$ 上训练 2000 个 Epoch。候选池由求解器分支定界过程中的中间解、局部 Hamming 扰动、贪心启发式探索以及不同违约程度的对抗掩码组合而成。各基准训练超参数配置如下： - CART：学习率 $2 \times 10^{-6}$，权重衰减 $1 \times 10^{-5}$，$\lambda_{\mathrm{cal}}=1.0$，$\lambda_{\mathrm{inf}}=0.1$，预测温度 $T=0.1$，排序温度 $\tau_{\mathrm{rank}}=0.05$。 - QKP：学习率 $1 \times 10^{-5}$，权重衰减 $1 \times 10^{-5}$，$\lambda_{\mathrm{cal}}=0.05$，$\lambda_{\mathrm{inf}}=0.1$，$T=0.5$，$\tau_{\mathrm{rank}}=0.05$。 - CA：学习率 $1 \times 10^{-6}$，权重衰减 $1 \times 10^{-5}$，$\lambda_{\mathrm{cal}}=0.01$，$\lambda_{\mathrm{inf}}=0.1$，$T=0.2$，$\tau_{\mathrm{rank}}=0.005$。自适应 Huber 尺度的比例系数统一设为 $\kappa_\delta = 0.15$，界限取 $[\delta_{\min}, \delta_{\max}] = [0.01, 0.5]$。

实验关键数据¶

主实验¶

实验在具有高维非线性变量交互的二次背包问题（QKP）、具有海量打包约束的组合拍卖（CA）以及层级工业级个性化细胞治疗供应链问题（CART）三大代表性基准上展开对比。评估指标包括平均原始最优差距（Primal Gap）、求解耗时、解落入最优 1% 范围内的比例（$\le 1\%$）以及硬约束可行率（Feasibility）。

方法	QKP Gap (%)	QKP Time (s)	QKP Feas. (%)	CART Gap (%)	CART Time (s)	CART Feas. (%)	CA Gap (%)	CA Time (s)	CA Feas. (%)
Full MIP (Gurobi)	0.00	525.21	100	0.00	3728.82	100	0.00	0.14	100
Predict+Search	1.13	0.12	99	22.02	251.79	83	29.81	0.01	100
Neural Diving	1.04	1.52	99	1.53	398.34	100	2.91	1.23	100
ConPaS	0.95	1.03	100	0.02	3404.19	100	0.90	0.26	100
Linear+MIP (BCE)	4.92	0.03	100	15.81	273.60	100	83.99	0.02	100
Linear+MIP (Contrastive)	58.55	0.03	100	24.18	410.04	100	30.82	0.02	100
EnerGNN (Linear)	26.87	0.28	100	21.80	391.36	100	0.20	0.31	100
EnerGNN (MLP)	0.31	3.56	100	0.05	214.03	100	0.53	8.62	100

消融实验¶

消融实验深入验证了损失函数组件、能量头架构尺寸以及测试期零样本约束注入对解质量与计算效率的具体影响。

1. 损失函数组件消融

配置	CART Gap (%)	CART $\le 1\%$ (%)	QKP Gap (%)	QKP $\le 1\%$ (%)	CA Gap (%)	CA $\le 1\%$ (%)
Full EnerGNN	0.05	100	0.31	99	0.53	77
w/o 校准损失 ($\mathcal{L}_{\mathrm{cal}}$)	0.78	70	0.88	68	7.69	4
w/o 不可行损失 ($\mathcal{L}_{\mathrm{inf}}$)	0.06	100	0.39	99	0.58	77

2. 零样本约束注入对比（CART 场景下随机停用核心选中设施）

方法	扰动类型	选中变量剔除比例 (%)	平均 Hamming 偏移	Primal Gap (%)	$\le 1\%$ 比例 (%)	可行率 (%)
EnerGNN	剔除 1 个设施	31.35	3.84	0.21	96.24	100
Neural Diving	剔除 1 个设施	31.35	3.84	2.99	40.44	89.66
ConPaS	剔除 1 个设施	31.35	3.84	0.30	87.15	100
EnerGNN	剔除 2 个设施	50.81	5.27	0.34	93.27	100
Neural Diving	剔除 2 个设施	50.81	5.27	4.38	25.06	72.85
ConPaS	剔除 2 个设施	50.81	5.27	0.70	77.96	99.77
EnerGNN	剔除 3 个设施	61.99	6.26	0.45	91.23	100
Neural Diving	剔除 3 个设施	61.99	6.26	4.32	20.18	49.12
ConPaS	剔除 3 个设施	61.99	6.26	1.08	69.88	98.28

关键发现¶

在具备强二次协同效益的 QKP 任务中，非线性 ReLU 头部展现出碾压性优势：带有 MLP 头部的 EnerGNN 取得了 0.31% 的平均差距，而退化为线性打分的 EnerGNN (Linear) 最优差距骤降至 26.87%，严格印证了理论分析中单变量打分无法表示非零成对协同项的局限性。
在 CART 工业供应链场景下，EnerGNN 通过准确拟合高层选址配置对下游复杂物流排程的边际价值函数，在保持 0.05% 超低最优差距的前提下，实现了相比 Gurobi 全量单体 MIP 高达 17.4 倍的端到端提速，相比 ConPaS 提速 15.9 倍。
零样本约束注入展现了无与伦比的鲁棒性：当外部环境强制剥离多达 3 个核心主力设施（剔除比例达 61.99%）时，Neural Diving 的解可行率断崖式跌落至 49.12%，而 EnerGNN 在完全不重新训练网络权重的前提下，直接由底层 MIP 施加硬约束求解，始终保持 100% 可行性且最优差距仅微升至 0.45%。
损失消融表明校准损失 $\mathcal{L}_{\mathrm{cal}}$ 是学习正确能量尺度的关键；若去掉该项，CA 上的最优差距从 0.53% 剧增至 7.69%。相反，不可行损失项 $\mathcal{L}_{\mathrm{inf}}$ 贡献相对微弱，证明了推断期硬约束由 MIP 求解器显式接管的解耦机制极为扎实。

亮点与洞察¶

偏好学习与硬约束求解的完全解耦：将神经网络的角色从“端到端黑盒生成解”重塑为“构造优化相容的目标函数景观”，显式物理约束完全留由成熟 MIP 求解器把关，彻底规避了神经网络在处理离散硬约束时频发的不可行性缺陷。
计算图前置与浅层 MIP 编译的高效折中：重型的 GNN 图特征提取全部在求解器外部离线完成且只执行一次，嵌入求解器分支定界树内的仅为单隐层紧凑 ReLU 映射，既维持了图级别的复杂上下文表征，又将在线推断新增的二值松弛变量严格控制在数十个量级。
即插即用的零样本约束注入范式：模型学到的是针对离散构型内在品质的通用评价面，面对突发的节点停机、容量缩水或业务排他新约束，无需耗时收集数据与微调网络，仅需在求解器模型中动态追加线性不等式即可实现近乎零损失的自适应调整。

局限与展望¶

能量表达能力与求解耗时的内在张力：嵌入求解器的能量头必须受限于分段线性结构（ReLU/LeakyReLU），消融实验显示加深或加宽能量头会导致 MIP 求解时间呈指数级攀升而收益微弱，限制了极端复杂交互函数的表示深度。
离线样本采集与标注成本的冷启动依赖：对比学习与能量校准高度依赖求解器在离线阶段生成的具有确定质量标注的候选构型，QKP 与 CART 分别需要约 125 与 130 个在线部署实例才能平摊前期的数据生成时间成本。
未来方向：探索分支定界过程中割平面生成技术与神经能量头结构的协同设计，以及向混合连续-整数决策（Mixed-Integer Continuous Decisions）层面的通用扩展。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙打通了表达型能量模型与混合整数线性规划的数学接口，解耦偏好学习与硬约束求解。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖直接决策、多层级调度、跨规模泛化与极端零样本约束扰动等多个维度，消融与理论证明严谨完备。
写作质量: ⭐⭐⭐⭐⭐ 数学建模推导严谨自洽，方法论与工程权衡论述透彻。
价值: ⭐⭐⭐⭐⭐ 为安全关键型与强约束运筹工业场景提供了一种高可靠、强泛化的新型神经组合优化范式。