acceptodds
Under review as a conference paper at ICLR 2027

From Algorithms to Reasoning: Operations Research as Process Supervision for Language Models

Abstract

Autonomous combinatorial optimization remains challenging for language models, while operations research provides well-established algorithms for these problems, and internalizing these algorithms as learned solution strategies could enhance the models’ optimization capabilities. We propose a training framework that uses operations research as verifiable process supervision, translating algorithmic structures and mathematical evaluation criteria into learning signals for intermediate decisions. The model constructs and revises candidate solutions through natural-language reasoning, while a verifier used during training evaluates and compares alternative decisions from the same state using constraint satisfaction, objective values, and algorithm-specific quality criteria. Under shared process-quality criteria, the framework combines local preference learning weighted by quality gaps with reinforcement learning over complete trajectories to jointly train local decision-making and global coordination. Experiments across six classes of combinatorial optimization problems demonstrate improvements in feasibility rates and solution quality. This approach to algorithm internalization could strengthen language models’ reasoning over long-horizon tasks in real-world settings, providing a methodological foundation for agent decision-making.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Large Language Models;Combinatorial Optimization;Column Generation; Reinforcement Learning; Algorithmic Reasoning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Fw79OpenReview ↗
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
  1. 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?
  2. 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?
  3. 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?
  4. 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?
  5. 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?
  6. 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.
  7. 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

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:

  • SFT: We implemented our own branch-and-price solver based on column generation. Through filtering and merging, we ensure that 80% of the demonstration trajectories exhibit iterative objective improvement and keep their lengths suitable for training, thereby constructing the CG-CoT demonstrations.
  • RDO: We sample problems from the shared instance pool, generate responses using the current policy, and sample candidate blocks conditioned on the same selected prefix. An OR-based evaluator constructs preference pairs according to validity, feasibility, and quality differences for RDO updates.
  • RLOO: We sample fresh complete responses to problems from the shared instance pool using the updated policy and perform reinforcement learning using terminal rewards and OR process rewards.

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.

