重塑优化建模与算法设计：2025年大模型（LLM）在优化领域的应用盘点 - 1

ICML 2025

• 问题：现有采用大语言模型（LLM）自动设计启发式算法的方法，普遍依赖于“种群进化”策略。这种策略只保留当前最优的一批解，会过早地淘汰掉那些“暂时表现不佳但有潜力”的解，导致算法很容易陷入局部最优，无法对复杂的算法空间进行全面探索。
• 方法：提出了一个名为MCTS-AHD 的新方法，其核心思想是用 蒙特卡洛树搜索（MCTS） 来取代传统的种群进化机制：
  • 用“树”代替“种群”：该方法不再维护一个固定大小的最优种群，而是构建一棵树来保存和组织所有生成过的启发式函数。 这意味着即使是性能暂时较差的函数（节点）也会被保留在树中，拥有被再次访问和优化的机会。
  • MCTS 指导探索：利用 MCTS 算法的选择（Selection）和扩展（Expansion）机制来智能地决定下一步要优化哪个函数。 MCTS能够平衡对当前最优解的“利用”和对潜力解的“探索”，从而更全面地探索整个算法空间，有效避免陷入局部最优。
  • 树路径推理（Tree-path Reasoning）：设计了一种新颖的、专门针对树结构的推理动作（Action s1）。 该动作让 LLM 分析从根节点到叶子节点的整条路径上的函数演变历史，从而启发 LLM 综合这些历史经验，生成一个更好的新函数。
  • 动态探索衰减（Exploration-Decay）：在搜索初期设置较高的探索率，鼓励算法大胆尝试不同的方向；随着搜索的进行，逐渐降低探索率，使算法最终能稳定收敛到高质量的解。
• 效果：在旅行商问题（TSP）等多个复杂优化任务中，设计出的启发式算法在质量上显著超越了现有的人工及其他自动设计方法 ，甚至在部分大规模问题上优于专门的深度学习模型 ，并能有效避免陷入局部最优 。

arXiv

• 问题：传统的计算方法（如元启发式算法、图神经网络GNN）在解决图结构的组合优化问题（如影响力最大化、网络拆解）时，面临着计算成本高、扩展性差或性能不佳的挑战 。直接使用大语言模型（LLM）处理文本描述的图结构，效果也同样不理想 。
• 方法：改变了图数据的表示方式。作者没有将图结构转换成矩阵或文本，而是将其“可视化”为一张图片，然后利用多模态大语言模型（MLLM）强大的空间和视觉推理能力来直接“观察”这张图，从而识别出关键节点 。这个过程模拟了人类通过观察图形来解决复杂问题的直觉能力，并且该方法还结合了一个简单的局部搜索算法来对MLLM给出的初始结果进行优化 。
• 效果：在影响力最大化和网络拆解等任务上，该方法（尤其是结合局部搜索后）的效果稳定地优于多种传统基准方法，甚至超越了先进的GNN模型。

arXiv

• 问题：大型语言模型（LLMs）是否可以作为一种可靠的进化优化器，来处理网络结构的组合优化问题？特别是，它们能否在迭代过程中始终生成遵守问题约束的有效解？
• 方法：提出了一种创新的“种群级（population-level）”优化策略，即将整个解种群在单次请求中输入给LLM进行交叉和变异等操作，而不是传统地逐个或逐对处理。 同时，他们设计了一个系统的错误检测与修复框架，能够自动识别并修正LLM生成的无效解，从而保障整个优化过程的稳健性。
• 效果：该方法在使用先进模型（如GPT-4）时，其优化效果（适应度）几乎能与传统代码实现的优化器相媲美 ，同时其“种群级”策略相比于“个体级”LLM方法，显著降低了计算开销。

arXiv

• 问题：大型语言模型（LLM）能否理解一个由领域专家编写的、已存在的复杂优化算法，并提出连专家本人都未曾想到的、能够实质性提升算法性能的改进方案？
• 方法：将一个名为CMSA的复杂优化算法的完整C++源代码直接提供给GPT-4o，并要求其提出改进。核心创新在于，LLM通过理解代码上下文，提出了一个全新的启发式（heuristic）策略：它将算法框架中一个已存在但未被专家在启发式部分使用的“age”（年龄）参数，与原有策略相结合，创造了一种全新的、基于“年龄”和“度”的加权选择机制来构建解。
• 效果：在解决最大独立集（MIS）问题时，由LLM提出的新算法版本，在解的质量上显著优于专家设计的原始版本，尤其是在图的规模和密度增大时，其优势愈发明显

arXiv

• 问题：设计用于解决组合优化问题（COPs）的高效启发式算法（heuristics）极其困难，不仅需要大量的领域知识，还非常耗时 。现有基于大语言模型（LLM）的自动化方法，在探索巨大且复杂的启发式算法空间时，缺乏有效的策略指导和前瞻性 。
• 方法：提出了一个名为“启发式规划”（Planning of Heuristics, PoH）的框架 。其核心思想是将“自动设计启发式算法”这一过程，从传统的直接迭代或进化，重新定义为一个战略规划问题 。具体来说，它将每个启发式算法视为一个“状态（state）”，将LLM生成的“改进建议”视为一个“行动（action）” ，并利用蒙特卡洛树搜索（MCTS） 算法来智能地探索由这些状态和行动构成的巨大搜索树 。通过MCTS，系统可以前瞻性地模拟不同改进路径的未来收益（rewards），从而战略性地引导搜索方向，高效地发现更优的算法 。
• 效果：在旅行商问题（TSP）和流水车间调度问题（FSSP）等基准测试上，该方法在求解质量上（如最优间隙）显著优于现有的人工设计启发式算法和其他基于LLM的自动化方法，尤其是在大规模问题上达到了SOTA水平 。

