acceptodds
Under review as a conference paper at ICLR 2027

Beyond Heuristic Ceiling: Co-Evolving LLM-Generated Heuristics and RL Selection for Combinatorial Optimization

Abstract

Neural combinatorial optimization faces a trade-off between solution quality and learning efficiency. End-to-end construction policies can attain high solution quality but incur substantial training cost and scale poorly due to their growing action space, whereas reinforcement learning (RL)-based heuristic selection learns efficiently over a compact action space but its performance ceiling is limited by the heuristic pool. To break this ceiling while retaining the learning efficiency of heuristic selection, we propose **CoEvoRL**, a collaborative framework that co-evolves LLM-generated heuristics and an RL-based selector. We formulate heuristic selection as a restricted Markov decision process and decompose its suboptimality into an action-abstraction gap induced by insufficient heuristic coverage, and a finite-sample RL training error whose bound increases with pool size. Motivated by this decomposition, CoEvoRL alternates between selector training and heuristic evolution in a closed loop, where the selector identifies coverage gaps in the current heuristic pool to guide the LLM toward complementary heuristics, while the evolved pool reshapes the selection space and drives further policy improvement. Two key designs make this loop practical: a variable-pool heuristic selector that accommodates changing heuristic pools without altering the network architecture, and a selective admission criterion that evaluates candidates by their marginal coverage gains against pool expansion costs to keep the pool compact. CoEvoRL reduces the optimality gap of heuristic selection by 4.6%–39.1%, while matching or outperforming substantially more costly construction policies, using only a lightweight selector and a small fraction of their training budget.

Primary area:
optimization
Keywords:
Neural combinatorial optimization, large language models, automated heuristic design, heuristic selection, reinforcement learning, co-evolution

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_ywCVOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes CoEvoRL, a framework that jointly evolves LLM-generated heuristics and an RL-based heuristic selector. The selector identifies states where the current pool lacks promising actions, and this feedback guides the LLM toward complementary heuristics. A variable-pool selector and coverage-aware admission/pruning rules support this iterative process. Experiments cover JSSP, TSP, multidimensional knapsack, and online bin packing.

Critical strengths
  1. Clear motivation and a meaningful methodological contribution. Using selector feedback to generate complementary heuristics is a sensible way to address this mismatch, and gives the LLM and RL components a clear reason to interact.

  2. The components fit together well. Coverage diagnosis guides generation, the admission criterion controls pool growth, and the variable-pool selector accommodates new heuristics. The analysis provides a useful rationale for balancing action coverage against selection difficulty.

  3. Broad and reasonable evaluation. Comparisons among heuristic-based methods control the initial pool, LLM budget, and selector training budget. The appendix includes results across ten runs with std, while the component ablations and exact decomposition on TSP-10 help explain the source of the gains.

Critical weaknesses
  1. The practical dependence on reference feedback needs clarification. Section 4.2 combines critic-estimated coverage gaps with optional reference-action feedback. However, it is unclear which main experiments use reference actions and how much they contribute. Appendix B.1 describes offline reference solutions, but does not fully explain how these become reference actions at partial states visited by the selector. The current “w/o diagnosis” ablation removes the diagnosis as a whole, so it does not establish how well the method works using only the learned critic. This matters when high-quality reference solutions are expensive or unavailable. Which experiments use reference-action feedback, and how are those actions obtained at the visited partial states? Could the authors report a critic-only variant without reference-action feedback?

  2. Evaluating four problem types is a strength. A compact heuristic pool reduces the selector’s action space, but coverage diagnosis still evaluates the full feasible primitive action set, so computational scalability also deserves empirical validation. Can an evolved pool and trained selector be reused on larger instances or a different distribution without repeating the full co-evolution process? A small transfer experiment, together with a runtime breakdown on larger instances, would help establish the practical scope.

  3. The efficiency claims. Table 3 reports total runtime and LLM usage only for JSSP (10x10), and inference time per instance is not reported. The matched-episode comparisons are useful for the limited-training setting, but the quality-cost trade-off differs across tasks. E.g., on TSP-100, CoEvoRL achieves a 13.94% gap, compared with 0.77% for Construct. (Full). The strongest conclusion is therefore that CoEvoRL improves heuristic selection and performs well under limited training budgets, with task-dependent trade-offs against fully trained construction policies. What is the training/evolution cost and inference time per instance for the other tasks, and specify the actual Full training budgets? A quality vs. total-cost comparison would make the intended application setting clearer.

Questions for authors

Please refer to weaknesses.

5 comments
AuthorsOpenReview ↗

