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	arXiv	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	arXiv	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	arXiv	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	Large Language Model-driven Large Neighborhood Search for Large-Scale MILP Problems		MILP	Under Review	Algorithm
2024.10	HeurAgenix: A Multi-Agent LLM-Based Paradigm for Adaptive Heuristic Evolution and Selection in Combinatorial Optimization		TSP,CVRP,JSSP, MaxCut,MKP	Under Review	Algorithm
2024.10	Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language Models		TSP,CVRP, BPP,MKP	Under Review	Algorithm
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
2025.01	Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design		TSP,CVRP,KP, BPP,MKP,ASP	arXiv	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.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

---

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	arXiv
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	arXiv
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	arXiv
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	arXiv
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	Under Review
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.11	CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention		16VRPs	arXiv
2024.12	Multi-task Representation Learning for Mixed Integer Linear Programming		MILP	arXiv