이중 어텐션을 이용한 혼합 정수 선형 최적화를 위한 범용 신경망 백본

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

조합 최적화를 위해 널리 사용되는 모델링 프레임워크인 혼합 정수 선형 계획법(MILP)은 많은 과학 및 공학 응용 분야의 핵심이지만, 규모가 커질수록 계산적으로 해결하기 어렵다는 문제가 있습니다. 최근 딥러닝의 발전은 MILP 인스턴스를 변수-제약 이분 그래프로 표현하고 그래프 신경망(GNN)을 적용하여 잠재적 구조 패턴을 추출하고 솔버 효율성을 높임으로써 이러한 문제에 대처하고 있습니다. 그러나 기존 아키텍처는 본질적으로 국소 지향적(local-oriented) 메커니즘에 의존하기 때문에 표현력이 제한되고 MILP에 대한 신경망 접근 방식의 발전을 저해합니다. 이에 본 논문에서는 단순한 그래프 관점을 넘어 풍부한 표현을 학습하는 어텐션 기반 신경망 아키텍처를 제안합니다. 설계된 이중 어텐션 메커니즘은 변수와 제약 조건에 대해 자기 어텐션(self-attention)과 교차 어텐션(cross-attention)을 병렬로 수행하여 전역적인 정보 교환과 심층적인 표현 학습을 가능하게 합니다. 우리는 이 범용 백본을 인스턴스 수준, 요소 수준, 풀이 상태 수준의 다양한 다운스트림 작업에 적용했습니다. 널리 사용되는 벤치마크에 대한 광범위한 실험 결과, 최신 베이스라인 모델 대비 일관된 성능 향상을 확인하였으며, 이는 어텐션 기반 신경망 아키텍처가 학습 기반 혼합 정수 선형 최적화를 위한 강력한 토대임을 시사합니다.

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.