Response by Authors [1/3]

Thank you for your careful review and constructive feedback. We address each point below, and have incorporated the related clarifications and additional results in our revised manuscript.

W1. Reference-action feedback and diagnosis ablations.

Thank you for raising this point.

First, we apologize for the ambiguity caused by our overly brief description in the original manuscript. We have revised Section 4.2 and Appendix B.2 to clarify under what condition reference actions can serve as meaningful diagnostic feedback and how we derive them from offline solutions. We use reference-action feedback only when the problem structure allows us to translate a given offline solution into a well-defined state-action MDP sequence. This feedback is used for TSP and JSSP in our main experiments. Specifically, for TSP, we follow the offline reference tour from the starting city, and take each subsequent city as the reference action for the corresponding decision step. For JSSP, we order the operations in the reference schedule by start time while respecting job precedence, then record their corresponding jobs to obtain a reference dispatch sequence. In both tasks, we use the reference action for diagnosis only if it is feasible in the current rollout state.

For the other two tasks, MKP and OBPP, the same translation does not produce a meaningful reference action at each decision step. In MKP, an offline solution specifies a subset of items but leaves their selection order undetermined, while in OBPP, the offline solution uses future arrivals, and thus a recovered decision may depend on hindsight unavailable to the selector in the current state. We therefore use only the critic-based coverage residual approximation for diagnosis in MKP and OBPP.

Second, to address your concern about the contributions of the critic-based residual and reference-action feedback in the diagnosis, we further evaluate two diagnosis-ablation variants: critic-only diagnosis and reference-only diagnosis:

ProblemJSSP 10×10JSSP 15×15JSSP 20×20TSP-20TSP-50TSP-100
CoEvoRL14.09%19.84%22.72%7.12%11.21%13.94%
critic-only14.90%19.93%22.70%7.21%13.43%13.99%
reference-only14.45%20.15%23.50%7.27%12.06%14.75%
w/o diagnosis15.36%20.41%23.23%7.39%14.49%16.20%

Generally, both signals contribute to the performance, and combining them yields the best gap in nearly all settings, suggesting that the two signals provide complementary information in the diagnostic feedback. Notably, the gain of critic-based diagnosis is more significant on larger instances with longer decision sequences, and the critic-only variant still remains advantageous without reference-action feedback. This demonstrates the effectiveness of CoEvoRL in settings where reference solutions are expensive or unavailable. This additional ablation study is provided in Appendix C.6 (Table 12) of our revised manuscript.

Finally, CoEvoRL still remains effective when reference solutions are expensive or unavailable. In CoEvoRL, each evolution round uses only 12 reference solutions for diagnostic feedback, which can also be reused across rounds. This cost is very low compared to the millions of training samples in common NCO methods. Furthermore, according to the ablation results, CoEvoRL still remains advantageous without reference-action feedback. Therefore, the critic-only variant provides another practical option and remains advantageous in settings where reference solutions are expensive or unavailable.

AuthorsOpenReview ↗

Response by Authors [2/3]

W2. Transfer to larger instances and runtime breakdown.

Thank you for this constructive feedback.

First, following your suggestion, we have evaluated the evolved heuristic pool and trained selector on larger-sized and out-of-distribution instances. We freeze both components of CoEvoRL trained on TSP-100 and JSSP 20 × 20, and evaluate them directly on 1) larger-sized instances up to TSP-1000 and JSSP 100 x 20 and 2) different instance distributions from the TSPLIB and Taillard JSSP benchmarks. The results are as follows (bold = best among methods under matched training budgets):

