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

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.

Many real-world decisions, such as scheduling tasks, allocating resources, and choosing plans, can be written as mathematical optimization problems. These models describe what we want to achieve and which choices are allowed, but finding the best solution becomes difficult when the number of choices and rules grows. Machine learning can provide useful guidance for difficult optimization problems. Existing methods often represent each problem as a graph of choices and rules: choices are the decisions to be made, and rules describe what these decisions must satisfy. These graph-based models mainly pass information along the direct links between choices and rules. As a result, two choices, or two rules, often need to communicate indirectly through several intermediate steps. This can make the model focus on nearby information and miss distant but important relationships. We propose a new neural network that gives the model a broader view of the optimization problem. It allows the model to gather information directly and in parallel among choices, among rules, and between choices and rules. This helps the model build a more complete representation of the problem.