- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies the automated design of decomposition strategies for large-scale mixed-integer linear programs. Classical decomposition relies on expert-crafted, problem-specific schemes, while generic automatic approaches use only the algebraic structure of the constraint matrix. The authors propose DecompPilot, an LLM-agent framework that draws on variable and constraint semantics to propose, implement, and refine model-level decompositions. They treat decomposition design as a long-horizon experimental search problem and introduce two mechanisms. A Trial Memory Tree records successful and failed solver trials to support refinement and backtracking within an instance. Decomposition Operator Induction abstracts recurring patterns from seed instances into reusable operators, which are frozen before held-out evaluation. All solutions are verified for strict feasibility against the original formulation. Experiments on unit-commitment benchmarks, including million-scale instances, and on bin packing show that the induced operators transfer to unseen instances. They yield feasible solutions on most held-out instances, with objective values close to a time-limited commercial solver and generally lower end-to-end runtime.
Critical strengths
- The paper is clearly written and well organized, which makes a complex multi-agent pipeline easy to follow.
- The figures are well designed and effectively illustrate the decomposition workflow, the Trial Memory Tree, and the operator induction process.
- The work is well motivated, addressing the practically relevant problem of reducing the expert effort required to design decomposition strategies for large-scale MILPs.
- The paper is transparent about its experimental protocol, providing detailed appendices on data splits, timing semantics, and per-instance results.
- The authors candidly discuss negative evidence and limitations, which is appreciated and helps contextualize the results.
Critical weaknesses
1. Inadequate baselines. The evaluation lacks domain-standard decomposition heuristics, so it cannot show whether simple, well-known schemes would perform comparably. The induced operators closely resemble textbook methods: rolling horizon for CA, generator-wise Dantzig–Wolfe for FERC and PEGASE, and Gilmore–Gomory pattern generation for bin packing. Yet none of these, nor Lagrangian relaxation or relax-and-fix, is evaluated as an expert-configured baseline. The only such baseline, Canonical CG, is effectively absent on all three unit-commitment suites, because the authors acknowledge its mapping to the original MILP did not pass the equivalence check. On bin packing, where it does run, the large runtime gap to DecompPilot is not explained even though both share the same pattern-based structure. The baselines also do not use the integer recovery and original-MILP polishing stages that DecompPilot relies on, so the comparison conflates decomposition design with post-processing. Finally, GCG-Auto is an exact branch-and-price method and is not a natural comparator for a heuristic pipeline. Comparisons with recent LLM-based decomposition methods cited in the related work, such as LLM-LNS and DRAGON, are also missing.
2. Missing ablations of the core components. The paper offers no evidence that its two central mechanisms are necessary. The only experiment labeled an ablation concerns a stopping rule within the FERC operator. There is no comparison of the Trial Memory Tree against linear refinement or against discarding failed trials, and no comparison of Operator Induction against directly reusing the best seed strategy. Most importantly, there is no one-shot baseline in which an LLM is simply prompted with the model description and the operator library, so it remains unclear whether a single prompt would already yield a comparable operator. The contributions of the Verifier and Exploration agents, of semantic descriptions, and of the operator priors are likewise untested. The trial-tree case studies are anecdotal, and the memory-guided search in Figure 5 arguably weakens the case for memory, since all inherited proposals were rejected and the successful candidates were reconstructed from the current instance. The authors also acknowledge that agents sometimes repeat similar refinements, which is the very failure mode the tree is meant to prevent.
3. Overstated discovery and unclear attribution of performance. The paper describes its operators as discovered, but they largely reinstantiate the three primitives supplied in the operator library: rolling horizon, DW/CG, and ADMM-style coordination. The search therefore appears to operate within a small, expert-designed space and to tune parameters such as block count, history depth, and fixing rules, rather than to discover new algorithmic structure. Moreover, a substantial share of the final solution quality appears to come from the commercial solver itself. The PEGASE operator spends about 600 seconds polishing the original MILP from a MIP start, which accounts for the large majority of its key solve time, and the FERC operator likewise ends with an original-MILP polish. Without an experiment that applies the same polish budget starting from a simple warm start, it is difficult to attribute the observed solution quality to the decomposition rather than to the final Gurobi solve.
4. Limited informativeness of the “Time” metric. Although the paper reports end-to-end wall time alongside key solve time, the latter is of limited value as a basis for comparison. For DecompPilot, key solve time is computed from the column generation critical path, which assumes perfectly parallel pricing, whereas for the monolithic solvers it is simply the actual solver runtime. These quantities are not directly comparable, particularly when the baseline solver’s thread budget is not matched (for FERC, the Gurobi reference is reported as single-threaded). The idealized critical path also does not appear to reflect actual execution: the frozen FERC operator uses a single pricing worker, and for PEGASE the recorded CG work wall time is substantially larger than the reported critical path. I would suggest either removing this column from the main comparison or reporting it under matched parallel resources, so that the claimed speedups rest on the wall-time measurements.
Questions for authors
See the Weaknesses
7 comments
Table P1. Main classical and LLM-based baseline comparison.
| Method | CA | CA | FERC | FERC | PEGASE | PEGASE | BinPacking | BinPacking |
|---|---|---|---|---|---|---|---|---|
| Δref (%) ↓ (Strict/total ↑) | TTT (s) ↓ (Hits/total ↑) | Δref (%) ↓ (Strict/total ↑) | TTT (s) ↓ (Hits/total ↑) | Δref (%) ↓ (Strict/total ↑) | TTT (s) ↓ (Hits/total ↑) | Δref (%) ↓ (Strict/total ↑) | TTT (s) ↓ (Hits/total ↑) | |
| Gurobi (threads=8) | +0.000 (5/5) | 49.14 (5/5) | +0.000 (9/9) | 114.56 (9/9) | +0.000 (73/73) | 294.89 (73/73) | +0.000 (5/5) | 904.32 (2/5) |
| DecompPilot | +0.316 (5/5) | 96.37 (5/5) | +0.246 (9/9) | 60.89 (9/9) | +0.317 (73/73) | 473.02 (73/73) | -0.884 (5/5) | 49.71 (5/5) |
| Rolling horizon | +0.004 (5/5) | 58.45 (5/5) | — | — | — | — | — | — |
| Relax-and-fix | +0.005 (5/5) | 96.06 (5/5) | +0.042 (9/9) | 569.46 (9/9) | +0.196 (72/73) | 1907.56 (72/73) | — | — |
| Generator-wise DW/CG | — | — | +1.750 (9/9) | 940.46 (2/9) | +0.372 (73/73) | 1312.21 (73/73) | — | — |
| Grouped DW/CG | — | — | +2.463 (9/9) | 899.83 (4/9) | +0.386 (73/73) | 1343.53 (73/73) | — | — |
| Gilmore–Gomory CG | — | — | — | — | — | — | -0.783 (5/5) | 113.38 (5/5) |
| LLM-LNS | +1.187 (5/5) | 228.85 (3/5) | +13.391 (9/9) | 116.70 (7/9) | +52.837 (56/73) | 304.92 (34/73) | -0.294 (5/5) | 43.68 (4/5) |
| DRAGON | — | — | — | — | — | — | +0.002 (5/5) | 108.21 (2/5) |
Results. On FERC, DecompPilot and Gurobi both attain 9/9 targets in mean recorded times of 60.89 and 114.56 s, a 46.8% reduction; DecompPilot is faster on all nine cases. On BinPacking, DecompPilot and tuned Gilmore–Gomory CG both attain 5/5 targets, with means of 49.71 and 113.38 s, a 56.2% reduction. These are the fastest non-ablation comparators with matching full target coverage on the respective datasets. DecompPilot also improves one final BinPacking objective and ties the other four. Gurobi reaches only 2/5 BinPacking targets; on those two common-hit instances, its mean is 904.32 s versus 38.13 s for DecompPilot, a 95.8% reduction. This two-instance comparison is reported separately from the full-coverage comparison. Conversely, DecompPilot takes 96.1% longer than Gurobi on CA and 60.4% longer on PEGASE, where both methods attain all targets. Worst DecompPilot reference differences are +0.429%, +1.017%, +0.740%, and −0.493% for CA, FERC, PEGASE, and BinPacking, respectively.
Revised conclusion. The frozen procedures return strictly feasible solutions and reach the declared targets on 92/92 Test instances. Relative to the fastest compared non-ablation baseline with matching full target coverage, mean recorded TTT is lower by 46.8% on FERC and 56.2% on BinPacking. These results support the ability of the framework to discover reusable decomposition operators and faster solution procedures on some problem families. We report dataset-specific outcomes, with complete data-level and instance-level objective–wall trajectories in Appendix P.
R2. Trial Memory Tree, induction, and other component ablations.
Response to W2 (stopping-policy limitation, one-shot generation, linear refinement, failure memory, best-Seed reuse, and agent/semantic/prior controls).
Response. We agree that the stopping-rule experiment alone does not test the proposed agent mechanisms. We have added separate single-instance memory and cross-instance operator-reuse comparisons, as shown below and in Appendix M.
Table P2a. Single-instance ablations: objective and original-row CVR.
| Variant | CA09 Obj. ↓ (CVR % ↓) | CA06 Obj. ↓ (CVR % ↓) | CA03 Obj. ↓ (CVR % ↓) | BP07 Obj. ↓ (CVR % ↓) | BP12 Obj. ↓ (CVR % ↓) | Saved strict outputs ↑ |
|---|---|---|---|---|---|---|
| A: One-shot LLM | — (NR) | 41728.83† (0.467836→0) | — (AD) | 205 (0) | 199 (0) | 3/5 |
| A-K: Best-of-K Independent Proposals | 48331.92 (0) | — (AD) | — (AD) | 204 (0) | 199 (0) | 3/5 |
| B: Memory-free Iterative Agent | — (AD) | — (AD) | — (0.012644→0‡) | 204 (0) | 199 (0) | 2/5 |
| C: Linear Refinement | — (NR) | — (NR) | — (AD) | — (NR) | — (NR) | 0/5 |
| D: Flat Trial Archive | — (NR) | — (NR) | — (AD) | 206 (0) | 199† (0) | 2/5 |
| E: No Failure Memory | — (NR) | — (AD) | — (NR) | 204 (0) | 199 (0) | 2/5 |
| F: Full Trial Memory Tree | 48298.65 (0) | 41717.64 (0) | 31806.43 (0) | — (NR) | 199 (0) | 4/5 |
The single-instance table matches the appendix: CA09/06/03 are the three CA Seeds, and BP07/12 are u500_07/12, two BinPacking Seeds. CVR is the percentage of original linear rows with violation above 10⁻⁶. NR means no saved row evaluation; AD means only ADMM residuals, not measured original-row CVR. An arrow shows pre/post repair. † marks numerical strict outputs from interrupted runs with incomplete trial eligibility; they count as saved strict outputs, not completed discovery successes. ‡ is a repaired diagnostic without an independent Strict Check and is not counted as a solution.
The clearest differences arise on the three CA instances. The full Trial Memory Tree obtains strictly feasible solutions on all three, whereas the memory-free, linear-refinement, flat-archive, and no-failure-memory variants obtain none. Independent sampling also leaves no saved strictly feasible solution on CA06 and CA03 despite seven and nine candidate opportunities, respectively; the full method succeeds on both. These results suggest that generating additional candidates or retaining only part of the search history does not reliably replace the structured use of previous trials and feedback on these cases.
Table P2b. Cross-instance induction ablation; definitions match P1.
| Method | CA Δref (%) ↓ (strict/total ↑) | FERC Δref (%) ↓ (strict/total ↑) | PEGASE Δref (%) ↓ (strict/total ↑) | BinPacking Δref (%) ↓ (strict/total ↑) |
|---|---|---|---|---|
| Single-instance operator reuse (G) | — (0/5) | +0.234 (9/9) | +0.064 (66/73) | −0.884 (5/5) |
| DecompPilot | +0.316 (5/5) | +0.246 (9/9) | +0.317 (73/73) | −0.884 (5/5) |
Response labels. R1, R2, ... number our response topics within each reviewer. W and Q retain the reviewer's original weakness and question numbers. Paragraph numbers count the body paragraphs after each weakness heading; the heading itself is excluded. Each response identifies the original comments it addresses, and closely related requests are answered together.
We thank the reviewer for the detailed and constructive assessment, and for the positive comments on the presentation. We have added classical and LLM-based baselines, expanded the ablations, and clarified the timing protocol and the scope of operator discovery. Related comments are grouped into the seven responses below.
R1. Classical and LLM-based baselines under revised evaluation.
Response. Thank you for identifying the missing comparisons. We agree that domain-standard and LLM-based baselines are both important here. We have added validated classical pipelines—rolling horizon, relax-and-fix, generator-wise/grouped DW/CG with integer recovery and bounded polish, and strong-initialization Gilmore–Gomory CG—together with LLM-LNS [1] and DRAGON [2]. Unvalidated UC Canonical CG remains a mapping diagnostic, and GCG-Auto remains contextual exact branch-and-price evidence rather than the principal heuristic comparator.
We now evaluate the main comparison under an eight-logical-CPU ceiling, using eight-thread serial solves or concurrent subproblem solves whose thread budgets sum to at most eight (e.g., 8×1 or 4×2).
FERC update relative to the original submission. The weaker objective–wall convergence on FERC motivated a more informative discovery objective. A reference runtime based only on Gurobi's termination time does not show the agents how quickly it reaches a useful solution. We therefore used the saved Gurobi (threads=8) trajectory up to 3600 s to provide quality-matched feedback: for a candidate's final objective, the reference time is the first saved strictly feasible Gurobi event attaining an equal or better objective. This guided DecompPilot’s search toward a more effective LP-quota generator-group operator. The operator constructs integer decisions through local MILPs, recovers global dispatch through a continuous LP, and invokes a predefined four-group fallback when the initial eight-group stage fails.
The current campaign uses a newly sampled 40%/20%/40% discovery/Validation/Test partition, realized as 10/5/9 instances. The Orchestrator selects two Seeds from the discovery pool; the remaining eight discovery instances do not enter Validation or Test. The instance set remains fixed within a campaign, although a new campaign can sample a different set. We now evaluate the frozen operator and all baselines on the nine FERC Test cases. The details of the discovered operator and data roles are described in Appendices G and R.
Table P1 below (Table 3 in the revised manuscript) presents the updated main comparison. The revised agent-search objective uses the saved Gurobi (threads=8) 3600-s trajectories as the reference goal in the system prompt. The additional baseline and ablation evaluations use these same trajectories as their references.
Reading the two columns. The two columns evaluate final solution quality and feasibility, and the speed and coverage of reaching a common quality target, respectively. Let Ri denote the best strictly feasible objective found by Gurobi (threads=8) on instance i within H=3600 s. The quality column reports the mean relative objective difference, Δref=100(fi(H)−Ri)/∣Ri∣, over strictly feasible outputs, together with strict/total, the number of test instances yielding such outputs. Lower values indicate better solution quality, and negative values indicate improvement over the Gurobi reference. The TTT column reports the average time to first reach the common quality target over instances that reach it, together with hits/total, the number of test instances reaching that target. Thus, the reported times show how quickly targets are reached, while the accompanying counts show how broadly each method succeeds across the test set.
For UC, the target is Ri+0.0105∣Ri∣. For BinPacking, let Bi be the number of bins in the common FFD initialization; the target is Bi−1. Necessary initialization, construction, coordination, recovery, polishing, and online LLM waiting remain charged before a hit. Appendix N defines the timing conventions; Appendix P provides data-level and instance-level objective–wall trajectories.