ProblemJSSP 30×20JSSP 50×20JSSP 100×20TSP-200TSP-500TSP-1000
Construct. (Full)27.83%17.99%7.28%4.50%34.12%52.84%
Construct. (Limit)33.70%21.92%10.21%85.99%130.35%172.35%
Best Heur.30.76%16.97%7.35%28.47%26.17%25.14%
EoH31.05%18.00%7.57%25.06%24.43%24.41%
Fixed Pool27.54%17.30%7.76%23.28%22.95%23.72%
HeurAgenix26.89%17.24%7.24%19.21%20.58%22.48%
CoEvoRL (Ours)26.62%16.71%7.02%17.10%18.27%20.48%
Taillard Bench.15 × 1520 × 1520 × 2030 × 1530 × 2050 × 1550 × 20100 × 20
Construct. (Full)22.16%27.99%24.55%29.11%33.78%20.84%23.49%15.15%
Construct. (Limit)28.82%30.83%34.22%34.28%37.47%23.07%25.86%16.16%
Best Heur.23.94%31.42%27.39%31.21%31.13%20.67%23.93%13.57%
EoH25.40%31.66%28.61%30.86%31.70%20.82%24.33%13.29%
Fixed Pool21.89%27.41%25.17%28.70%30.89%21.01%23.28%13.47%
HeurAgenix21.19%26.36%23.78%28.46%29.95%20.67%22.77%13.18%
CoEvoRL (Ours)21.01%26.49%23.57%28.26%29.45%21.20%22.33%13.17%
TSPLIB Bench.50-100100-200200-500500-10001000-2000
Construct. (Full)1.88%6.08%26.13%43.77%78.08%
Construct. (Limit)51.96%71.47%109.35%143.64%205.61%
Best Heur.25.25%23.38%23.88%27.84%25.94%
EoH21.92%21.29%22.78%26.31%24.81%
Fixed Pool19.49%18.49%22.69%25.12%23.59%
HeurAgenix15.57%16.06%19.92%22.42%23.00%
CoEvoRL (Ours)14.97%15.40%18.81%21.73%21.88%

CoEvoRL shows strong generalization, achieving the best solution quality in nearly all settings. Notably, as the instance size grows, the advantage of learning heuristic selection approaches becomes more significant. The gaps of Construct. (Full) grow from 0.77% to 52.84% when generalizing from TSP-100 to TSP-1000, while CoEvoRL remains stably effective across a range of larger instance sizes (20.48% on TSP-1000) and on out-of-distribution benchmark instances.

Furthermore, in response to your concern about the runtime breakdown, we report the inference runtime on the original and larger-sized instances, and break the total time into three components: 1) generating proposals with the heuristics (Theur.T_{\text{heur.}}), 2) selecting a proposal with the selector (Tselect.T_{\text{select.}}), and 3) updating the environment (Tenv.T_{\text{env.}}). The results are as follows (in seconds):

JSSP10 × 1015 × 1520 × 2030 × 2050 × 20100 × 20
Theur.T_{\text{heur.}}0.018 (34.5%)0.058 (41.0%)0.141 (46.9%)0.295 (51.3%)0.768 (57.0%)2.903 (62.9%)
Tselect.T_{\text{select.}}0.023 (44.4%)0.052 (37.1%)0.094 (31.3%)0.143 (24.8%)0.239 (17.8%)0.486 (10.5%)
Tenv.T_{\text{env.}}0.010 (18.3%)0.028 (19.6%)0.060 (19.9%)0.129 (22.4%)0.326 (24.2%)1.200 (26.0%)
TtotalT_{\text{total}}0.0520.1410.3000.5761.3484.617
TSP20501002005001000
Theur.T_{\text{heur.}}0.004 (37.3%)0.020 (54.0%)0.083 (69.3%)0.321 (78.1%)1.964 (78.6%)7.847 (67.3%)
Tselect.T_{\text{select.}}0.005 (44.5%)0.012 (31.9%)0.024 (20.2%)0.050 (12.1%)0.135 (5.4%)0.607 (5.2%)
Tenv.T_{\text{env.}}0.002 (15.8%)0.005 (12.6%)0.012 (9.6%)0.038 (9.2%)0.395 (15.8%)3.187 (27.3%)
TtotalT_{\text{total}}0.0100.0360.1190.4112.50011.663

As instance size grows, generating proposals with the heuristics becomes the dominant runtime cost, reflecting the necessary computational requirements on larger instances, while the selector accounts for a smaller share of total runtime. Overall, even at the largest sizes tested (TSP-1000 and JSSP 100 × 20), we can reuse the frozen heuristic pool and selector directly, with a modest end-to-end inference time. The full transfer results and detailed runtime statistics are reported in Appendices C.5 and C.7 of our revised manuscript.

AuthorsOpenReview ↗

Response by Authors [3/3]

W3. Inference time and training efficiency.

Thank you for this insightful feedback. Your assessment, "The strongest conclusion is therefore that CoEvoRL improves heuristic selection and performs well under limited training budgets, with task-dependent trade-offs against fully trained construction policies", exactly highlights the central claim and main findings of our work.

Following your suggestions, we now provide 1) more comprehensive training / evolution cost statistics on all four problems (Appendix C.7), 2) the inference runtime on both the original and larger-sized instances (response W2), and 3) the full training budgets of Construct. (Full) baselines in our experiments (Appendix B.3). All the detailed statistics and results are also presented in the appendices of our revised manuscript.

