Benders decomposition and column generation solve large‑scale optimization problems by exchanging cuts, columns, and dual values between a master problem and subproblems, but they are notoriously hard to implement correctly. Large language models (LLMs) can now automate parts of algorithm design, suggesting the possibility of agents that automatically build decomposition solvers for new problems. To measure how well current coding agents handle these two algorithms, we introduce DecompGym, a benchmark containing 81 instances from nine problem families (five Benders, four column‑generation). For each instance an agent must produce a solver that satisfies three criteria: execution within a 60‑second time limit, numerical feasibility together with a method audit performed by an LLM judge that reads the code, and an objective value within 1 % of the stored optimum.
We evaluate 12 models from the GPT, Claude, and Gemini families using coding‑agent tools, allowing up to ten attempts per instance. Two retry strategies are compared: independent regeneration and reflection, where the latter first diagnoses the failure before regenerating code. On the first attempt, two models solve every instance and seven achieve over 90 % success. Most Benders failures (48 of 62) are missing or sub‑optimal solutions, while the dominant column‑generation failure is rejection by the method audit. Pure output checks would mistakenly accept 93 of the 108 attempts that actually fail the audit. The most frequent rejection, an “optimalif”, occurs 96 times, 92 of them in a single model. Reflection turns 66 % of retries into successes, compared with 39 % for plain regeneration, and it repairs audit failures because the judge pinpoints the defective gaps. Therefore, decomposition agents need checks on how a solver arrives at its answer and feedback that locates errors. The benchmark is available at https://github.com/SIKAI-C/DecompGym.
Review