DecompGym：对 LLM Agent 设计分解算法的基准测试

Benders 分解和列生成通过在主问题与子问题之间传递割、列和对偶值来求解大规模优化问题，但正确实现它们非常困难。如今，大语言模型已能自动完成算法设计的部分工作，这为构建能够针对新问题开发分解求解器的 Agent 指明了方向。作为迈向此类 Agent 的第一步，我们研究了当前编码 Agent 设计和实现这两种算法的能力，以及它们失败的方式。我们引入了 DecompGym，其中包含来自九个问题族的 81 个实例（五个 Benders 问题族、四个列生成问题族），要求 Agent 针对指定方法编写求解器。每个求解器必须满足三个标准：在 60 秒时限内执行完成；具备数值可行性，并通过方法审查，即由 LLM 评审员读取求解器代码；以及目标值与已存储最优目标值的差距不超过 1%。我们评估了在编码 Agent 工具中运行的 12 个 GPT、Claude 和 Gemini 模型。在最多十次尝试中，我们比较了独立重新生成与反思两种方式，后者会先诊断失败原因。在首次尝试中，有两个模型解决了所有实例，另有七个模型解决了超过 90% 的实例。在 Benders 失败案例中，大多数（62 个中的 48 个）是缺少解或解并非最优。列生成最常见的失败原因是方法审查被拒。仅进行输出检查会接受 108 次方法审查失败尝试中的 93 次。最常见的拒绝类型是 optimalif，共出现 96 次，其中 92 次来自同一个模型。反思能将 66% 的重试转化为成功，而重新生成的比例为 39%；对于方法审查失败，反思也能进行修复，因为评审员会指出缺陷所在。因此，分解算法 Agent 需要检查求解器如何得到答案，并提供能够定位错误的反馈。该基准测试已发布于 https://github.com/SIKAI-C/DecompGym。