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

📄 arXiv: 2608.30103v1 📥 PDF

作者: Jessica D. Elrefaei, Kaixun Hua, Seungbae Kim, Hoang Nam Tran, Juan S. Borrero

分类: cs.LG, cs.AI

发布日期: 2026-08-31

备注: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

💡 一句话要点

提出Graph4BiLO以解决双层混合整数线性优化问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 双层优化 图神经网络 混合整数线性优化 价值函数学习 资源分配

📋 核心要点

  1. 双层混合整数线性优化问题计算复杂，现有方法在评估下层最优值时成本高昂。
  2. 提出Graph4BiLO，通过图神经网络学习双层价值函数，使用共享参数适应不同问题规模。
  3. 实验结果显示，Graph4BiLO在多个实例上与Neur2BiLO相当，同时避免了特定规模的神经网络设计。

📝 摘要（中文）

双层混合整数线性优化问题建模了领导者预期跟随者最佳响应的层级决策过程。尽管表达能力强，但由于下层最优性嵌入领导者的可行区域，这些问题计算上具有挑战性。本文提出Graph4BiLO，一种基于图神经网络（GNN）的方法，通过变量-约束图表示学习双层价值函数。与固定长度的多层感知机（MLP）表示不同，GNN使用共享的消息传递参数，因此可以在多个问题规模上应用单一训练模型。所学习的ReLU网络被精确编码为混合整数线性约束，并嵌入近似的单层公式中。随后，修复步骤重新解决跟随者问题，以恢复双层可行的跟随者响应。实验表明，Graph4BiLO在20-100个物品的背包干预实例上，与精确的MibS求解器和基于学习的Neur2BiLO方法相比，获得了相当的目标值。

🔬 方法详解

问题定义：本文聚焦于双层混合整数线性优化问题，现有方法在处理下层最优性时计算成本高，难以有效求解。

核心思路：Graph4BiLO通过图神经网络（GNN）学习双层价值函数，利用变量-约束图表示，避免了固定长度多层感知机的局限性，能够适应不同规模的问题。

技术框架：整体架构包括图神经网络模块用于学习价值函数，混合整数线性约束的编码，以及后续的修复步骤以确保跟随者响应的双层可行性。

关键创新：最重要的创新在于使用共享消息传递参数的GNN，使得单一模型可以在不同问题规模上有效应用，显著提高了模型的通用性。

关键设计：设计中采用了ReLU网络结构，损失函数通过优化双层价值函数的近似来定义，确保了模型在训练过程中的有效性和准确性。具体的参数设置和网络结构细节在实验部分进行了详细描述。

🖼️ 关键图片

img_0
img_1
img_2

📊 实验亮点

实验结果表明，Graph4BiLO在20-100个物品的背包干预实例上，获得的目标值与Neur2BiLO相当，且避免了针对特定规模的神经网络设计。此外，在零样本转移实验中，从20个物品的训练实例成功迁移到未见过的40和60个物品实例，展示了良好的模型泛化能力。

🎯 应用场景

该研究在优化领域具有广泛的应用潜力，尤其是在资源分配、供应链管理和决策支持系统中。通过提高双层优化问题的求解效率，Graph4BiLO可以帮助决策者在复杂环境中做出更优选择，未来可能推动智能决策系统的发展。

📄 摘要（原文）

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.