A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention

Peixin Huang, Yaoxin Wu, Yining Ma, Cathy Wu, Wen Song, Wei Zhang · 2026

Read A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention by Peixin Huang, Yaoxin Wu, Yining Ma, Cathy Wu, Wen Song, Wei Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-04509.txt.

Introduction

Peixin Huang and five co-authors give optimization solvers a new kind of neural backbone, in a 2026 arXiv paper. Mixed-integer linear programming is the standard language for hard planning and scheduling problems, but its NP-hardness makes big instances slow. learning-based helpers usually read a problem as a graph of variables and constraints, using graph neural networks whose local view limits what they can grasp.

The alternative proposed here is attention, organized around the elements themselves: variables and constraints each attend within their own kind, and cross-attend to the other kind, in parallel. Tested at three levels — judging whole instances, scoring individual elements, and reading the state of a solve in progress — the backbone consistently beat graph-network architectures. The authors present element-centric dual attention as a stronger foundation for learning-enhanced combinatorial optimization generally.

Catalog record

CREATORPeixin Huang, Yaoxin Wu, Yining Ma, Cathy Wu, Wen Song, Wei Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-04509

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A General Neural Backbone for Mixed-Integer Linear Optimization via Dual Attention Peixin Huang, Yaoxin Wu, Yining Ma, Cathy Wu, Wen Song, Wei Zhang Abstract 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. keywords General Combinatorial Optimization, Mixed-Integer Linear Programming, Deep Learning, Attention Mechanism † † equal-contributors: These authors contributed equally to this work. † † equal-contributors: These authors contributed equally to this work. 1 Introduction Combinatorial Optimization Problems (COPs) are ubiquitous in science and engineering 27 ; 45 ; 17 ; 40 ; 37 . However, a major computational bottleneck for COP solving is the well-known NP-hardness, making it very challenging to solve large-scale problems in practice. The recent surge of Neural Combinatorial Optimization (NCO) has become a promising direction to break through this scalability bottleneck 4 . Based on historical data, NCO methods leverage deep (reinforcement) learning to discover useful hidden patterns through offline learning, so as to achieve fast online solving and overcome the efficiency and optimality limitation of human-designed algorithmic framework or components. Among NCO studies, research on general COP models is of particular importance due to their wide applicability in modeling various problems and the availability of off-the-shelf solvers with robust performance and optimality guarantee. In this paper, we focus on Mixed-Integer Linear Programming (MILP), the workhorse of combinatorial optimization in practice 4 ; 31 . Though MILP does not cover the full spectrum of COP, it is general enough to model a large portion of scientific and engineering problems across various domains such as manufacturing 38 , logistics 57 , finance 2 , biology 42 , medicine 35 , and chemistry 36 . Due to its strong application value, MILP has been a long-standing pillar of mathematical optimization, with very active research communities and strong general-purpose solvers such as Gurobi, CPLEX, and SCIP 13 . While performance of these modern MILP solvers has been continuously improved during the past decades, efficiently solving large-scale practical problems remains extremely challenging due to the strong NP-hardness. Motivated by the recent success of NCO, deep learning has been applied in various ways to speed up MILP solvers 46 , such as learning primal heuristics to find high-quality feasible solution quickly 16 ; 39 ; 28 ; 24 ; 26 ; 33 ; 48 ; 54 ; 25 , learning branching heuristics to reduce search tree size 20 ; 22 ; 55 ; 23 ; 47 ; 56 ; 49 ; 18 , learning cutting plane control policies to speed up linear programming solving at each node 50 ; 53 ; 41 ; 32 ; 44 . While deep learning for MILP is thriving, research on the backbone neural architecture is surprisingly sparse, which is the key bottleneck in this emerging field. As the foundation of learning based MILP models, the backbone neural architecture is responsible for extracting high-level feature embeddings from raw instance data to facilitate downstream learning tasks. The mainstream and state-of-the-art approach is to model MILP instance as a variable-constraint bipartite graph, and apply Graph Neural Network (GNN) to extract variable and constraint embeddings through message passing and aggregation among neighboring nodes 20 ; 9 . This neural architecture encodes the structural information of MILP through local message passing and is naturally size-invariant, and is able to handle instances of varying scales. However, the above graph-based scheme has limited power in MILP representation, mainly due to its local-oriented mechanism. Specifically, in one layer of GNN, each node can only fuse information within its one-hop neighborhood, resulting in a very limited receptive field. Stacking multiple GNN layers cannot effectively alleviate this bottleneck because node embeddings quickly become indistinguishable due to GNN’s inherent over-smoothing and over-squashing issues 30 ; 51 . The consequence is that each node’s information source is within a small local range (normally within 4 hops in the bipartite graph), which significantly impairs the capability of graph-based architectures in capturing deeper representations and long-range dependencies that is crucial for efficiently solving general COPs. The limited expressive power of GNN in representing MILP has been noticed and theoretically studied in several works 12 ; 11 ; 10 . However, they are still under the local-oriented framework of GNN, and essentially cannot overcome this limitation. Figure 1 : Overview of the proposed attention-driven architecture. This paper addresses the fundamental challenge of designing a more powerful backbone representation learning architecture for MILP, the most widely adopted modeling framework for COPs in practice. Different from existing works, we propose to view an MILP instance as two types of heterogeneous elements, i.e., variables and constraints. Then, we design a novel neural architecture to extract element embeddings through a dual-attention mechanism, as illustrated in Fig. 1 . The first aspect is to analyze the intra-type relationships through full self-attention, enabling each node to directly access information from any other node of the same type. The second aspect is to capture inter-type relationships through bidirectional cross-attention, so as to exploit variable-constraint dependencies inherent in the MILP instance’s structure. With this design, each element can globally establish direct and adaptive connections with long-range ones, significantly enhancing its receptive field. Moreover, more layers can be stacked to enhance the quality of generated embeddings, thereby overcoming limitations of existing graph-based architectures. Through this paradigm, we aim to establish a new foundation for deep learning-based general combinatorial optimization solving. Our architecture serves as a general backbone that can be readily applied to diverse MILP learning tasks, including instance-level prediction (e.g., feasibility and optimal objective), element-level prediction (e.g., optimal solution), and solving state-level prediction (e.g., branching policy). Extensive experiments on problems from various domains demonstrate that the proposed attention-based architecture exhibits substantially stronger expressive power than existing GNN counterparts, suggesting that attention-driven representations may constitute a new paradigm for learning to solve general COPs. 2 Preliminaries Mixed-Integer Linear Programming (MILP). A general MILP with n variables and m constraints can be formally defined as \min\mathbf{c}^{\top}\mathbf{x},\quad\text{s.t.}\quad\mathbf{Ax}\leq\mathbf{b},\quad\mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\quad\mathbf{x}\in\mathbb{Z}^{q}\times\mathbb{R}^{n-p}, (1) where \mathbf{x} is a vector of n decision variables, with q of them being integer variables and the rest n-q variables being continuous. \mathbf{c}\in R^{n} represents the coefficient of each variable in the objective function. \mathbf{A}\in\mathbb{R}^{m\times n} is the coefficient matrix of the m constraints, and b\in\mathbb{R}^{m} is the corresponding right-hand side values. \mathbf{l}\in(\mathbb{R}\cup\{-\infty\})^{n} and \mathbf{u}\in(\mathbb{R}\cup\{+\infty\})^{n} denote the upper and lower bound for each variable, respectively.

Read the complete text