Home

Awesome

<h1 align="center">Foundation Models for Combinatorial Optimization</h1>

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.

DatePaperLinkProblemVenueRemark*
2023.07Large Language Models for Supply Chain OptimizationCodeSupply_ChainarXivAlgorithm w. Interpretability
2023.09Can Language Models Solve Graph Problems in Natural Language?CodeGraphNeurIPS 2023Solution
2023.09Large Language Models as OptimizersCodeTSPICLR 2024Solution
2023.10Chain-of-Experts: When LLMs Meet Complex Operations Research ProblemsCodeMILPICLR 2024Formulation
2023.10OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language ModelsCodeMILPICML 2024Formulation
2023.10AI-Copilot for Business Optimisation: A Framework and A Case Study in Production SchedulingCodeJSSParXivFormulation
2023.11Large Language Models as Evolutionary OptimizersCodeTSPCEC 2024Solution
2023.11Algorithm Evolution Using Large Language Model   TSParXivAlgorithm
2023.12Mathematical discoveries from program search with large language modelsCodeBPPNatureAlgorithm
2024.02ReEvo: Large Language Models as Hyper-Heuristics with Reflective EvolutionCode <br> Project-PageTSP,VRP,OP, MKP,BPP,EDANeurIPS 2024Algorithm
2024.02AutoSAT: Automatically Optimize SAT Solvers via Large Language ModelsSATarXivAlgorithm
2024.02From Large Language Models and Optimization to Decision Optimization CoPilot: A Research ManifestoMILParXivFormulation
2024.03How Multimodal Integration Boost the Performance of LLM for Optimization: Case Study on Capacitated Vehicle Routing ProblemsVRParXivSolution
2024.03RouteExplainer: An Explanation Framework for Vehicle Routing ProblemCode <br> Project-PageVRPPAKDD 2024Interpretability
2024.03Can Large Language Models Solve Robot Routing?Code <br> Project-PageTSP,VRParXivAlgorithm
2024.05Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language ModelCodeTSP,BPP, FSSPICML 2024Algorithm
2024.05ORLM: Training Large Language Models for Optimization ModelingCodeGeneral OPTarXivFormulation
2024.05Self-Guiding Exploration for Combinatorial ProblemsCodeTSP,VRP,BPP, AP,KP,JSSPNeurIPS 2024Solution
2024.06Eyeballing Combinatorial Problems: A Case Study of Using Multimodal Large Language Models to Solve Traveling Salesman ProblemsTSParXivSolution
2024.07Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial ChallengesCodeTSP,mTSParXivSolution
2024.07Solving General Natural-Language-Description Optimization Problems with Large Language ModelsCodeMILPNAACL 2024Formulation
2024.08Diagnosing Infeasible Optimization Problems Using Large Language ModelsMILPINFORFormulation
2024.08LLMs can ScheduleCodeJSSParXivSolution
2024.09Multi-objective Evolution of Heuristic Using Large Language ModelTSP,BPParXivAlgorithm
2024.10Towards Foundation Models for Mixed Integer Linear ProgrammingMILParXivFormulation
2024.10LLMOPT: Learning to Define and Solve General Optimization Problems from ScratchGeneral OPTarXivFormulation
2024.10Large Language Model-driven Large Neighborhood Search for Large-Scale MILP ProblemsMILPUnder ReviewAlgorithm
2024.10HeurAgenix: A Multi-Agent LLM-Based Paradigm for Adaptive Heuristic Evolution and Selection in Combinatorial OptimizationTSP,CVRP,JSSP, MaxCut,MKPUnder ReviewAlgorithm
2024.10Efficient Heuristics Generation for Solving Combinatorial Optimization Problems Using Large Language ModelsTSP,CVRP, BPP,MKPUnder ReviewAlgorithm
2024.10OptiBench: Benchmarking Large Language Models in Optimization Modeling with Equivalence-Detection EvaluationMILPUnder ReviewBenchmark
2024.10OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization ModelingMILPUnder ReviewBenchmark
2024.10DRoC: Elevating Large Language Models for Complex Vehicle Routing via Decomposed Retrieval of Constraints48VRPsUnder ReviewFormulation
2024.10STARJOB: Dataset for LLM-Driven Job Shop SchedulingJSSPUnder ReviewSolution
2024.10LLM4Solver: Large Language Model for Efficient Algorithm Design of Combinatorial Optimization SolverMILPUnder ReviewAlgorithm
2024.10Unifying All Species: LLM-based Hyper-Heuristics for Multi-objective OptimizationTSPUnder ReviewAlgorithm
2024.10Evo-Step: Evolutionary Generation and Stepwise Validation for Optimizing LLMs in ORMILPUnder ReviewFormulation
2024.10Automatic programming via large language models with population self-evolution for dynamic job shop scheduling problemDyJSSParXivAlgorithm
2024.11Large Language Models for Combinatorial Optimization of Design Structure MatrixDSMarXivSolution
2024.12HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMsCodeTSP,BPP,OParXivAlgorithm

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.

DatePaperLinkProblemVenue
2023.05Efficient Training of Multi-task Combinatorial Neural Solver with Multi-armed Bandits   TSP,VRP,OP,KParXiv
2024.02Multi-Task Learning for Routing Problem with Cross-Problem Zero-Shot GeneralizationCode16VRPsKDD 2024
2024.03Towards a Generic Representation of Combinatorial Problems for Learning-Based ApproachesCodeSAT,TSP,COL,KParXiv
2024.04Cross-Problem Learning for Solving Vehicle Routing ProblemsCodeTSP,OP,PCTSPIJCAI 2024
2024.05MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-ExpertsCode16VRPsICML 2024
2024.06RouteFinder: Towards Foundation Models for Vehicle Routing ProblemsCode <br> Project-Page24VRPsarXiv
2024.06GOAL: A Generalist Combinatorial Optimization Agent LearnerCode(A)TSP,5VRPs,OP,JSSP, OSSP,UMSP,KP,MVC, MIS,MCLP,TRP,SOParXiv
2024.08UNCO: Towards Unifying Neural Combinatorial Optimization through Large Language ModelTSP,CVRP,KP, MVCP,SMTWTParXiv
2024.09MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at ScaleCodeMAPFarXiv
2024.10Toward Learning Generalized Cross-Problem Solving Strategies for Combinatorial OptimizationTSP,VRP,SDVRP, OP,PCTSP,SPCTSPUnder Review
2024.10Learning General Representations Across Graph Combinatorial Optimization Problems7GDPsUnder Review
2024.10Solving Diverse Combinatorial Optimization Problems with a Unified Model(A)TSP,CVRP,OP,PCTSP, SPCTSP,KP,MIS,FFSPUnder Review
2024.10SHIELD: Multi-task Multi-distribution Vehicle Routing Solver with Sparsity & Hierarchy in Efficiently Layered Decoder16VRPsUnder Review
2024.10Unified Neural Solvers for General TSP and Multiple Combinatorial Optimization Tasks via Problem Reduction and Matrix Encoding(A)TSP,DHCP, 3SATUnder Review
2024.11CaDA: Cross-Problem Routing Solver with Constraint-Aware Dual-Attention16VRPsarXiv