Research map / Learning theory and algorithms / Combinatorial and search optimization

Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policies

NeurIPS 2026 · Learning theory and algorithms › Combinatorial and search optimization · approach: Unsupervised neural combinatorial optimization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a teacher-aware LLM evolutionary framework that queries independently trained learned optimization policies on states visited by candidate heuristics, using teacher action agreement as a second Pareto objective, yielding static heuristics for JSSP, TSP, CVRP and MaxCut.

Problem

LLM-based automatic heuristic design relies on delayed endpoint performance and textual or population feedback, ignoring action-level behavioral information from learned combinatorial optimization policies.

Approach

Treat independently trained neural policies as behavioral teachers: query them on states visited by candidate programs, measure top-1 action agreement as a second objective, and use disagreement cases to guide analyzer-driven revision and Pareto-based population retention, while the final heuristic is selected by task objective and needs no neural inference.

Key results

• JSSP 20x20 makespan 1812.15 for the proposed method vs 1866.92 for EoH and 1867.06 for ReEvo.
• TSP50 tour length 6.387 vs 6.912 (EoH) and 7.014 (ReEvo); TSP200 12.250 vs 13.520 (EoH).
• CVRP50 route length 9.671 vs 9.689 (EoH) and 10.056 (ReEvo); the margin over EoH is small.

Surprising findings

• Max-align selection (choosing the final program by teacher agreement) is not consistently better than the full method, and is slightly better on JSSP OOD and TSP in-domain.
• On MaxCut, the method is not uniformly faster than performance-only evolution and is slower on several settings (e.g., BA200w 43.41s vs 16.40s for EoH).

Limitations

• Requires an alignable learned teacher and a task-specific interface adapter.
• Requires analyzer LLM calls in addition to program generation.
• Runtime overhead on some MaxCut settings and the method is not uniformly better (e.g., ER800u).

Experimental setup

Datasets: randomly generated JSSP 20x20 design instances TSP50 design instances CVRP50 design instances BA200w weighted Barabasi-Albert graphs

Benchmarks: JSSP random 10x10/15x15/20x20 Taillard 20x20/30x20 TSP50/TSP200/TSPLIB70 CVRP50/CVRP200/VRPLIB192 MaxCut BA/ER/Physics graphs

Metrics: makespan tour length route length cut value runtime

Baselines: EoH ReEvo SPT MWKR FDD-MWKR MOR L2D Offline-LD LEHD LKH ECO-DQN

Builds on: EoH ReEvo FunSearch MEoH LEHD

Closest papers by meaning

• PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.88)
• RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience (ICML 2026 · similarity 0.88)
• Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks (NeurIPS 2026 · similarity 0.87)
• Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces (NeurIPS 2026 · similarity 0.86)
• ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution (NeurIPS 2024 · similarity 0.86)
• DesignX: Human-Competitive Algorithm Designer for Black-Box Optimization (NeurIPS 2025 · similarity 0.85)