Furthermore, to make our standpoint clearer, we provide a solution quality vs. training budget curve to compare the construction policies under different training budgets from 1× to 12× relative to CoEvoRL (Appendix C.4 of our revised manuscript). The table below summarizes the gaps at selected budgets:

ProblemJSSP 10×10TSP-20MKP-100OBPP-100
CoEvoRL (1×)14.09%7.12%1.32%5.09%
Construct. (1x)22.12%18.32%4.45%7.14%
Construct. (4x)16.43%9.39%4.15%6.95%
Construct. (8x)16.29%8.23%4.11%6.91%
Construct. (12x)17.58%7.58%4.10%6.85%

The marginal gains from additional training vary across tasks, while the construction baseline approaches CoEvoRL on TSP-20 at 12× budgets, but its gains on MKP-100 and OBPP-100 are rather modest, possibly due to different problem structures. CoEvoRL achieves better solution quality than the construction baselines, with only a smaller training budget. The detailed curves are presented in Figure 5 of Appendix C.4.

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

This work studies heuristic selection for combinatorial optimization and proposes CoEvoRL, which adopts RL selector training and LLM-based heuristic evolution in an alternative learning manner. The core idea is to improve action coverage without making the heuristic pool too large. Experiments on four problems and an exact decomposition on TSP-10 are conducted. However, the major concern is whether the analysis justifies the actual working mechanism and the claimed learning efficiency.

Critical strengths
  • The motivation, i.e., enhancing the selector with evolving heuristics rather than standalone performance, is interesting and meaningful.

  • The four-problem evaluation, component ablations, and exact TSP-10 decomposition provide useful evidence for the proposed mechanism.

Critical weaknesses
  • The theoretical results do not justify the statistical cost used in Eq. (12). Proposition 2 studies the existence of a tabular learner for a fixed pool, whereas the implementation uses neural policy gradients and an evolving pool. An increasing upper bound also does not show that each added heuristic increases actual training error. Thus, the admission rule is a motivated heuristic, not a consequence guaranteeing improvement.

  • The efficiency comparison needs to consider the information used in coverage diagnosis. CoEvoRL learns an off-pool critic over primitive actions and can use precomputed reference actions. Their contribution and preparation cost are not isolated. Moreover, the construction comparison modifies POMO to single-start decoding, so it does not establish superiority over its standard inference procedure.

Questions for authors

Q1. A primary concern is the connection between Eqs. (7), (9) and (12). Eq. (7) uses the Q∗Q^*-greedy policy's state distribution, not the learned selector's. Under what conditions does a positive admission score imply a smaller performance gap after retraining? If no such result is intended, could the claims be refined accordingly?

Q2. How are reference actions obtained at the visited partial states, and how much improvement remains without them? Missing one reference optimum does not imply a coverage gap when another optimal action is covered. How is this case handled?

Q3. Could the efficiency comparison include reference-solution preparation and off-pool evaluation, with matched information access? Would the main conclusion remain with standard POMO decoding under a matched inference budget?

4 comments
AuthorsOpenReview ↗

Response by Authors [1/2]

Thank you for your time and effort in reviewing our manuscript and providing constructive feedback. We address each point below, and have incorporated the related clarifications and additional results in our revised manuscript.

W1, Q1. Theoretical results and admission criterion (12).

Thank you for this insightful feedback. As you correctly point out, Proposition 2 is established under the assumptions stated in Section 3.3 and Appendix A.3, and we agree that an increasing upper bound does not necessarily imply an actual increase in the training error. Our admission criterion (12) is a motivated surrogate designed to capture the qualitative trade-off suggested by the suboptimality decomposition (9), rather than a rigorous guarantee of performance improvement.

In response to your concern, we have also examined finite-sample analyses of policy-gradient methods to see how they relate to the K\sqrt{K}-dependence in admission criterion (12). Xiao (2022) establishes a sample-complexity bound for policy mirror descent, including natural policy gradient, whose dependence on the number of actions and target accuracy is O~(K/ϵ2)\widetilde{O}(K/\epsilon^2) when other problem-dependent factors are held fixed [1]. This also corresponds to a O~(K/N)\widetilde{O}(\sqrt{K/N}) error dependence on the sampling budget NN under its assumptions. Mondal and Aggarwal (2024) further provide a finite-sample performance bound of O(N−1/2)O(N^{-1/2}), up to approximation error, for accelerated natural policy gradient under general parameterization and suitable regularity assumptions [2]. These results are qualitatively consistent with our theoretical results, further supporting the motivation of K\sqrt{K}-dependence in our admission criterion (12).

