DRAGON：面向大规模组合优化的LLM驱动分解与重构Agent

大语言模型（LLM）近来通过基于提示的策略在解决组合优化问题（COP）上展现出前景。然而，其可扩展性与泛化能力仍然有限，且效果随问题规模增大而下降，尤其是在涉及超过30个节点的路径类问题中。我们提出DRAGON，即Decomposition and Reconstruction Agents Guided OptimizatioN（引导优化的分解与重构Agent），一个结合元启发式设计与LLM推理优势的新框架。从初始全局解出发，DRAGON自主识别具有高优化潜力的区域，并策略性地将大规模COP分解为可管理的子问题。每个子问题随后被重新表述为简洁的局部优化任务，并在积累经验的引导下通过针对性LLM提示求解。最后，局部优化后的解被系统地重新整合到原始全局上下文中，从而得到显著改善的整体结果。通过与优化环境持续交互并利用自适应经验记忆，各Agent从反馈中迭代学习，有效耦合符号推理与启发式搜索。实证结果表明，与仅限于小规模实例的现有基于LLM的求解器不同，DRAGON在TSPLIB、CVRPLIB和Weibull-5k装箱基准上持续产出可行解，并在超过300万变量的背包问题上取得接近最优的结果（0.16%差距）。这项工作展示了反馈驱动的语言Agent作为可泛化、可解释的大规模优化新范式的潜力。