A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention
This work addresses computational bottlenecks in combinatorial optimization for scientific and engineering applications, representing an incremental advance over existing neural methods.
The authors tackled the challenge of limited representation power in graph neural networks for mixed-integer linear programming by introducing a dual-attention neural architecture that enables global information exchange, resulting in consistent improvements over state-of-the-art baselines across various benchmarks.
Mixed-integer linear programming (MILP), a widely used modeling framework for combinatorial optimization, are central to many scientific and engineering applications, yet remains computationally challenging at scale. Recent advances in deep learning address this challenge by representing MILP instances as variable-constraint bipartite graphs and applying graph neural networks (GNNs) to extract latent structural patterns and enhance solver efficiency. However, this architecture is inherently limited by the local-oriented mechanism, leading to restricted representation power and hindering neural approaches for MILP. Here we present an attention-driven neural architecture that learns expressive representations beyond the pure graph view. A dual-attention mechanism is designed to perform parallel self- and cross-attention over variables and constraints, enabling global information exchange and deeper representation learning. We apply this general backbone to various downstream tasks at the instance level, element level, and solving state level. Extensive experiments across widely used benchmarks show consistent improvements of our approach over state-of-the-art baselines, highlighting attention-based neural architectures as a powerful foundation for learning-enhanced mixed-integer linear optimization.