We believe the above discussion also answers your question Q1. The admission criterion in (12) is designed to identify promising candidates by the qualitative trade-off suggested by the suboptimality decomposition (9). We use the selector rollouts as a practical surrogate to approximate the coverage-greedy policy in (7), and a positive admission score indicates a reduction in coverage residual estimation on the sampled states, which does not imply guaranteed global performance improvement after retraining. Our component ablations and gap decomposition results provide empirical support for the rationale and effectiveness of this design. We have added this further discussion in Appendix A.3 and refined the corresponding claims in our revised manuscript.

[1] Xiao, Lin. "On the convergence rates of policy gradient methods." Journal of Machine Learning Research 23.282 (2022): 1-36.

[2] Mondal, Washim U., and Vaneet Aggarwal. "Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward Markov decision processes." International Conference on Artificial Intelligence and Statistics. 2024.

AuthorsOpenReview ↗

Response by Authors [2/2]

W2, Q2, Q3. Implementation, cost, and contribution of reference-miss feedback.

Thank you for raising this point. We apologize for our overly brief description in the original manuscript.

First, we would like to clarify that the offline preparation of reference solutions and actions accounts for a very small fraction of the total training and evolution time. In CoEvoRL, each evolution round uses only 12 reference solutions for diagnostic feedback, which can also be reused across rounds. This cost is very low and affordable in practice, compared to the millions of training samples in common NCO methods. For example, on JSSP 10 × 10 (Table 3 in our manuscript), the reference preparation time is only 0.15 minutes, compared to 24.20 minutes of CoEvoRL and 106.45 minutes of the construction baseline. The wall-clock runtime in Table 3 of our manuscript has already included this time spent preparing the reference solutions.

Second, regarding the construction of reference actions, we apologize for our overly brief description in the original manuscript. Specifically, the reference-miss feedback is applied if the problem structure allows us to translate a given offline solution into a well-defined state-action MDP sequence, e.g., TSP and JSSP in our main experiments. For TSP, we follow the offline reference tour from the starting city, and take each subsequent city as the reference action for the corresponding decision step. For JSSP, we order the operations in the reference schedule by start time while respecting job precedence, then record their corresponding jobs to obtain a reference dispatch sequence. In both tasks, we use the reference action for diagnosis only if it is feasible in the current rollout state, and check coverage against the given single reference action without enumerating all alternative optimal actions (such alternatives are uncommon in fact). We acknowledge that a miss may be a false alarm if another optimal action is covered. Because reference-miss only guides the prompt, such false alarms affect guidance rather than admission.

Third, to address your concern about the contributions of the critic-based residual and reference-action feedback in the diagnosis, we further evaluate two diagnosis-ablation variants: critic-only diagnosis and reference-only diagnosis:

ProblemJSSP 10×10JSSP 15×15JSSP 20×20TSP-20TSP-50TSP-100
CoEvoRL14.09%19.84%22.72%7.12%11.21%13.94%
critic-only14.90%19.93%22.70%7.21%13.43%13.99%
reference-only14.45%20.15%23.50%7.27%12.06%14.75%
w/o diagnosis15.36%20.41%23.23%7.39%14.49%16.20%

Generally, both signals contribute to the performance, and combining them yields the best gap in nearly all settings, suggesting their complementary information in the diagnostic feedback. Notably, the gain of critic-based diagnosis is more significant on larger instances with longer decision sequences, and CoEvoRL still remains advantageous without reference-action feedback. This demonstrates the effectiveness of CoEvoRL in settings where reference solutions are expensive or unavailable. This additional ablation study is provided in Appendix C.6 (Table 12) of our revised manuscript.

W2, Q3. Multi-start decoding of POMO.

Thank you for this constructive comment. Following your suggestion, we further evaluate POMO with multi-start decoding and ×8 inference augmentation, using the model trained with the same budget as CoEvoRL (corresponding to Construct. (Limit)):

SizeTSP-20TSP-50TSP-100
POMO (standard)18.32%40.12%58.58%
POMO (multi-starts)5.98%25.96%44.33%
POMO (multi-starts + ×8 aug)2.46%20.13%37.83%
CoEvoRL7.12%11.21%13.94%

Multi-start decoding and ×8 inference augmentation improve POMO, allowing it to outperform CoEvoRL on TSP-20 at the expense of several times the inference cost. CoEvoRL retains a substantial advantage on TSP-50 and TSP-100 even against POMO with multi-start decoding and ×8 augmentation, supporting its effectiveness under limited training budgets on larger-sized instances.

I would like to thank the authors for providing detailed responses, which address my concerns. Thus, I will keep the score.

