DRAGON: 대규모 조합 최적화 문제 해결을 위한 LLM 기반 분해 및 재구성 에이전트

DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimization

최근 대규모 언어 모델(LLM)은 프롬프트 기반 전략을 통해 조합 최적화 문제(COP)를 해결하는 데 유망한 결과를 보여주었습니다. 그러나 이러한 모델의 확장성과 일반화 능력은 제한적이며, 특히 30개 이상의 노드를 포함하는 라우팅 문제와 같이 문제의 크기가 커질수록 효과가 감소합니다. 본 연구에서는 분해 및 재구성 에이전트 기반 최적화(Decomposition and Reconstruction Agents Guided OptimizatioN, DRAGON)라는 새로운 프레임워크를 제안합니다. DRAGON은 메타휴리스틱 설계와 LLM 추론의 장점을 결합합니다. 초기 전역 솔루션에서 시작하여, DRAGON은 높은 최적화 잠재력을 가진 영역을 자율적으로 식별하고, 대규모 COP를 관리 가능한 하위 문제로 전략적으로 분해합니다. 각 하위 문제는 간결하고 국소적인 최적화 문제로 재구성되어, 축적된 경험에 의해 안내되는 LLM 프롬프팅을 통해 해결됩니다. 마지막으로, 국지적으로 최적화된 솔루션은 원래의 전역 컨텍스트에 체계적으로 통합되어, 전반적으로 상당한 성능 향상을 달성합니다. DRAGON 에이전트는 최적화 환경과의 지속적인 상호 작용을 통해 적응형 경험 메모리를 활용하여 피드백으로부터 반복적으로 학습하며, 이를 통해 기호 추론과 휴리스틱 검색을 효과적으로 결합합니다. 실험 결과는 기존의 LLM 기반 솔버가 작은 규모의 문제에만 제한되는 것과 달리, DRAGON이 TSPLIB, CVRPLIB 및 Weibull-5k 컨테이너 적재 벤치마크에서 실행 가능한 솔루션을 지속적으로 제공하며, 3백만 개 이상의 변수를 가진 배낭 문제에서 거의 최적의 결과(0.16% 차이)를 달성한다는 것을 보여줍니다. 본 연구는 피드백 기반 언어 에이전트가 일반화 가능하고 해석 가능한 대규모 최적화의 새로운 패러다임을 제시할 수 있는 가능성을 보여줍니다.

Large Language Models (LLMs) have recently shown promise in addressing combinatorial optimization problems (COPs) through prompt-based strategies. However, their scalability and generalization remain limited, and their effectiveness diminishes as problem size increases, particularly in routing problems involving more than 30 nodes. We propose DRAGON, which stands for Decomposition and Reconstruction Agents Guided OptimizatioN, a novel framework that combines the strengths of metaheuristic design and LLM reasoning. Starting from an initial global solution, DRAGON autonomously identifies regions with high optimization potential and strategically decompose large-scale COPs into manageable subproblems. Each subproblem is then reformulated as a concise, localized optimization task and solved through targeted LLM prompting guided by accumulated experiences. Finally, the locally optimized solutions are systematically reintegrated into the original global context to yield a significantly improved overall outcome. By continuously interacting with the optimization environment and leveraging an adaptive experience memory, the agents iteratively learn from feedback, effectively coupling symbolic reasoning with heuristic search. Empirical results show that, unlike existing LLM-based solvers limited to small-scale instances, DRAGON consistently produces feasible solutions on TSPLIB, CVRPLIB, and Weibull-5k bin packing benchmarks, and achieves near-optimal results (0.16% gap) on knapsack problems with over 3M variables. This work shows the potential of feedback-driven language agents as a new paradigm for generalizable and interpretable large-scale optimization.