arXiv:2608.30103cs.LGcs.AI2026-08

用图神经网络学习双层优化的价值函数,可跨规模通用且性能接近现有方法。

Graph4BiLO: Graph Neural Network Approximation for Bilevel Mixed-Integer Linear Optimization

  • 基于变量-约束图的GNN学习双层优化值函数,共享参数实现跨问题规模泛化
  • 在20-100个物品的背包干扰问题上,目标值与Neur2BiLO相当
  • 支持零样本迁移,20项训练数据可直接用于40、60项未见问题

双层混合整数线性优化问题建模了领导者预判跟随者最优响应的层级决策过程。尽管表达能力强,但其计算复杂,因下层最优性嵌入上层可行域。价值函数重构将嵌套的下层优化替换为涉及下层最优值的约束,但精确评估该值函数本身代价高昂。本文提出Graph4BiLO,一种基于图神经网络(GNN)的方法,从变量-约束图表示中学习双层值函数。相较于固定长度多层感知机(MLP)表示,该GNN使用共享的消息传递参数,因此可通过单一训练模型应用于多种问题规模。学习得到的ReLU网络被精确编码为混合整数线性约束,并嵌入近似单层公式。随后通过修复步骤重新求解下层问题以恢复满足双层可行性的响应。我们在20–100项物品的背包干扰实例上,对比了精确的MibS求解器和基于学习的Neur2BiLO方法。Graph4BiLO在所有测试规模上均获得与Neur2BiLO相近的目标值,同时避免了针对特定规模的神经网络。额外的分布外实验表明,从20项训练实例到此前未见的40项和60项实例具有零样本迁移能力。然而,在每个图节点嵌入消息传递显著增加了最终混合整数公式的规模和求解时间。这些结果揭示了可泛化图表示与嵌入GNN带来的计算成本之间的核心权衡。

原文摘要 · Abstract (English)

Bilevel mixed-integer linear optimization problems model hierarchical decision processes in which a leader anticipates the optimal response of a follower. Although expressive, these problems are computationally challenging because lower-level optimality is embedded in the leader's feasible region. Value-function reformulations replace the nested follower optimization with a constraint involving the follower's optimal value, but evaluating this value function exactly can itself be expensive. This paper introduces Graph4BiLO, a graph neural network (GNN) approach for learning bilevel value functions from variable--constraint graph representations. In contrast to fixed-length multilayer perceptron (MLP) representations, the GNN uses shared message-passing parameters and can therefore be applied across multiple problem sizes with a single trained model. The learned ReLU network is encoded exactly as mixed-integer linear constraints and embedded in an approximate single-level formulation. A repair step subsequently re-solves the follower problem for the selected leader decision to recover a bilevel-feasible follower response. We evaluate Graph4BiLO on knapsack interdiction instances with 20--100 items against the exact MibS solver and the learning-based Neur2BiLO method. Graph4BiLO obtains objective values comparable to Neur2BiLO across all tested sizes while avoiding size-specific neural networks. An additional out-of-distribution experiment demonstrates zero-shot transfer from 20-item training instances to previously unseen 40- and 60-item instances. However, embedding message passing at every graph node substantially increases the resulting mixed-integer formulation size and solve time. These results identify a central tradeoff between size-generalizable graph representations and the computational cost of embedding GNNs within optimization models.

双层优化图神经网络混合整数规划可泛化学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。