Thank you for your positive assessment and feedback. We sincerely appreciate your time and constructive suggestions, which have helped us improve the clarity and completeness of our paper.

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

In this paper, the authors aim to improve the NCO paradigm by addressing two of its weaknesses: computational cost and inefficiency in the selection of actions. To this end, they propose a new framework that incorporates a RL model and an LLM, which, through alternating and iterative processes, aims to achieve better solutions than the standard paradigms in the field of NCO.

Critical strengths
  • This work aims to improve the performance of NCO models, which is a relevant topic that requires further research.
Critical weaknesses
  • The paper is hard to understand. The presentation is very bad. Through the abstract and introduction sections, there are terms such as "pool of heuristics", "suboptimality decomposition", and similar terms that do not make much sense.
  • It is true that the computational cost of NCO models is high during training. However, once trained, if the scenario (the instance-generating distribution) to which the model is applied is static, then its computational cost is very, very low. The inference times for NCO models are in the region of a few seconds. Therefore, one of the initial premises on which this work is based is partially incorrect.
  • The main weakness of the paper is its lack of justification. The authors essentially state that NCO has two problems, and therefore propose an alternative that is better. However, the stumbling block here is that they do not adequately substantiate what the actual problems are, or how they are characterised. This, in turn, affects the assessment of whether CoEvoRL actually represents an improvement.
  • The experimentation lacks rigour. The problem sizes used are very, very small. For example, current NCO models are capable of optimally solving instances of size n=1000 in a matter of seconds, but in this paper, the TSP problem sizes do not exceed n=100. Something similar occurs with the JSSP, and so on. Similarly, whilst each problem in the literature has its own ‘state-of-the-art’ models, here a general selection of competitors is made and CoEvoRL is evaluated against them. If the aim is to validate the framework, it should be compared against the best model for each specific problem.
  • It seems that the authors wish to develop a framework that is the best for all COs, but it is clear that there is no single best model for optimising every problem (NFL theorem, Wolpert and McReady 1997). This is something that ought to be mentioned in the introduction.
  • The bibliography on NCO contains errors. The main reference for NCO is Bello 2016, not Bengio 2021. Furthermore, the overview of the literature on NCO is very poor (for example, no distinction is made between ‘constructive’ and ‘neural improvement’).
  • I do not see any scientific contribution in this work beyond proposing yet another optimisation framework that has not been rigorously validated.
Questions for authors
  • How do the authors justify their claim that NCO suffers from high computational costs, given that inference is typically very efficient once a model has been trained?
  • Why are the experimental instances so small, and why do the authors not compare their framework against state-of-the-art NCO models specifically designed for each problem? Can the reported results substantiate the claimed improvements in NCO?
  • What is the actual scientific contribution of this work beyond proposing another general-purpose optimization framework?
5 comments
AuthorsOpenReview ↗

Response by Authors [1/4]

Overall response and clarification of our contributions.

Thank you for your time and effort in reviewing our manuscript and providing detailed feedback. Your comments highlight the need to explain our research objective and contributions more clearly. We clarify them below, which also serves as our overall response to Weaknesses 2, 4, 7 and Questions 1, 3 raised in your comments.

First, we would like to clarify the central research setting considered in our work: better solution quality under a limited training budget. We agree that, as mentioned in your comments, existing NCO methods can deliver high solution quality and efficient inference once sufficiently trained (Paragraph 2, Introduction). However, our concern is the cost of obtaining such policies: they may require extensive training samples (e.g., real-world or synthetic instances), long training time, and substantial computational resources (e.g., GPU resources), which are often unavailable in real-world practice. We therefore focus on the limited-training-budget setting, where the central challenge is how to achieve better solution quality under a limited training budget. Within this setting, we build on learning heuristic selection, a less explored paradigm in NCO, whose compact action space makes learning sample-efficient but its achievable performance is bounded by the heuristic pool (i.e., "heuristic ceiling"). CoEvoRL leverages the emerging capabilities of LLMs to address this limitation by jointly optimizing the heuristic pool and its learned selector, demonstrating the potential of this paradigm and improving the effectiveness of NCO under limited training budgets. Under the same training budget, the comparison with Construct. (Limit) in Table 1 demonstrates the advantage of CoEvoRL.

