Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2026

Abstract

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. DRAGON autonomously identifies regions in initial solution 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 global context to yield a significantly improved outcome. By continuously interacting with the optimization environment and experience memory, the agents iteratively learn from feedback, effectively coupling symbolic reasoning with heuristic search. Empirical results show that, 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.

Keywords

Agentic AI, Combinatorial Optimization, Metaheuristics

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Sustainability

Publication

AAMAS 2026: Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems, Paphos, Cyprus, May 25-29

First Page

2809

Last Page

2817

ISBN

9798400723179

Identifier

10.65109/SBAY6258

Publisher

ACM

City or Country

New York

Additional URL

https://doi.org/10.65109/SBAY6258

Download

Share

COinS