Comparative Evaluation of Prompting Strategies for LLM-Based Combinatorial Optimization

Abstract

Large Language Models (LLMs) demonstrate remarkable performance on natural language understanding tasks but struggle with mathematical optimization problems, primarily due to calculation hallucinations and constraint tracking failures. The LLM-based Formalized Programming (LLMFP) framework addresses the above problems by shifting the role of the LLM from a solver to a translator that converts the natural language problems into executable Python code utilizing the Z3 solver. While the framework achieves up to 95% accuracy, its monolithic design introduces limitations such as error propagation, the lack of validation between stages, and parsing difficulties. Error analysis shows that the majority of LLMFP failures are due to formatting and parsing issues rather than reasoning errors. This paper presents the Parser-CoderValidator (PCV) technique, a three-stage modular architecture. The technique decomposes the optimization problem into three stages. First, we establish a new baseline through a comprehensive comparative analysis of the performance of the four state-of-the-art LLMs (GPT-OSS-20B, GPT-OSS-120B, Gemini 2.5 Flash, Grok-Code-Fast-1) on 687 optimization problems across three problem domains: Coffee Supply Chain, Facility Location, and Workforce Scheduling. We then present a comparison of several prompting strategies, demonstrating that PCV achieves up to 39.71% overall accuracy improvements over the LLMFP baseline, with the most dramatic gains in Facility Location. The results underscore the significance of the PCV framework, which demonstrates that careful design of the prompting and validation process is as critical as model selection for achieving reliable LLM-based optimization.