Second, our key methodological contribution lies in 1) formulating the limitations of heuristic selection through suboptimality decomposition, 2) developing a closed-loop co-evolution framework to address them, and 3) showing a promising path toward combining the learning efficiency of heuristic selection with solution quality approaching construction policies. Specifically, the suboptimality decomposition separates the gap induced by the restricted action coverage of the heuristic pool, from the finite-sample RL training error of learning a selector (Section 3). Building on this insight, CoEvoRL uses feedback from selector rollouts to identify states where the current pool provides inadequate proposals and guide the evolution of complementary heuristics, and candidates are assessed by their marginal contribution to the existing pool, against the incremental statistical learning cost of pool expansion (Section 4). Our decomposition analysis (Figure 3) and ablation studies (Table 2) provide evidence for this mechanism and its contribution to solution quality under limited training budgets. The experiments demonstrate that, alongside learning construction policies at high training cost for better solution quality, incorporating LLMs with learning heuristic selection offers another promising way to improve solution quality under a limited training budget.

We hope the above clarification can address your concerns about the research setting and contributions of our work. Below we provide detailed point-by-point responses to each comment.

W1. Presentation clarity.

Thank you for your time and effort in reviewing our manuscript. To improve readability, we have added cross-references at the first mention of key terms and our methodology, directing readers to the sections where they are explained in detail. Specifically, for the two terms highlighted in your comments, a heuristic pool is a collection of heuristics (a common term in hyper-heuristics [1, 2]), which propose candidate actions at each decision step for the selector to choose from, while the suboptimality decomposition separates the overall solution gap into an abstraction gap induced by the pool’s restricted action coverage and the RL training error associated with the learned selector, as explained in Paragraph 4, Introduction and Section 3. In the revised manuscript, each term is accompanied by a brief intuitive explanation at its first use.

[1] Burke, Edmund K., et al. "Hyper-heuristics: A survey of the state of the art." Journal of the Operational Research Society 64.12 (2013): 1695-1724.

[2] Soria-Alcaraz, Jorge A., et al. "A methodology for determining an effective subset of heuristics in selection hyper-heuristics." European Journal of Operational Research 260.3 (2017): 972-983.

AuthorsOpenReview ↗

Response by Authors [2/4]

W2, Q1. Background and motivation.

Thank you for raising this point. We agree that sufficiently trained NCO models can provide high-quality solutions with efficient inference. However, as described in our Abstract and Introduction, our central concern is not the inference efficiency, but the computational cost of learning such policies, as discussed in "Overall response and clarification of our contributions". Table 1 in our manuscript shows that L2D and POMO reach high quality with extensive training (Construct. (Full)), but degrade sharply under a limited budget (Construct. (Limit)), e.g., 58.58% vs. 0.77% on TSP-100. Building on this insight, our work focuses on better solution quality under a limited training budget, a setting that is common in real-world optimization, where training instances can be limited or extensive training time and resources (e.g., extensive GPUs) are prohibitive.

To further examine how solution quality depends on training budget and support our claim, we have added solution quality vs. training budget curves in Appendix C.4 (also summarized in the table below), evaluating construction policies with training budgets ranging from 1× to 12× that of CoEvoRL. These results show that additional training improves construction policies, while CoEvoRL achieves better or competitive solution quality with only a smaller training budget. Together, these results provide strong empirical support for the advantages and practical value of CoEvoRL in limited-training-budget settings.

ProblemJSSP 10×10TSP-20MKP-100OBPP-100
CoEvoRL (1×)14.09%7.12%1.32%5.09%
Construct. (1x)22.12%18.32%4.45%7.14%
Construct. (4x)16.43%9.39%4.15%6.95%
Construct. (8x)16.29%8.23%4.11%6.91%
Construct. (12x)17.58%7.58%4.10%6.85%

W3. Justification of design rationale.

Thank you for this comment. We apologize that the original presentation did not make our design rationale sufficiently clear. Our design of CoEvoRL is not to "address two problems", but rather to manage the two terms in the suboptimality decomposition (9) to achieve better overall quality.

We argue that the limitations of existing learning construction policy and learning heuristic selection approaches arise, in part, from addressing only one term in suboptimality (9) without adequately accounting for the other. Specifically, learning construction policies avoid the abstraction gap by directly operating over the primitive decision space, but can incur high learning error due to the huge action space. Conversely, learning heuristic selection restricts the action space and can facilitate learning, but its achievable performance is fundamentally bounded by the coverage of its heuristic pool. Therefore, they emphasize different sides of the trade-off between performance ceiling and learning efficiency.

In contrast, CoEvoRL aims to improve this trade-off, i.e., improving the heuristic ceiling through better pool coverage, while keeping the selection space compact so that learning remains efficient. All components are designed to serve this objective. Figure 3 directly reports these two terms of suboptimality separately during training / evolution, showing that CoEvoRL reduces the abstraction gap while keeping selector learning error manageable, achieving the lowest overall gap. Together with component ablations, these results provide empirical support for our design rationale and show the benefit of jointly optimizing the heuristic pool and RL selector.

