Rethinking LLM-Driven Heuristic Design: Generating Efficient and Specialized Solvers via Dynamics-Aware Optimization

A research team including Rongzheng Wang, Yihong Huang, and others has published a paper introducing DASH (Dynamics-Aware Solver Heuristics), a novel framework that fundamentally improves how Large Language Models (LLMs) are used to generate heuristics for combinatorial optimization problems. Current LLM-Driven Heuristic Design (LHD) methods suffer from 'endpoint-only evaluation,' which ignores the solver's convergence process and runtime, and 'high adaptation costs,' requiring expensive re-training for new problem instances. DASH tackles this by co-optimizing the solver's internal search mechanisms and its runtime schedule, guided by a new metric that evaluates the entire convergence dynamics, not just the final result.

Furthermore, DASH incorporates a Profiled Library Retrieval (PLR) system, which archives specialized solvers created during the evolutionary process. When faced with a new problem instance, DASH can retrieve a similar, pre-optimized solver from this library for a 'warm start,' drastically reducing the need to restart adaptation from scratch. The team validated DASH on four distinct combinatorial optimization problems. The results showed DASH improves runtime efficiency by over 4 times compared to prior LHD baselines while maintaining or improving solution quality. Crucially, by enabling these profile-aware warm starts, DASH maintained performance under distribution shifts while slashing the costly LLM adaptation process by approximately 90%.