Benders 分解和列生成是通过在主问题和子问题之间传递割平面、列和对偶值来求解大规模优化问题的技术，但实现难度大。大型语言模型已经能够自动化算法设计的部分环节，这为构建能够为新问题生成分解求解器的智能体提供了可能。为评估当前编码型智能体在这两类算法上的设计与实现能力，我们推出了 DecompGym 基准，收录了来自九个问题族的 81 个实例（五个 Benders、四个列生成），要求智能体为每个实例编写一个满足以下三条标准的求解器：
- 在 60 秒内完成求解；
- 数值上可行，并通过 LLM 判官的“方法审计”，即判官阅读代码并给出评价；
- 求得的目标值与已知最优值的误差不超过 1%。
我们使用 12 种 GPT、Claude 和 Gemini 模型在编码智能体工具下进行实验，最多允许十次尝试，并比较两种重试策略：独立重新生成和带有反思的重试（先诊断失败原因再生成）。结果显示，首轮尝试时有两种模型能够全部解出实例，七种模型的成功率超过 90%。Benders 失败主要表现为缺失或次优解（62 次中有 48 次），列生成的主要失败是被方法审计拒绝。仅凭输出检查会错误接受 93 次实际未通过审计的尝试。最常见的审计拒绝是“optimalif”，共出现 96 次，其中 92 次来自同一模型。反思策略将重试成功率提升至 66%，而单纯重新生成仅为 39%，并且能够修复审计失败，因为判官会指出具体缺陷。由此可见，分解求解器的智能体需要对求解过程进行检查并获得定位错误的反馈。基准代码已在 https://github.com/SIKAI-C/DecompGym 发布。
点评