AuthorsOpenReview ↗

Response by Authors [3/4]

W4, Q2. Evaluation scale and task-specific baselines.

Thank you for this constructive feedback. First, we respectfully note that, to our knowledge, no current NCO method can establish that instances of TSP-1000 can generally be optimally solved within seconds. Their effectiveness at that scale commonly relies either on heavier training effort (e.g., diffusion-based approaches), which is precisely the cost that motivates our work, or on generalization from training on smaller instances, which typically degrades solution quality as instance size increases.

Second, to demonstrate the effectiveness of CoEvoRL on larger-sized instances, following your suggestion, we evaluate the generalization of CoEvoRL by freezing the evolved heuristic pool and the selector trained on TSP-100 and JSSP 20 × 20, and test directly on larger-sized instances up to TSP-1000 and JSSP 100 × 20, including public benchmarks such as TSPLIB and Taillard JSSP benchmarks. The results are as follows (bold = best among methods under matched training budgets):

ProblemJSSP 30×20JSSP 50×20JSSP 100×20TSP-200TSP-500TSP-1000
Construct. (Full)27.83%17.99%7.28%4.50%34.12%52.84%
Construct. (Limit)33.70%21.92%10.21%85.99%130.35%172.35%
Best Heur.30.76%16.97%7.35%28.47%26.17%25.14%
EoH31.05%18.00%7.57%25.06%24.43%24.41%
Fixed Pool27.54%17.30%7.76%23.28%22.95%23.72%
HeurAgenix26.89%17.24%7.24%19.21%20.58%22.48%
CoEvoRL (Ours)26.62%16.71%7.02%17.10%18.27%20.48%
Taillard Bench.15 × 1520 × 1520 × 2030 × 1530 × 2050 × 1550 × 20100 × 20
Construct. (Full)22.16%27.99%24.55%29.11%33.78%20.84%23.49%15.15%
Construct. (Limit)28.82%30.83%34.22%34.28%37.47%23.07%25.86%16.16%
Best Heur.23.94%31.42%27.39%31.21%31.13%20.67%23.93%13.57%
EoH25.40%31.66%28.61%30.86%31.70%20.82%24.33%13.29%
Fixed Pool21.89%27.41%25.17%28.70%30.89%21.01%23.28%13.47%
HeurAgenix21.19%26.36%23.78%28.46%29.95%20.67%22.77%13.18%
CoEvoRL (Ours)21.01%26.49%23.57%28.26%29.45%21.20%22.33%13.17%
TSPLIB Bench.50-100100-200200-500500-10001000-2000
Construct. (Full)1.88%6.08%26.13%43.77%78.08%
Construct. (Limit)51.96%71.47%109.35%143.64%205.61%
Best Heur.25.25%23.38%23.88%27.84%25.94%
EoH21.92%21.29%22.78%26.31%24.81%
Fixed Pool19.49%18.49%22.69%25.12%23.59%
HeurAgenix15.57%16.06%19.92%22.42%23.00%
CoEvoRL (Ours)14.97%15.40%18.81%21.73%21.88%

CoEvoRL shows strong generalization, achieving the best solution quality in nearly all settings. Notably, as the instance size grows, the advantage of learning heuristic selection approaches becomes more significant. The gaps of Construct. (Full) grow from 0.77% to 52.84% when generalizing from TSP-100 to TSP-1000, while CoEvoRL remains stably effective across a range of larger instance sizes (20.48% on TSP-1000). The results precisely highlight the advantage of CoEvoRL over learning construction policy, the major paradigm of current NCO methods, in generalizing to larger-sized instances.

Finally, regarding the choice of NCO baselines, we agree that each problem has specialized methods that advance the state of the art, but they generally require heavier models and training efforts to achieve improved solution quality. As clarified in "Overall response and clarification of our contributions", our particular focus is the trade-off between solution quality and training cost, namely, achieving better solutions under limited training budgets. We do not claim that CoEvoRL universally surpasses the best NCO methods while using only a fraction of their training resources. We therefore choose task-specific construction models that are among the most established and representative for their respective problems: L2D for JSSP, POMO for TSP, RL-to-Rank for MKP, and ORL for OBPP. We evaluate them under both their full training budgets (Construct. (Full)) and a matched training budget (Construct. (Limit)), allowing us to fairly compare the performance with substantial training and under budget constraints. We have added this scope statement to our revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.