arXiv

• 问题：大型语言模型（LLMs）在解决复杂的图组合优化（GCO）问题时，由于缺乏严谨的结构化推理能力，容易产生错误的推理步骤（幻觉），导致其表现远不如传统求解器。
• 方法：提出了一个名为 GraphThought 的框架 ，其核心思想是为大语言模型（LLM）生成高质量、结构化的“思考链”（reasoning thoughts）作为微调数据。 该框架通过两种方式生成这些思考链：
  • 前向生成： 对于多项式时间可解的简单问题，通过分解经典启发式算法来提取推理步骤。
  • 后向生成： 对于NP-hard等复杂问题，先用传统求解器得到最优解，然后反向推导出通往该解的理想推理路径。
• 效果：基于该方法微调后的80亿参数模型Llama-GT，在GraphArena基准测试中取得了当前最优性能，效果显著超越了更大规模的语言模型（如DeepSeek-V3），并在部分任务上接近商业求解器Gurobi的水平。

arXiv

• 问题：如何自动、可靠地判断两个看起来不同（例如，变量名不同、约束顺序不同、或经过了数学变换）的优化问题数学模型，实际上是等价的？ 现有的自动化方法依赖简单的启发式规则，并不可靠。
• 方法：
  • 定义新标准： 提出了一种名为“准卡普等价”（Quasi-Karp Equivalence）的形式化定义。其核心思想是：如果能找到一个函数，将一个模型的最优解映射（转换）成另一个模型的最优解，那么这两个模型就是等价的。
  • 利用大语言模型（LLM）发现映射： 设计了一个名为 EquivaMap 的框架，利用大语言模型（LLM）来自动寻找这个关键的变量映射函数。
  • 轻量级验证： 在找到映射后，通过一个无需额外调用求解器的验证步骤，来确认映射后的解在新模型中是否依然可行且最优，从而保证判断的准确性。
• 效果：EquivaMap 在判断各种等价变换（如变量重缩放、添加有效不等式等）的准确率上达到了100%，显著优于现有基准方法（在这些变换下准确率为0%）。

arXiv

• 问题：现实世界中的车辆路径问题（VRP）存在大量复杂的约束条件，为每一种问题变体手动设计高效的求解器耗时耗力且需要大量专业知识。
• 方法：提出了一个名为 ARS（Automatic Routing Solver）的框架。其核心思想是，利用大语言模型（LLM）的编程能力，将用自然语言描述的VRP问题约束，自动生成为可执行的“约束感知启发式”代码。 该代码随后被集成到一个通用的启发式算法框架（包含“破坏与修复”及“局部搜索”等操作）中，从而使这个通用框架能够求解各种带复杂约束的VRP变体，无需手动为每个变体编写和调整算法。
• 效果：在解决常见VRP问题时，ARS的成功率超过90%，在一个包含1000个复杂变种的新基准测试RoutBench上成功率超过60%，其成功率比其他七种基于LLM的方法高出至少30%。

arXiv

• 问题：大型语言模型（LLM）虽然强大，但在将复杂的、用自然语言描述的“优化”与“满足”类问题，自动、准确地转换成特定编程模型（如MiniZinc）可执行代码方面，依然存在巨大鸿沟。
• 方法：构建并推出了一个名为 TEXT2ZINC 的基准数据集。其核心创新在于：首次将“优化”和“满足”这两类问题统一收录，并提供从自然语言描述到独立于求解器（solver-agnostic）的 MiniZinc 标准化代码模型的完整对应。该数据集旨在为训练和评测语言模型解决此类问题的能力，提供一个统一的“靶场”。
• 效果：在该数据集上对 GPT-4 进行基准测试，结果表明，即便是采用“思维链”等高级提示策略，模型生成的代码最高也仅有约 60% 的执行正确率和 25% 的求解正确率，证明了当前的大语言模型距离可靠地自动化建模还有很长的路要走。

ICLR 2025

• 问题：当前对大语言模型（LLM）的评测存在局限，如依赖缺乏真实世界多样性的合成数据 、任务过于简单 ，以及评估方法无法区分模型是真正理解还是在“蒙”答案 。因此，学术界缺乏一个能够严格、真实地评估大语言模型在复杂图计算问题上推理能力的基准。
• 方法：为此构建了一个名为 GraphArena 的新评测基准 。其核心创新在于三点：
  • 真实数据： 所有评测问题均基于从真实世界（如学术网络 DBLP、知识图谱 DBpedia 等）采样并保留了原始拓扑结构的图，而非人工合成的简单图 。
  • 复杂任务： 包含4种多项式时间问题和6种更具挑战性的 NP-完全问题（如旅行商问题），以考察模型更高阶的推理能力，如算法规划和策略选择 。
  • 严格评估： 提出了一种“基于路径”的评估框架，要求模型输出完整的解题路径，而不仅仅是最终答案。通过检查路径的可行性和最优性，将结果精确地分类为正确、次优、幻觉或缺失，从而更深入地分析模型的失败模式 。
• 效果：通过对十多个主流大语言模型的测试发现 ，即使是顶尖模型（如 GPT-4o 和 Claude-3.5-Sonnet）在处理更大、更复杂的图问题时也表现挣扎，且频繁出现“幻觉”（即生成格式正确但不可行的答案）。

2024年大模型（LLM）在优化领域的应用盘点见：
https://zhuanlan.zhihu.com/p/1930614603429183884
https://zhuanlan.zhihu.com/p/1930301683642119468