- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes a training framework for using LLMs as end-to-end combinatorial optimization solvers. Compared to methods that primarily use outcome-based rewards, they construct process rewards based on mathematical evaluation criteria as supervision signals. Specifically, they borrow the decomposition idea of column generation and structure the chain of thought of LLMs into COLUMNS and MASTER blocks. They first train the model using solver-derived demonstrations and freeze the resulting SFT checkpoint as the reference policy for preference optimization. They then alternate between preference optimization using pairs constructed at selected block boundaries and RL using complete solution trajectories. The proposed method is tested on six classes of CO problems.
Critical strengths
This paper demonstrates a novel way to structure the model's CoT as decomposed blocks inspired by the CG method and to supervise the training of end-to-end LLM-based CO solvers using mathematically grounded evaluation criteria. The appendix also provides concrete worked examples and detailed explanations to help clarify the proposed method.
Critical weaknesses
The current experiments focus on six classes of CO problems with small instance sizes (even the largest instances remain small, e.g., 16-25 items for BPP or 16-25 nodes for TSPTW under NLCO's size definitions). The paper does not report solving times using conventional solvers on these instances, therefore, it is unclear if training an end-to-end LLM solver offers practical computational benefits. It is also unclear whether the trained model generalizes across problem sizes or types , as the training data configuration is not clearly specified. In particular, are separate models trained for each problem class, or is a single model trained jointly on all six classes? Moreover, the proposed method is not evaluated on broader long horizon tasks, so the suggested benefits for real-world long horizon reasoning in the abstract remain unverified.
Questions for authors
- In table 2,CG-CoT SFT achieves an FR of 9.52% but a Q5 of 19.05% on large scale problems. But according to the definitions in section 5.1, FR should be no smaller than Q5. is this a typo?
- Are separate models trained for each problem class, or is a single model trained jointly on all six classes? What are the training data sources and dataset sizes for SFT, DPO, and RL? Do these stages use the same problem instances or separate sets of instances?
- Forge (Li et al., 2026) is discussed as a closely related method but is not included in the experimental comparison. Is there a reason for its exclusion?
- The abstract suggests that this approach could improve language models' reasoning on real-world long-horizon tasks. How would the CG-inspired CoT structure apply to such tasks? or is the intended scope limited to CO problems? If so, reporting conventional solver runtimes as well as model inference times would help assess the computational benefit of amortized optimization. Also, has the model been evaluated on problem sizes or problems types not seen during training?
- Appendix F.3 reports λ_P = 0.1 for the TSPTW run. Is this value fixed across tasks? How sensitive is final solution quality to this hyperparameter, given that locally preferred blocks may not lead to better overall solutions?
- I'm curious about how the model's reasoning behavior changes across training stages, for example, how output token counts and the number of optimization rounds change after SFT, and subsequent alternating DPO and RL training.
- Why alternate between local DPO and full-trajectory RL rather than DPO first and then RL? have you compared these two training schedules?
6 comments
[Q4.1, W4] Long-horizon reasoning in real-world decision-making
Thank you for raising this concern. We agree that evaluation on six classes of combinatorial optimization problems alone is insufficient to validate the model’s reasoning capabilities on broader real-world long-horizon tasks. Our research aims to explore how decomposition ideas from operations research and process supervision can be incorporated into model training, enabling models to coordinate multiple local decisions and construct solutions that satisfy overall constraints. To address this concern, we have added a realistic decision-making case study combining multi-day travel route planning and item-packing arrangements to illustrate the potential of our method for real-world decision-making.
The additional experiment further examines this capability in a realistic decision-making setting. The task incorporates route-planning requirements associated with TSPTW and packing requirements associated with BPP into a single natural-language request. The model must produce an overall feasible four-day travel plan while coordinating dependencies across stages. Specifically, the number of backpacks affects travel times and route feasibility; overnight washing and charging determine whether clothing and battery-powered items can be reused on subsequent days; and backpack capacity must be reserved for a souvenir collected during the trip. The complete task description and evaluation criteria are provided in Appendix J.1–J.2.
We compare three workflows based on Qwen3.5-9B: base-model free reasoning with the reasoning prompt, a code-enabled agent with access to Python and preinstalled OR-Tools, NumPy, and pandas, and our trained routing model with the reasoning prompt. Our workflow combines the trained routing model with base-model packing and maintenance decisions, without additional training for the travel task. We evaluate the complete submitted plans against all task constraints. The results are as follows:
| Method | Whole-plan feasibility | Cumulative output tokens ↓ |
|---|---|---|
| Base-model free reasoning + reasoning prompt | Feasible | 32,926 |
| Code-enabled agent | Infeasible | 29,254 |
| Our trained routing model + reasoning prompt | Feasible | 13,149 |
The results show that our workflow constructs a complete feasible plan with 55.1% fewer cumulative output tokens than the code-enabled agent, whose submitted plan is infeasible. It also uses 60.1% fewer cumulative output tokens than base-model free reasoning with the reasoning prompt, which also produces a feasible plan. This supplements the original evaluation on individual task families and shows the potential of learned optimization capabilities to support realistic planning needs involving multiple types of combinatorial constraints. Detailed results and the generated travel plan are provided in Section 5.6 and Appendix J.4–J.5, Tables 7–9.
[W1] Problem instance sizes
Thank you for this suggestion. We agree that, by the standards of traditional combinatorial optimization, the instances in the original manuscript remain relatively small. The term “Large” follows NLCO’s relative size categories and does not refer to industrial-scale instances. Nevertheless, distinguishing between instance sizes within this range remains meaningful. The specific size ranges are provided in Appendix H.1, Table 3.
Our research targets the everyday decision-making needs of ordinary users. Specialized solvers play an important role in tasks such as large-scale industrial production scheduling. We aim to investigate how users who lack experience in mathematical programming and coding can conveniently obtain feasible, high-quality solutions through natural-language interaction. The practical travel-planning case in Appendix J illustrates this application setting. At the benchmark sizes evaluated here, our language-based reasoning method achieves higher feasibility on all six tasks and higher optimality rates on five tasks than a Qwen3.5-9B agent equipped with SCIP and code-execution capabilities. The comparison from Table 1 is summarized below, with further analysis in Appendix I. All values are percentages.
| Task | Our method: FR ↑ | Agent with SCIP: FR ↑ | Our method: Opt. ↑ | Agent with SCIP: Opt. ↑ |
|---|---|---|---|---|
| CSP | 90.67 | 12.00 | 56.00 | 9.33 |
| BPP | 88.67 | 66.67 | 86.00 | 66.67 |
| CVRP | 72.67 | 16.00 | 16.67 | 16.00 |
| TSPTW | 60.67 | 22.67 | 14.00 | 20.00 |
| JSSP | 64.67 | 2.67 | 27.33 | 2.67 |
| GCP | 66.00 | 49.33 | 50.00 | 48.00 |
We have also added evaluations beyond the training sizes to further examine the applicability of our method. Specifically, for CSP, all training stages use instances with 5–25 item types. We further evaluated the model on expanded instances with 25–42 item types, achieving a feasibility rate of 48.61% and a mean gap over feasible solutions of 1.46% using Best-of-N (N=8). The largest instance with a feasible generated solution contains 41 item types, compared with the training maximum of 25. These results are reported in Section 5.6 and Appendix L, Table 13.
We thank the reviewer Fw79 for the careful reading and constructive suggestions. Your comments have helped us clarify the training and evaluation settings, strengthen comparisons with existing methods, and expand our analyses of generalization, process-reward sensitivity, and learned reasoning behavior. We have also added a practical decision-making case study to illustrate the intended applications of our approach. Below, we respond to each point and summarize the corresponding revisions.
[Q1] Consistency between FR and Q5 in Table 2
Thank you for your careful reading. We re-examined the original files and found that the evaluation function used for the original records did not account for certain cases, which caused the inconsistency. We have corrected this issue. Q5 measures the proportion of all instances with feasible solutions meeting the quality threshold, so it cannot exceed FR.
Meanwhile, we have further extended our CSP experiments. We observed that, after a prolonged plateau, the feasibility rate increased again. This indicates that the earlier checkpoint used in the original manuscript did not fully capture the gains achievable through further training. Under greedy evaluation, the updated main method achieves a feasibility rate of 82.00%, a near-optimality rate (Q5) of 72.00%, and a mean gap over feasible solutions of 4.44% on CSP Large. The updated results are reported in Section 5.3, Table 2.
We have also conducted a series of analyses of this phenomenon, as detailed in Section 5.5, Figure 5, and Appendix M.
[Q2, W3.2] Model training and data configuration
Thank you for raising this question. We have clarified the training setup in the manuscript. Specifically, the main-method results on the six problem families were obtained from six separately trained models. All models are initialized from Qwen3.5-9B and use the same training framework, with each model trained on data from its corresponding task.
Regarding data sources, all training problem instances are constructed using the problem-generation code provided by NLCO. SFT and the RDO–RLOO stage use disjoint sets of problem instances, while RDO and RLOO share the same problem-instance pool. The training samples for each stage are constructed as follows:
Under this procedure, the RDO preference samples and RLOO responses are regenerated as the policy is updated.
The training data sizes are summarized as follows. For each single-task model, SFT uses 7,850 complete demonstration trajectories, while RDO and RLOO share a pool of 3,200 training problem instances. We have added these configurations in Appendix H.1–H.4, including the benchmark instance-size ranges in Table 3 and training hyperparameters in Table 4. Further details of demonstration construction and the training procedure are provided in Appendices B and D.
[Q3] Comparison with Forge
Thank you for this suggestion. We have reproduced Forge on all six task families studied in this work and included it in the updated experimental comparisons. Forge’s single-response results have been added to Table 1. In addition to single-response evaluation (N=1), we have also added Best-of-N (N=8) results for the Forge baseline to compare the benefits that different methods obtain from additional sampling.
The results show that our method achieves better solving performance on the vast majority of problems. Detailed feasibility rates, optimality gaps, and optimality rates, together with the corresponding BoN results, are provided in Section 5.2, Table 1.