[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:

MethodWhole-plan feasibilityCumulative output tokens ↓
Base-model free reasoning + reasoning promptFeasible32,926
Code-enabled agentInfeasible29,254
Our trained routing model + reasoning promptFeasible13,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.

TaskOur method: FR ↑Agent with SCIP: FR ↑Our method: Opt. ↑Agent with SCIP: Opt. ↑
CSP90.6712.0056.009.33
BPP88.6766.6786.0066.67
CVRP72.6716.0016.6716.00
TSPTW60.6722.6714.0020.00
JSSP64.672.6727.332.67
GCP66.0049.3350.0048.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.

Reviewer_RhEoOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes an operations research (OR)-guided process supervision framework for LLM-based combinatorial optimization. The proposed CG-CoT structures reasoning into column generation and master optimization steps, while combining SFT, reward-weighted DPO (RDO), and RLOO reinforcement learning. Experiments across six optimization tasks demonstrate improvements in solution feasibility and quality.

Critical strengths
  1. Interesting integration of OR and process supervision. The paper introduces mathematical optimization criteria to supervise intermediate reasoning steps, providing more informative training signals.

  2. Broad experimental evaluation. Experiments across six combinatorial optimization tasks demonstrate promising improvements in feasibility and solution quality.

Critical weaknesses
  1. Insufficient ablations and missing RL baselines. The contributions of key components are not adequately isolated, including quality-weighted DPO, process rewards, RTG, and alternating RDO–RLOO training. A standard GRPO baseline is also missing. Comparisons under matched training budgets are needed to justify the proposed framework.

  2. Incomplete comparisons and presentation issues. Best-of-8 results are reported only for the proposed method, without equivalent baseline comparisons. Evaluation sample sizes also differ across methods without sufficient clarification. Additionally, Table 1 has excessively small fonts, while Figure 2 contains overlapping arrows and inconsistent abbreviations (JSP vs. JSSP).

Questions for authors
  1. Can the authors provide more comprehensive ablations to clarify the contributions of individual training components?

  2. How does the proposed method compare with standard GRPO under the same training budget?

  3. Can the authors provide matched Best-of-N comparisons and clarify the evaluation sample sizes?

2 comments

We thank the reviewer RhEo for the careful review and constructive suggestions. Your comments have helped us clarify the GRPO baseline and training configurations, strengthen the analysis of individual training components, expand the Best-of-N comparisons, and improve the presentation of our results. We address your comments and summarize the corresponding revisions below.

[W1.2, Q2] Comparison with GRPO and Clarification of Training Budgets

Thank you for raising this question. We would like to clarify that the method applying GRPO to combinatorial optimization is FOARL [1], which is already included among our experimental baselines. FOARL uses GRPO with terminal rewards that evaluate solution feasibility and optimality. It is included in Table 1, and we have further clarified this relationship in the manuscript. Our method achieves higher feasibility than FOARL on all six tasks under single-response evaluation. In particular, on CSP, our method increases FR from 64.67% to 90.67% while reducing Gap from 6.78% to 3.27%.

We report the initialization and training configurations in Appendix H.2–H.5, with our method’s hyperparameters summarized in Table 4. Both methods use Qwen3.5-9B as the base model, with SFT conducted separately according to their respective procedures. They use the same dataset sizes—7,850 SFT examples and 3,200 RL training instances per task—and the same number of RL training iterations. We also analyze differences in their training behavior. The results are shown in Figures 4(a) and 5(c), with discussion in Sections 5.4–5.5 and Appendix M.2.

The results show that, over the first pass through the common training pool, our method with OR process supervision achieves a higher mean fixed terminal score RFR_F, excluding process-reward bonuses from the evaluation. Together with the component ablations in Section 5.3, Table 2, these results support the contribution of OR process supervision to improving the LLM’s ability to solve combinatorial optimization problems.

[W1.1, Q1] Individual Contributions of the Training Components

Thank you for this suggestion. We agree that the contributions of the training components should be examined more explicitly. We therefore conducted additional ablation experiments. Our full training framework consists of CG-CoT SFT + RDO + OR-RLOO + RTG. We evaluate variants that replace RDO with unweighted DPO, remove both OR process rewards and RTG from RLOO, disable RTG alone, or perform RDO first and then OR-RLOO, to examine their respective contributions.

Detailed results are provided in Section 5.3, Table 2, with configuration definitions in Appendix H.6. The summary below aggregates greedy evaluation results across all 150 CSP instances. The standard RLOO variant retains RDO while disabling both OR process rewards and RTG.

Training variantFR (%) ↑Q5Q_5 (%) ↑Gap (%) ↓
Full method90.6787.333.27
DPO in place of RDO88.6783.333.16
RTG = 084.0084.002.39
Standard RLOO72.6772.672.06
RDO first, then OR-RLOO84.0078.671.59

The results show that the full method achieves the highest overall FR and Q5Q_5 among the ablated variants. To better understand the role of alternating training, we also analyze how local preference data change as the policy evolves, with details provided in Section 5.3, Figure 2.

In particular, alternating training continually refreshes preference data using the current policy. Compared with RDO first, alternating RDO and RLOO reduces candidate invalidity from 17.61% to 4.26%, while the difference between pricing-quality and validity preference shares shifts from −5.01 to 15.45 percentage points. Furthermore, holding candidate pairs fixed and rescoring them under later states’ LP dual prices reverses 26.5% of eligible preferences under instance weighting. These observations show that both the candidate distribution and local quality comparisons change as training proceeds, supporting continued resampling and preference supervision to keep training aligned with the evolving policy.

[W2.2] Table readability and figure presentation

Thank you for pointing out these issues. We initially considered the single-sample results sufficient to demonstrate the advantages of our method, while BoN was primarily intended to show its performance with additional sampling. We now agree that the benefits of Best-of-N sampling should be evaluated for both our method and the baselines. To this end, we have added corresponding BoN evaluations for multiple baselines. The results are summarized below (all values are percentages):

MethodBPPJSSPCVRPTSPTWCSPGCP
FR ↑Gap ↓Opt. ↑FR ↑Gap ↓Opt. ↑FR ↑Gap ↓Opt. ↑FR ↑Gap ↓Opt. ↑FR ↑Gap ↓Opt. ↑FR ↑Gap ↓Opt. ↑
FOARL (N=1)78.674.2462.672.6713.630.6712.759.931.3434.673.3117.3364.676.7827.3341.331.6139.33
FOARL + BoN (N=8)91.334.3470.676.6731.721.3322.157.756.0450.003.2326.0092.003.6352.0064.001.5160.00
Forge (N=1)73.333.7467.332.0011.161.3310.679.123.3334.673.5118.6761.335.1432.0044.671.3442.00
Forge + BoN (N=8)90.672.9573.337.3321.733.3323.337.256.6749.333.3426.6792.002.7061.3364.000.9461.33
Our method (N=1)88.670.5586.0064.677.3527.3372.6712.6416.6760.6710.2014.0090.673.2756.0066.001.3550.00
Our method + BoN (N=8)100.001.3194.0074.677.9236.0086.6710.4518.6787.335.9526.6796.002.5663.3372.000.9456.00

The results show that our method outperforms the other methods on the vast majority of problems.

Evaluation sample sizes. We have now completed evaluation on the full NLCO evaluation set for the tasks studied in this work and updated Table 1. All methods are compared on the same test instances.

Updated training results. We also extended CSP training and observed that, after a plateau, the feasibility rate increased again and the optimality gap decreased further. Thus, the earlier checkpoint did not capture these later training gains. We have updated the table with full-test-set evaluation results for the model obtained after extended training.

[W2.2] Table readability and figure presentation

Thank you for pointing out these presentation issues. We will increase the font size in Table 1 and adjust its layout to improve readability. For Figure 2, we will revise the arrow layout and visual styling to reduce overlap and make the optimization trajectories easier to follow. We have also addressed similar presentation issues elsewhere in the manuscript.

We will also replace the inconsistent “JSP” labels with “JSSP” and ensure consistency across the main text, figures, and captions.

[1] Jiang, Xia, et al. “Large Language Models as End-to-end Combinatorial Optimization Solvers.” Advances in Neural Information Processing Systems, 38, 2025.

Reviewer_UQnMOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper investigates training large language models (LLMs) as direct, end-to-end combinatorial optimization solvers without test-time external solver calls. To overcome the limitations of outcome-only reinforcement learning, the authors propose an operations research (OR)-driven process supervision framework grounded in column generation (CG) and branch-and-price (B&P) principles.

Specifically, the method introduces CG-CoT, a block-structured chain-of-thought format alternating between <OR:COLUMNS> (proposing candidate partial solutions/columns) and <OR:MASTER> (assembling accumulated columns into a global integer plan), concluding with <OR:FINAL>. During training, an offline OR evaluator computes LP dual values, reduced costs, and dual relaxation lower bounds (based on dual-feasibility correction) to evaluate intermediate blocks. The policy is first initialized via supervised fine-tuning (SFT) on solver-derived traces, followed by alternating RDO (OR-reward-weighted Direct Preference Optimization on same-prefix alternative blocks) and RLOO (Reinforcement Learning Leave-One-Out over complete trajectories with a causal history baseline). The approach is evaluated on Qwen3.5-9B across six classical combinatorial optimization problems from NLCO (BPP, JSSP, CVRP, TSPTW, CSP, and GCP).

Critical strengths

Mathematically Sound Process Supervision Formulation:

The paper provides a rigorous mathematical adaptation of classical column generation theory into intermediate process supervision. Specifically, Proposition 1 and Appendix C effectively leverage dual-feasibility correction bounds to bound subproblem pricing errors and integer master suboptimality without solving NP-hard problems during training. The ablation studies (Table 2) clearly substantiate the complementary roles of local preference updates (RDO) and global trajectory coordination (RLOO).

Critical weaknesses
  1. Impractical Setting, Severe Scalability Wall, and Missing OOD Evaluation:
  • Artificial Problem Setting: The "no-tool end-to-end" paradigm is disconnected from real-world agent practices, where discrete optimization is naturally delegated to dedicated solvers or execution harnesses. Forcing an LLM to autoregressively emit thousands of JSON tokens to solve standard MILPs offers negligible practical utility.
  • Severe Scalability Collapse: Autoregressive token sampling cannot withstand combinatorial explosion. Table 2 shows that on CSP "Large", the model's feasibility rate (FR) plummets to 38.10%, and the optimality rate (Opt.) collapses to 4.76%, demonstrating that soft probabilistic generation hits an immediate wall on non-trivial instances.
  • Absence of Algorithmic OOD Validation: The paper claims to study "algorithm internalization," yet evaluates exclusively on the six training task families. Without zero-shot evaluation on an unseen decomposable problem (e.g., facility location), there is no evidence that the model has internalized column generation rather than merely memorizing task-specific prompt templates and heuristics.
  1. Unpolished Presentation and Layout Issues (Table 1 and Formatting): The manuscript feels largely unpolished. The font size in Table 1 is visibly way smaller than 10pt (and well below allowable table minimums), making it difficult to read. Furthermore, the formatting of figures and tables throughout the paper displays noticeable spacing quirks—for instance, the caption of Table 1 sits uncomfortably close to the table itself while leaving an unnatural gap to the body text above, suggesting ad-hoc \vspace adjustments to force pagination. While agent assistance in research and drafting is understandable, the authors still bear the ultimate responsibility for the presentation quality of their submission.
Questions for authors
  1. Practical Motivation of the "No-Tool End-to-End" Setting: The authors motivate this work by claiming it strengthens LLM reasoning for "real-world settings" and provides a foundation for "agent decision-making." However, the mainstream consensus in modern AI is overwhelmingly to leverage scaffolded execution harnesses, environments, or dedicated solvers to unlock model capability (analogous to how recent breakthroughs on ARC-AGI achieved near-100% scores through test-time search harnesses rather than expecting unassisted token guessing). What is the genuine practical value of forcing an LLM into an unassisted, end-to-end token generator that emits thousands of raw JSON tokens—especially when dedicated lightweight solvers handle these instances in milliseconds with 100% feasibility, while the proposed method achieves only a 38% feasibility rate on larger instances?
  2. Generalization and the Limits of Probabilistic Generation (vs. Deterministic Execution like Qwenputer): Even if we grant this "no-tool end-to-end" setting for the sake of argument, how do the authors justify its theoretical and practical viability?
    • Algorithmic Generalization: Does the model truly internalize column generation as a general algorithmic strategy, or is it merely memorizing task-specific prompt heuristics? Can the authors provide zero-shot evaluation on an unseen decomposable problem family (e.g., facility location)?
    • Probabilistic Sampling vs. Deterministic State Machines: Combinatorial optimization inherently requires exact, deterministic state transitions. Recent open-source explorations on Qwen (such as Qwenputer, which compiles a 32-bit RISC-V CPU into Qwen3.5's Gated DeltaNet attention memory to execute deterministic code internally) suggest that executing algorithms inside weights without tools requires deterministic state-machine mechanisms. In contrast, this paper relies on soft probabilistic token sampling, which quickly collapses under combinatorial explosion (evidenced by the 4.76% optimal rate on CSP Large). How can a purely probabilistic token-generation paradigm ever overcome this fundamental combinatorial ceiling?
4 comments

We thank Reviewer UQnM for the careful review and constructive feedback. Your comments have helped us clarify the practical value of our approach, strengthen the evaluation on larger instances and the analysis of learned solving behavior, and improve the presentation. We address your concerns and summarize the corresponding revisions below.

[W1.1, Q1] Practical value of directly generating solutions

Thank you for raising this concern. We agree that specialized solvers and execution tools play an important role in optimization tasks such as large-scale industrial production scheduling. Our research addresses the combinatorial optimization needs of everyday users, aiming to help them obtain feasible, high-quality decision plans more conveniently and quickly through natural-language interaction. We also seek to further explore the potential of LLMs for solving NP-hard problems.

First, our work aims to make optimization accessible to non-expert users. Many everyday decisions involve optimization, while users seeking decision-making assistance may lack experience in mathematical programming. Setting up solver environments and meeting licensing requirements can pose substantial barriers, making it practically valuable to obtain solutions directly through language. In these settings, tasks are often moderate in size and involve ambiguous, interrelated requirements expressed in natural language, which can be difficult to translate accurately into mathematical models and executable programs.

Our work continues the exploration of language-driven combinatorial optimization pursued by EHOP [1], GraphArena [2], FOARL [3], Forge [4] and NLCO [5]. This research direction aims to develop interactive, code-free models that enable non-expert users to obtain solutions without writing programs, particularly for everyday decision-making tasks involving ambiguous requirements. We believe that their usability, interactivity, and accessibility will make this research direction increasingly important.

To examine whether our approach can better meet these needs compared with workflows relying on “dedicated solvers or execution harnesses,” we conducted supplementary experiments using the same Qwen-3.5-9B backbone. We allowed the tool-enabled baseline to install software packages, generate programs, and execute code. The results are summarized below.

MethodFeasibility rate (%) ↑Time (s) ↓
Qwen-3.5-9B agent28.22492.60
Our method (9B)73.14≈225.6

The results show that, at the problem scales considered in our paper, our method achieves a higher feasibility rate and produces solutions in less time. Solver execution is only one component of the overall workflow. A tool-using agent must also correctly formulate the requirements, generate code, and convert execution results into the final solution, while debugging errors when they occur. The time and reliability of these steps jointly affect the delivery of the final solution.

Furthermore, we constructed a realistic decision-making task combining multi-day travel route planning and item-packing arrangements to illustrate the practical value of our approach. Details are provided in Appendix J. This task resembles a coupling of TSPTW and BPP in an everyday decision setting and illustrates the ambiguity and modeling difficulties of such tasks. The results are shown below.

MethodOverall feasibility rate (%) ↑Time (s) ↓
Qwen-3.5-9B100.001,659.07
Qwen-3.5-9B agent0.001,542.49
Our joint model100.00657.43

Beyond these practical motivations, we also aim to explore the potential of LLMs for solving combinatorial optimization problems. Previous studies have largely relied on LLMs’ own capabilities to improve combinatorial optimization performance. Our work further investigates how the structure of the problems themselves and traditional operations research knowledge can be translated into effective training signals. In our supplementary analysis, we observe three phenomena:

  1. Model performance exhibits plateaus and stepwise gains during reinforcement learning.
  2. Incorporating OR process signals leads to higher final performance than reinforcement learning based solely on outcome rewards.
  3. Training improves the reliability of initial solution construction and the preservation of existing feasible plans, with these subprocesses improving at different rates across training stages.

Details are provided in Sections 5.3–5.5 and Appendix M. These observations support an explanation in which improvements in solving subprocesses translate into terminal gains through discrete generation choices and final constraint checks. A plateau in terminal evaluation therefore does not necessarily indicate that learning has stopped. These analyses provide empirical evidence for understanding how OR process supervision improves LLM solving capabilities.

[W1.2] Performance on larger instances and extended training

Thank you for pointing this out. We agree that performance on larger instances is an important aspect of evaluating our method. Our method now achieves a feasibility rate of 82.00%, an optimality rate of 28.00%, and a mean optimality gap of 4.44% on the large CSP instances evaluated here.

This is because to investigate the reported limitation, we extended training to examine how model performance evolved. After extended training, we observed that feasibility improved again and the optimality gap decreased further following a prolonged plateau. The updated metrics are reported in Table 2, Section 5.3. These observations indicate that training progress is not uniform, and a plateau does not necessarily mean that the benefits of further training have been exhausted. A detailed analysis of the training dynamics is provided in Section 5.5 and Appendix M.

The results reported in the original manuscript did not fully reflect the advantages of our method. The updated CSP Large results are summarized below.

Training checkpointFeasibility rate FR (%) ↑Optimality rate Opt. (%) ↑Gap over feasible solutions (%) ↓
Originally reported checkpoint38.104.7610.50
Checkpoint after extended training82.0028.004.44

The original results were reported on the sampled evaluation set, while the updated results use the complete CSP Large test set. The fixed-instance analysis of training progress is provided in Section 5.5 and Appendix M.

These results more comprehensively characterize our method’s performance at the larger instance sizes evaluated. Further training brings improvements within our original autoregressive solution-generation framework, indicating that the observed bottleneck can still be alleviated through learning.

The current feasibility rate of 82.00%, together with our training-dynamics analysis, indicates that autoregressive solution generation can be further improved through learning. Specifically, incorporating OR process signals leads to higher final performance than reinforcement learning based solely on outcome rewards. Our behavioral analysis identifies improvements in initial solution construction and feasible-plan retention. These observations support an explanation in which these subprocesses improve at different rates, and their improvements translate into terminal gains through discrete generation choices and final constraint checks. Further discussion is provided in Sections 5.3–5.5 and Appendix M.

[W2] Table 1 and overall presentation

Thank you for pointing out these presentation issues. We agree that Table 1 would benefit from improved readability. We will increase its font size and reorganize the layout accordingly. We will also revise the affected figure and table spacing elsewhere in the manuscript to improve presentation consistency.

But we would like to clarify that we did not use manual \vspace adjustments around Table 1 to force pagination. Table 1 was typeset using the standard LaTeX table environment and \caption command under the conference template.

[Q2.2] Probabilistic Generation and Deterministic Execution

Thank you for raising this concern. We agree that reliable state maintenance is important for combinatorial optimization. We would like to distinguish between exact program execution and learning effective optimization strategies. Qwenputer compiles a predefined RISC-V processor into additional network layers, with processor weights assigned by a compiler while the original Qwen weights remain unchanged. This demonstrates an approach to exact internal execution, but does not establish that effective learning-based optimization must rely on this mechanism. Its technical documentation also records cases where the processor returns the correct result, but the language model subsequently produces an incorrect answer, illustrating that reliable execution and effective coordination of the solution process remain distinct challenges. [6]

Probabilistic generation does not preclude satisfying deterministic constraints. The key question is whether the learned policy can reliably construct feasible, high-quality solutions. We study this through verifiable OR process supervision. During training, candidate columns receive feedback on their validity and pricing quality, while assembled solutions are evaluated for feasibility and objective quality.

To examine the contribution of these supervision signals, we added CSP experiments and training ablations, including Ours w/o process reward & RTG. This ablation retains RDO but disables both OR process rewards and RTG, using only terminal rewards during the RL stage. Compared with this control, the full method increases the feasibility rate from 72.67% to 90.67% and the near-optimality rate Q5Q_5 from 72.67% to 87.33%. Detailed results are provided in Section 5.3, Table 2, with the ablation configurations described in Appendix H.6.

To examine and illustrate the effects of training, we use the same fixed terminal score RFR_F to evaluate solution quality and compare first-plan construction before and after training. Over the first pass through the common training pool, our final submissions achieve a higher mean RFR_F than the FOARL and Forge baseline curves. The moving-average RFR_F of our first complete-plan attempts also remains above both baseline curves throughout the plotted CSP training windows (Figure 4(a)). In the before-and-after CSP analysis, first-plan feasibility increases from 71.08% after CG-CoT SFT to 89.08% after subsequent training (Appendix M.1). This indicates that the benefits of mathematically grounded process supervision extend beyond inference-time iterative optimization and also involve changes to the solution-construction strategies learned by the LLM.

[W1.3, Q2.1] Generalization of learned optimization strategies

Thank you for this question. We examine learned optimization capabilities and their transfer through three complementary analyses.

1. Reuse in practical decision-making. In the four-day travel scenario discussed above, our frozen joint SFT routing policy generates 5/5 feasible routes, compared with 2/5 for base-model CG-CoT prompting within the same workflow, without additional training (Appendix J). This comparison identifies a contribution from the learned policy beyond providing the structured prompt.

2. Mathematically verified solving behavior. Our trajectory analysis evaluates proposed columns using reduced costs under the current prefix’s LP dual and compares generated plans with the restricted integer optimum supported by their accumulated column pools. In the illustrated GCP and TSPTW trajectories, generated plans attain these restricted optima (Figure 3 and Appendix F).

The GCP transfer failure reported below does not by itself establish that the model merely memorizes templates. Our CSP analysis shows that post-SFT training increases first-plan feasibility from 71.08% to 89.08% and final feasibility conditional on a feasible first plan from 73.62% to 99.91%, while the mean number of MASTER blocks remains essentially unchanged at 4.84 versus 4.82 (Appendix M). These observations support improvements in solution construction and plan preservation, while the GCP results identify a boundary of the measured cross-family transfer.

3. Transfer to a new objective and a different problem family. To examine objective transfer within routing, we freeze our source-selected TSPTW checkpoint (RL290) and evaluate weighted traveling repairman with hard time windows. The new objective minimizes weighted customer service-start times while retaining mandatory visits and depot return. We use 16 generated development instances, eight each at 7 and 8 customers, without target-task training. The prompt includes one numerical example. BoN8 uses temperature 0.9 and a 16,384-token response limit. Complete candidates are independently checked and ranked by the new objective without repair. Exact enumeration provides the reference optima.

CustomersInstancesFeasibility (%) ↑Exact optimality (%) ↑Mean gap (%) ↓
78100.0012.505.07
88100.0050.002.24
Overall16100.0031.253.65

Exact optimality is the percentage of instances attaining the reference optimum, and mean gap is averaged over feasible solutions. The frozen model with BoN8 achieves 100% feasibility and five exact optima, supporting reuse under a new objective within a shared routing structure.

Cross-family transfer to GCP is substantially weaker. We evaluate 12 graphs with 9–23 vertices. The frozen TSPTW models achieve 1/12 feasible solutions.

A possible explanation is the change in column construction and solution assembly: TSPTW requires ordered routes with time propagation, whereas GCP requires independent sets combined into a complete valid coloring. Shared CG-CoT notation does not make these operations equivalent.

References

[1] Duchnowski, Alex, Ellie Pavlick, and Alexander Koller. “A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems.” Findings of the Association for Computational Linguistics: EMNLP 2025, pp. 6628–6651, 2025.

[2] Tang, Jianheng, et al. “GraphArena: Evaluating and Exploring Large Language Models on Graph Computation.” The Thirteenth International Conference on Learning Representations, 2025.

[3] Jiang, Xia, et al. “Large Language Models as End-to-end Combinatorial Optimization Solvers.” Advances in Neural Information Processing Systems, 38, 2025.

[4] Li, Xiaozhe, et al. “Forge: Quality-Aware Reinforcement Learning for NP-Hard Optimization in LLMs.” Findings of the Association for Computational Linguistics: ACL 2026, pp. 28351–28368, 2026.

[5] Jiang, Xia, et al. “Reasoning in a Combinatorial and Constrained World: Benchmarking LLMs on Natural-Language Combinatorial Optimization.” Findings of the Association for Computational Linguistics: ACL 2026, pp. 30592–30648, 2026.

[6] Agrawal, Divyansh. Qwenputer: a computer compiled into the weights of a pretrained language model. Version 0.1.0, software and technical documentation, 2026. https://github.com/divagr18/qwenputer

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.