LLM 기반 휴리스틱 설계 재고: 동적 특성 인지 최적화를 통한 효율적이고 특화된 솔버 생성

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

대규모 언어 모델(LLM)은 자동화된 휴리스틱 생성 기능을 통해 조합 최적화 분야를 발전시켰습니다. 기존의 수동 설계 방식에서 벗어나, 본 논문에서 제안하는 LLM 기반 휴리스틱 설계(LHD) 프로세스는 LLM을 활용하여 반복적으로 솔버를 생성하고 개선함으로써 높은 성능을 달성합니다. 그러나 기존의 LHD 프레임워크는 다음과 같은 두 가지 중요한 한계점을 가지고 있습니다. (1) 최종 결과만을 평가하여 솔버를 순위화하며, 수렴 과정 및 실행 시간 효율성을 고려하지 않습니다. (2) 데이터 분포의 변화로 인해 새로운 문제 유형에 대한 특화된 솔버를 생성하기 위해 상당한 재적응 비용이 발생합니다. 이러한 문제를 해결하기 위해, 본 논문에서는 수렴 과정을 고려하는 지표를 기반으로 솔버 탐색 메커니즘과 런타임 스케줄을 동시에 최적화하는 프레임워크인 Dynamics-Aware Solver Heuristics (DASH)를 제안합니다. DASH는 효율적이고 고성능의 솔버를 식별합니다. 또한, 비용이 많이 드는 재적응을 완화하기 위해, DASH는 Profiled Library Retrieval (PLR)을 통합합니다. PLR은 진화 과정과 동시에 특화된 솔버를 효율적으로 저장하고, 다양한 데이터 분포에 대한 비용 효율적인 초기화(warm-start)를 가능하게 합니다. 네 가지 조합 최적화 문제에 대한 실험 결과, DASH는 실행 시간 효율성을 3배 이상 향상시키고, 다양한 문제 규모에서 최첨단 모델보다 우수한 솔루션 품질을 달성했습니다. 또한, 프로파일 기반 초기화를 통해 DASH는 다양한 데이터 분포에서 우수한 정확도를 유지하면서 LLM 적응 비용을 90% 이상 절감합니다.

Large Language Models (LLMs) have advanced the field of Combinatorial Optimization through automated heuristic generation. Instead of relying on manual design, this LLM-Driven Heuristic Design (LHD) process leverages LLMs to iteratively generate and refine solvers to achieve high performance. However, existing LHD frameworks face two critical limitations: (1) Endpoint-only evaluation, which ranks solvers solely by final quality, ignoring the convergence process and runtime efficiency; (2) High adaptation costs, where distribution shifts necessitate re-adaptation to generate specialized solvers for new instance groups. To address these issues, we propose Dynamics-Aware Solver Heuristics (DASH), a framework that co-optimizes solver search mechanisms and runtime schedules guided by a convergence-aware metric, thereby identifying efficient and high-performance solvers. Furthermore, to mitigate expensive re-adaptation, DASH incorporates Profiled Library Retrieval (PLR). PLR efficiently archives specialized solvers concurrently with the evolutionary process, enabling cost-effective warm-starts for heterogeneous distributions. Experiments on four combinatorial optimization problems demonstrate that DASH improves runtime efficiency by over 3 times, while surpassing the solution quality of state-of-the-art baselines across diverse problem scales. Furthermore, by enabling profile-based warm starts, DASH maintains superior accuracy under different distributions while cutting LLM adaptation costs by over 90%.