Advances in LLM-Assisted Combinatorial Optimization

Combinatorial optimization (CO) concerns decision-making over discrete solution spaces under constraints and lies at the core of many complex systems across science, engineering, and society. Yet current approaches to solving CO problems still rely heavily on expert-designed solvers and manual tuning. Large language models (LLMs), trained on massive corpora, offer a promising new avenue for enhancing CO solution methods with stronger capabilities for generalization and adaptation in complex or previously unseen scenarios. Some existing surveys provide high-level taxonomies without examining solver-level methods, while others focus narrowly on specific perspectives. To fill this gap, we present a methodology-oriented synthesis of recent LLM-assisted CO work, covering three mainstream solution paradigms: mathematical programming, heuristics, and end-to-end solvers. We first develop a hierarchical taxonomy that groups existing methods by solution paradigm and, within each paradigm, further classifies them by the workflow stage and the interaction pattern through which LLMs engage with the solver. We then formalize the workflow of each paradigm, clarify the functional role of LLMs, and analyze the core techniques in key modules. We further summarize the problem domains studied in the literature and discuss representative applications. Finally, we identify current limitations and outline future directions in architecture, methodology, and problem scope.