LLM과 그래프 신경망 솔버를 결합하여 조합 최적화 문제를 해결하는 방법

Aligning LLMs with Graph Neural Solvers for Combinatorial Optimization

최근 연구에서는 대규모 언어 모델(LLM)이 자연어로 작업과 인스턴스를 표현하여 조합 최적화 문제(COP)를 해결하는 데 효과적임을 보여주었습니다. 그러나 순수 언어 기반 접근 방식은 많은 COP에 내재된 복잡한 관계 구조를 정확하게 파악하는 데 어려움을 겪으며, 이로 인해 중간 규모 이상의 인스턴스를 처리하는 데 효과가 떨어집니다. 이러한 한계를 극복하기 위해, 본 연구에서는 LLM을 그래프 신경망 솔버와 결합하여 보다 일반화된 신경망 기반 COP 휴리스틱을 학습하는 새로운 방법인 AlignOPT를 제안합니다. 특히, AlignOPT는 LLM의 의미 이해 능력을 활용하여 COP 및 해당 인스턴스의 텍스트 설명을 인코딩하고, 동시에 그래프 신경망 솔버를 활용하여 COP 인스턴스의 기본 그래프 구조를 명시적으로 모델링합니다. 본 연구의 접근 방식은 언어적 의미와 구조적 표현 간의 강력한 통합 및 정렬을 가능하게 하여, 보다 정확하고 확장 가능한 COP 솔루션을 제공합니다. 실험 결과는 AlignOPT가 다양한 COP에서 최첨단 성능을 달성하며, 의미적 및 구조적 표현을 결합하는 데 효과적임을 보여줍니다. 특히, AlignOPT는 강력한 일반화 능력을 보여주며, 이전에 보지 못한 COP 인스턴스로 효과적으로 확장됩니다.

Recent research has demonstrated the effectiveness of large language models (LLMs) in solving combinatorial optimization problems (COPs) by representing tasks and instances in natural language. However, purely language-based approaches struggle to accurately capture complex relational structures inherent in many COPs, rendering them less effective at addressing medium-sized or larger instances. To address these limitations, we propose AlignOPT, a novel approach that aligns LLMs with graph neural solvers to learn a more generalizable neural COP heuristic. Specifically, AlignOPT leverages the semantic understanding capabilities of LLMs to encode textual descriptions of COPs and their instances, while concurrently exploiting graph neural solvers to explicitly model the underlying graph structures of COP instances. Our approach facilitates a robust integration and alignment between linguistic semantics and structural representations, enabling more accurate and scalable COP solutions. Experimental results demonstrate that AlignOPT achieves state-of-the-art results across diverse COPs, underscoring its effectiveness in aligning semantic and structural representations. In particular, AlignOPT demonstrates strong generalization, effectively extending to previously unseen COP instances.