用双注意力机制提升混合整数规划求解效率
A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention
- 以变量和约束为元素，通过双注意力并行建模
- 在三种任务上均超越传统图神经网络方法
- 适合需要高效求解组合优化的工程与科研场景
混合整数线性规划（MILP）是科学与工程中组合优化的基础框架，但因NP难问题难以大规模求解。现有基于学习的方法通常将MILP实例建模为变量-约束二分图，并使用图神经网络（GNN）进行表征学习，但其局部性限制了表达能力。本文提出一种以元素为中心的注意力驱动神经主干，通过双注意力机制实现变量与约束内部的自注意力以及跨类型交叉注意力。在实例级、元素级和求解状态级三类代表性任务中，该模型持续优于传统的基于GNN的架构，表明基于注意力的元素中心建模是增强组合优化学习的有效基础。
原文摘要 · Abstract (English)
Mixed-integer linear programming (MILP) is a foundational framework for combinatorial optimization across science and engineering, but remains hard to solve at scale due to NP-hardness. Recent learning-based methods typically model MILP instances as variable-constraint bipartite graphs and use Graph Neural Networks (GNNs) for representation learning, yet their locality limits representation power. We propose an attention-driven neural backbone that adopts an element-centric view of variables and constraints, with dual attention performing parallel intra-type self-attention and inter-type cross-attention. Across three representative tasks at the instance, element, and solving-state levels, our model consistently outperforms conventional GNN-based architectures, highlighting attention-based, element-centric modeling as a powerful foundation for learning-enhanced combinatorial optimization.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。