Foundation Models for Combinatorial Optimization

FM4CO contains interesting research papers (1) using Existing Large Language Models for Combinatorial Optimization, and (2) building Domain Foundation Models for Combinatorial Optimization.

LLMs for Combinatorial Optimization

Most research utilizes existing FMs from language and vision domains to generate/improve solutions* or algorithms* (hyper-heuristic), yielding impressive results when integrated with problem-specific heuristics or general meta-heuristics. Other studies employ LLMs to investigate the interpretability* of COP solvers, automate problem formulation*, or simplify the use of domain-specific tools through text prompts. Given the capabilities of LLMs, this area of research is likely to garner increasing interest.

| Date | Paper | Link | Problem | Venue | Remark* | | :-----: | :----------------------------------------------------------: | :----------------------------------------------------------: | :-------------------: | :------------: | :--------------: | | 2023.07 | Large Language Models for Supply Chain Optimization | | Supply_Chain | arXiv | Algorithm w. Interpretability | | 2023.09 | Can Language Models Solve Graph Problems in Natural Language? | | Graph | NeurIPS 2023 | Solution | | 2023.09 | Large Language Models as Optimizers | | TSP | ICLR 2024 | Solution | | 2023.10 | Chain-of-Experts: When LLMs Meet Complex Operations Research Problems | | MILP | ICLR 2024 | Formulation | | 2023.10 | OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models | | MILP | ICML 2024 | Formulation | | 2023.10 | AI-Copilot for Business Optimisation: A Framework and A Case Study in Production Scheduling | | JSSP | arXiv | Formulation | | 2023.11 | Large Language Models as Evolutionary Optimizers | | TSP | CEC 2024 | Solution | | 2023.11 | Algorithm Evolution Using Large Language Model |     | TSP | arXiv | Algorithm | | 2023.12 | Mathematical discoveries from program search with large language models | | BPP | Nature | Algorithm | | 2023.12 | NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes | | TSP,KP, GCP,MSP | ACL 2024 | Benchmark | | 2024.02 | ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution |
| TSP,VRP,OP, MKP,BPP,EDA | NeurIPS 2024 | Algorithm | | 2024.02 | AutoSAT: Automatically Optimize SAT Solvers via Large Language Models | | SAT | arXiv | Algorithm | | 2024.02 | From Large Language Models and Optimization to Decision Optimization CoPilot: A Research Manifesto | | MILP | arXiv | Formulation | | 2024.03 | How Multimodal Integration Boost the Performance of LLM for Optimization: Case Study on Capacitated Vehicle Routing Problems | | VRP | arXiv | Solution | | 2024.03 | RouteExplainer: An Explanation Framework for Vehicle Routing Problem |
| VRP | PAKDD 2024 | Interpretability | | 2024.03 | Can Large Language Models Solve Robot Routing? |
| TSP,VRP | arXiv | Algorithm | | 2024.05 | Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model | | TSP,BPP,FSSP | ICML 2024 | Algorithm | | 2024.05 | ORLM: Training Large Language Models for Optimization Modeling | | General OPT | Operations Research | Formulation | | 2024.05 | Self-Guiding Exploration for Combinatorial Problems | | TSP,VRP,BPP, AP,KP,JSSP | NeurIPS 2024 | Solution | | 2024.06 | Eyeballing Combinatorial Problems: A Case Study of Using Multimodal Large Language Models to Solve Traveling Salesman Problems | | TSP | ISBCom 2024 | Solution | | 2024.07 | Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial Challenges | | TSP,mTSP | arXiv | Solution | | 2024.07 | Solving General Natural-Language-Description Optimization Problems with Large Language Models | | MILP | NAACL 2024 | Formulation | | 2024.08 | Diagnosing Infeasible Optimization Problems Using Large Language Models | | MILP | INFOR | Formulation | | 2024.08 | LLMs can Schedule | | JSSP | arXiv | Solution | | 2024.09 | Multi-objective Evolution of Heuristic Using Large Language Model | | TSP,BPP | AAAI 2025 | Algorithm | | 2024.10 | Towards Foundation Models for Mixed Integer Linear Programming | | MILP | ICLR 2025 | Formulation | | 2024.10 | LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch | | General OPT | ICLR 2025 | Formulation | | 2024.10 | OptiBench: Benchmarking Large Language Models in Optimization Modeling with Equivalence-Detection Evaluation | | MILP | Under Review | Benchmark | | 2024.10 | OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling | | MILP | ICLR 2025 | Benchmark | | 2024.10 | DRoC: Elevating Large Language Models for Complex Vehicle Routing via Decomposed Retrieval of Constraints | | 48VRPs | ICLR 2025 | Formulation | | 2024.10 | STARJOB: Dataset for LLM-Driven Job Shop Scheduling | | JSSP | Under Review | Solution | | 2024.10 | LLM4Solver: Large Language Model for Efficient Algorithm Design of Combinatorial Optimization Solver | | MILP | Under Review | Algorithm | | 2024.10 | Unifying All Species: LLM-based Hyper-Heuristics for Multi-objective Optimization | | TSP | Under Review | Algorithm | | 2024.10 | Evo-Step: Evolutionary Generation and Stepwise Validation for Optimizing LLMs in OR | | MILP | Under Review | Formulation | | 2024.10 | Automatic programming via large language models with population self-evolution for dynamic job shop scheduling problem | | DyJSSP | arXiv | Algorithm | | 2024.11 | Large Language Models for Combinatorial Optimization of Design Structure Matrix | | DSM | arXiv | Solution | | 2024.12 | HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs | | TSP,BPP,OP | AAAI 2025 | Algorithm | | 2024.12 | Evaluating LLM Reasoning in the Operations Research Domain with ORQA | | General OR | AAAI 2025 | Benchmark | | 2024.12 | QUBE: Enhancing Automatic Heuristic Design via Quality-Uncertainty Balanced Evolution | | OBP,TSP,CSP | arxiv | Algorithm | | 2025.01 | Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design | | TSP,CVRP,KP, BPP,MKP,ASP | ICML 2025 | Algorithm | | 2025.01 | Bridging Visualization and Optimization: Multimodal Large Language Models on Graph-Structured Combinatorial Optimization || Influence Maximization, Network Dismantling | arXiv | Algorithm | | 2025.01 | Can Large Language Models Be Trusted as Black-Box Evolutionary Optimizers for Combinatorial Problems? || Influence Maximization | arXiv | Algorithm | | 2025.02 | Improving Existing Optimization Algorithms with LLMs || MIS | arXiv | Algorithm | | 2025.02 | Planning of Heuristics: Strategic Planning on Large Language Models with Monte Carlo Tree Search for Automating Heuristic Optimization || TSP,FSSP | arXiv | Algorithm | | 2025.02 | GraphThought: Graph Combinatorial Optimization with Thought Generation || MIS,MVC,TSP | arXiv | Algorithm | | 2025.02 | EquivaMap: Leveraging LLMs for Automatic Equivalence Checking of Optimization Formulations || MILP | arXiv | Algorithm | | 2025.02 | ARS: Automatic Routing Solver with Large Language Models || VRP | arXiv | Benchmark & Algorithm | | 2025.02 | Text2Zinc: A Cross-Domain Dataset for Modeling Optimization and Satisfaction Problems in MiniZinc | | LP,MIP,CP | arXiv | Formulation (Dataset) | | 2025.02 | GraphArena: Evaluating and Exploring Large Language Models on Graph Computation | | MVC,MIS,MCP, TSP,MCS,GED | ICLR 2025 | Benchmark & Dataset & Model| | 2025.03 | Leveraging Large Language Models to Develop Heuristics for Emerging Optimization Problems || UPMP | arXiv | Algorithm | | 2025.03 | OR-LLM-Agent: Automating Modeling and Solving of Operations Research Optimization Problem with Reasoning Large Language Model || OP | arXiv | Formulation | | 2025.03 | Combinatorial Optimization for All: Using LLMs to Aid Non-Experts in Improving Optimization Algorithms |
| TSP | arXiv | Algorithm | | 2025.03 | Automatic MILP Model Construction for Multi-Robot Task Allocation and Scheduling Based on Large Language Models || MILP | arXiv | Formulation | | 2025.03 | Code Evolution Graphs: Understanding Large Language Model Driven Design of Algorithms || BBO,TSP,BPP | arXiv | Interpretability | | 2025.04 | CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization || General COP | arXiv | Benchmark | | 2025.04 | Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning || BPP,TSP,FP | arXiv | Algorithm | | 2025.04 | OptimAI: Optimization from Natural Language Using LLM-Powered AI Agents || MILP | arXiv | Formulation | | 2025.04 | Fitness Landscape of Large Language Model-Assisted Automated Algorithm Search || OBP,TSP, CVRP,VRPTW | arXiv | Benchmark & Interpretability | | 2025.04 | Large Language Models powered Neural Solvers for Generalized Vehicle Routing Problems || VRP | ICLR 2025 Workshop AgenticAI | Algorithm | | 2025.05 | Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models || TSP,CVRP,BPP, MKP,OP | KDD 2025 | Algorithm | | 2025.05 | CALM: Co-evolution of Algorithms and Language Model for Automatic Heuristic Design || TSP,KP,OBP,OP | arXiv | ALgorithm | | 2025.05 | Know the Ropes: A Heuristic Strategy for LLM-based Multi-Agent System Design || KP | arXiv | Solution | | 2025.05 | A Comprehensive Evaluation of Contemporary ML-Based Solvers for Combinatorial Optimization | | MIS,MDS, TSP,CVRP,CFLP, CPMP,FJSP,STP | arXiv | Benchmark | | 2025.05 | RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language Models || TSP,CVRP, KP,BPP,MKP | arXiv | Algorithm | | 2025.05 | Generalizable Heuristic Generation Through Large Language Models with Meta-Optimization || TSP,CVRP,BPP | arXiv | Algorithm | | 2025.05 | Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems | | MILP | ICML 2025 | Algorithm | | 2025.06 | EALG: Evolutionary Adversarial Generation of Language Model–Guided Generators for Combinatorial Optimization || TSP,OP | arXiv | Algorithm | | 2025.06 | CP-Bench: Evaluating Large Language Models for Constraint Modelling || CP | arXiv | Benchmark | | 2025.06 | REMoH: A Reflective Evolution of Multi-objective Heuristics approach via Large Language Models || FJSSP | arXiv | Algorithm | | 2025.06 | HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization || TSP,SAT | arXiv | Benchmark | | 2025.06 | ALE-Bench: A Benchmark for Long-Horizon Objective-Driven Algorithm Engineering |
| General OPT | arXiv | Benchmark | | 2025.06 | OPT-BENCH: Evaluating LLM Agent on Large-Scale Search Spaces Optimization Problems |
| GCP,KP,MCP, MIS,SCP,TSP | arXiv | Benchmark | | 2025.06 | STRCMP: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization || SAT | arXiv | Solution | | 2025.06 | HeurAgenix: Leveraging LLMs for Solving Complex Combinatorial Optimization Challenges | | TSP,CVRP,JSSP, MaxCut,MKP | arXiv | Algorithm | | 2025.07 | Large Language Models for Combinatorial Optimization: A Systematic Review || CO | arXiv | Review | | 2025.07 | DHEvo: Data-Algorithm Based Heuristic Evolution for Generalizable MILP Solving || MILP | arXiv | Algorithm | | 2025.07 | MeLA: A Metacognitive LLM-Driven Architecture for Automatic Heuristic Design || TSP,BPP,ACS | arXiv | Algorithm | | 2025.07 | Pareto-Grid-Guided Large Language Models for Fast and High-Quality Heuristics Design in Multi-Objective Combinatorial Optimization || TSP,CVRP,KP | arXiv | Algorithm | | 2025.07 | Automatically discovering heuristics in a complex SAT solver with large language models || SAT | arXiv | Algorithm | | 2025.07 | Nested-Refinement Metamorphosis: Reflective Evolution for Efficient Optimization of Networking Problems || TSP,MKP,CVRP | ACL 2025 | Algorithm | | 2025.08 | ReflecSched: Solving Dynamic Flexible Job-Shop Scheduling via LLM-Powered Hierarchical Reflection || DFJSP | arxiv | Solution | | 2025.08 | OptiHive: Ensemble Selection for LLM-Based Optimization via Statistical Modeling || MDVRP,WSCP | arxiv | Formulation | | 2025.08 | EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design || OBP,TSP,CVRP | arxiv | Algorithm | | 2025.08 | X-evolve: Solution space evolution powered by large language models || CSP,BPP, Shannon capacity | arxiv | Algorithm | | 2025.08 | EvoCut: Strengthening Integer Programs via Evolution-Guided Language Models || MILP | arxiv | Formulation | | 2025.08 | HIFO-PROMPT: Prompting with Hindsight and Foresight For LLM-Based Automatic Heuristic Design || TSP,OBP,FSSP | arxiv | Algorithm | | 2025.09 | LLM-QUBO: An End-to-End Framework for Automated QUBO Transformation from Natural Language Problem Descriptions || MILP | arxiv | Formulation |

