Large Language Models for Combinatorial Optimization: A Systematic Review
arXiv:2507.03637 · doi:10.1145/3801961
Abstract
This systematic review explores the application of Large Language Models (LLMs) in Combinatorial Optimization (CO). We report our findings using the Preferred Reporting Items for Systematic Reviews and Meta-Analyses (PRISMA) guidelines. We conduct a literature search via Scopus and Google Scholar, examining over 2,000 publications. We assess publications against four inclusion and four exclusion criteria related to their language, research focus, publication year, and type. Eventually, we select 103 studies. We classify these studies into semantic categories and topics to provide a comprehensive overview of the field, including the tasks performed by LLMs, the architectures of LLMs, the existing datasets specifically designed for evaluating LLMs in CO, and the field of application. Finally, we identify future directions for leveraging LLMs in this field.
References in corpus (96)
- LLaMA: Open and Efficient Foundation Language Models
- Llama 2: Open Foundation and Fine-Tuned Chat Models
- LoRA: Low-Rank Adaptation of Large Language Models
- BERTScore: Evaluating Text Generation with BERT
- pymoo: Multi-objective Optimization in Python
- A Survey on Large Language Model based Autonomous Agents
- Sparks of Artificial General Intelligence: Early experiments with GPT-4
- Large Language Models are Zero-Shot Reasoners
- Emergent Abilities of Large Language Models
- Gemini: A Family of Highly Capable Multimodal Models
- Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models
- Code Llama: Open Foundation Models for Code
- Mistral 7B
- Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context
- BART: Denoising Sequence-to-Sequence Pre-training for Natural Language Generation, Translation, and Comprehension
- StarCoder: may the source be with you!
- GPT Models in Construction Industry: Opportunities, Limitations, and a Use Case Validation
- Gemma 2: Improving Open Language Models at a Practical Size
- Mixtral of Experts
- DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model
- Large Language Models as Optimizers
- DeepSeek LLM: Scaling Open-Source Language Models with Longtermism
- DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models
- Metaheuristics "In the Large"
- Biased Random-Key Genetic Algorithms: A Review
- StarCoder 2 and The Stack v2: The Next Generation
- Zephyr: Direct Distillation of LM Alignment
- Towards Next-Generation Urban Decision Support Systems through AI-Powered Construction of Scientific Ontology using Large Language Models -- A Case in Optimizing Intermodal Freight Transportation
- A Survey of Optimization-based Task and Motion Planning: From Classical To Learning Approaches
- DeepSeek-Coder-V2: Breaking the Barrier of Closed-Source Models in Code Intelligence
- Yi: Open Foundation Models by 01.AI
- Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them
- Accelerating Material Design with the Generative Toolkit for Scientific Discovery
- Large Language Models for Supply Chain Optimization
- Open-TI: Open Traffic Intelligence with Augmented Language Model
- Large Language Model for Multi-objective Evolutionary Optimization
- Algorithm Evolution Using Large Language Model
- Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model
- Talk like a Graph: Encoding Graphs for Large Language Models
- NL4Opt Competition: Formulating Optimization Problems Based on Their Natural Language Descriptions
- Metaheuristics and Large Language Models Join Forces: Toward an Integrated Optimization Approach
- Evolutionary Computation in the Era of Large Language Model: Survey and Roadmap
- Large Language Models as Evolutionary Optimizers
- Towards Optimizing with Large Language Models
- A Survey in Mathematical Language Processing
- Camels in a Changing Climate: Enhancing LM Adaptation with Tulu 2
- TRIP-PAL: Travel Planning with Guarantees by Combining Large Language Models and Automated Planners
- RouteExplainer: An Explanation Framework for Vehicle Routing Problem
- How Multimodal Integration Boost the Performance of LLM for Optimization: Case Study on Capacitated Vehicle Routing Problems
- OpenCoder: The Open Cookbook for Top-Tier Code Large Language Models
- Linear programming word problems formulation using EnsembleCRF NER labeler and T5 text generator with data augmentations
- Holy Grail 2.0: From Natural Language to Constraint Models
- Artificial Intelligence for Operations Research: Revolutionizing the Operations Research Process
- VTCC-NLP at NL4Opt competition subtask 1: An Ensemble Pre-trained language models for Named Entity Recognition
- How Susceptible are LLMs to Influence in Prompts?
- Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents
- Pivoting Retail Supply Chain with Deep Generative Techniques: Taxonomy, Survey and Insights
- Language Models for Business Optimisation with a Real World Case Study in Production Scheduling
- Deep Insights into Automated Optimization with Large Language Models and Evolutionary Algorithms
- A Novel Approach for Auto-Formulation of Optimization Problems
- OptiMUS-0.3: Using Large Language Models to Model and Solve Optimization Problems at Scale
- Tag Embedding and Well-defined Intermediate Representation improve Auto-Formulation of Problem Description
- Exploring the True Potential: Evaluating the Black-box Optimization Capability of Large Language Models
- Can Large Language Models Solve Robot Routing?
- 20 years of Greedy Randomized Adaptive Search Procedures with Path Relinking
- Towards Foundation Models for Mixed Integer Linear Programming
- Learning to Deliver: a Foundation Model for the Montreal Capacitated Vehicle Routing Problem
- Synthesizing mixed-integer linear programming models from natural language descriptions
- A Systematic Survey on Large Language Models for Algorithm Design
- Identify Critical Nodes in Complex Network with Large Language Models
- DCP-Bench-Open: Evaluating LLMs for Constraint Modelling of Discrete Combinatorial Problems
- Evaluating LLM Reasoning in the Operations Research Domain with ORQA
- Combining Constraint Programming Reasoning with Large Language Model Predictions
- Towards an Automatic Optimisation Model Generator Assisted with Generative Pre-trained Transformer
- A bi-objective -constrained framework for quality-cost optimization in language model ensembles
- Planning Anything with Rigor: General-Purpose Zero-Shot Planning with LLM-based Formalized Programming
- Highlighting Named Entities in Input for Auto-Formulation of Optimization Problems
- OPD@NL4Opt: An ensemble approach for the NER task of the optimization problem
- Multi-objective Evolution of Heuristic Using Large Language Model
- GraphWiz: An Instruction-Following Language Model for Graph Problems
- LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?
- Navigating the Labyrinth: Evaluating LLMs' Ability to Reason About Search Problems
- Text2Zinc: A Cross-Domain Dataset for Modeling Optimization and Satisfaction Problems in MiniZinc
- From Large Language Models and Optimization to Decision Optimization CoPilot: A Research Manifesto
- Exploring and Benchmarking the Planning Capabilities of Large Language Models
- GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability
- LLMs for Mathematical Modeling: Towards Bridging the Gap between Natural and Mathematical Languages
- OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling
- LLMs for Cold-Start Cutting Plane Separator Configuration
- TS-EoH: An Edge Server Task Scheduling Algorithm Based on Evolution of Heuristic
- AutoRNet: Automatically Optimizing Heuristics for Robust Network Design via Large Language Models
- LLM4AD: A Platform for Algorithm Design with Large Language Model
- MindOpt Tuner: Boost the Performance of Numerical Software by Automatic Parameter Tuning
- GraphTeam: Facilitating Large Language Model-based Graph Analysis via Multi-Agent Collaboration
- The Case for Developing a Foundation Model for Planning-like Tasks from Scratch
- QUBE: Enhancing Automatic Heuristic Design via Quality-Uncertainty Balanced Evolution