Large Language Models for Metaheuristic Implementation: A Case Study with Variable Neighborhood Search
Abstract
Metaheuristics are widely used in combinatorial optimization to address large-scale problems but often require considerable expertise and engineering effort. In this paper, we investigate whether recent large language models (LLMs) can translate state-of-the-art algorithmic descriptions into performant code with minimal human intervention. We introduce a generalizable prompting framework: Context, Communication, and Iteration (CCI), and apply it to replicate a Variable Neighborhood Search for the balanced minimum sum-of-squares clustering problem using Gemini 2.5 Pro and Claude Sonnet 4. According to our computational experiments, Gemini achieved solutions with a mean difference of 0.032% from the reference implementation (median: 0.009%), being statistically non-inferior within a 0.01% margin. Notably, Gemini corrected a missing mathematical term in the neighborhood evaluation formula described in the source paper, whereas Claude did not. Our findings suggest that LLM-assisted engineering is a viable pathway to facilitate algorithm replication, making high-performance methods more accessible to researchers and allowing them to tackle larger and more complex problems.