Domain FMs for Combinatorial Optimization

Developing a domain FM capable of solving a wide range of COPs presents an intriguing and formidable challenge. Recent efforts in this area aim towards this ambitious goal by creating a unified architecture or representation applicable across various COPs.

| Date | Paper | Link | Problem | Venue | | :-----: | :----------------------------------------------------------: | :----------------------------------------------------------: | :--------------------------------------: | :----------: | | 2022.08 | One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction | | CSP | IJCAI 2023 | | 2023.05 | Efficient Training of Multi-task Combinatorial Neural Solver with Multi-armed Bandits |     | TSP,VRP,OP,KP | TMLR | | 2024.02 | Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot Generalization | | 16VRPs | KDD 2024 | | 2024.03 | Towards a Generic Representation of Combinatorial Problems for Learning-Based Approaches | | SAT,TSP,COL,KP | CPAIOR 2024 | | 2024.04 | Cross-Problem Learning for Solving Vehicle Routing Problems | | TSP,OP,PCTSP | IJCAI 2024 | | 2024.05 | MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts | | 16VRPs | ICML 2024 | | 2024.06 | RouteFinder: Towards Foundation Models for Vehicle Routing Problems |
| 24VRPs | ICML 2024 Workshop on FM | | 2024.06 | GOAL: A Generalist Combinatorial Optimization Agent Learner | | (A)TSP,5VRPs,OP,JSSP, OSSP,UMSP,KP,MVC, MIS,MCLP,TRP,SOP | ICLR 2025 | | 2024.08 | UNCO: Towards Unifying Neural Combinatorial Optimization through Large Language Model | | TSP,CVRP,KP, MVCP,SMTWTP | arXiv | | 2024.09 | MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale | | MAPF | AAAI 2025 | | 2024.10 | Toward Learning Generalized Cross-Problem Solving Strategies for Combinatorial Optimization | | TSP,VRP,SDVRP, OP,PCTSP,SPCTSP | Under Review | | 2024.10 | Learning General Representations Across Graph Combinatorial Optimization Problems | | 7GDPs | Under Review | | 2024.10 | Solving Diverse Combinatorial Optimization Problems with a Unified Model | | (A)TSP,CVRP,OP,PCTSP, SPCTSP,KP,MIS,FFSP | Under Review | | 2024.10 | SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity & Hierarchy in Efficiently Layered Decoder | | 16VRPs | ICML 2025 | | 2024.10 | Unified Neural Solvers for General TSP and Multiple Combinatorial Optimization Tasks via Problem Reduction and Matrix Encoding | | (A)TSP,DHCP,3SAT | ICLR 2025 | | 2024.10 | Foundation Models for Boolean Logic | | Boolean Logic | Under Review | | 2024.11 | CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention | | 16VRPs | ICML 2025 | | 2024.12 | Multi-task Representation Learning for Mixed Integer Linear Programming | | MILP | arXiv | | 2025.05 | A Mixed-Curvature based Pre-training Paradigm for Multi-Task Vehicle Routing Solver | | VRP | ICML 2025 | | 2025.07 | LRM-1B: Towards Large Routing Model || VRP | arxiv | | 2025.08 | FORGE: Foundational Optimization Representations from Graph Embeddings || MIP | arxiv |