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

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.