/awesome-fm4co

Recent research papers about Foundation Models for Combinatorial Optimization

MIT LicenseMIT

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 Code Supply_Chain arXiv Algorithm w. Interpretability
2023.09 Can Language Models Solve Graph Problems in Natural Language? Code Graph NeurIPS 2023 Solution
2023.09 Large Language Models as Optimizers Code TSP ICLR 2024 Solution
2023.10 Chain-of-Experts: When LLMs Meet Complex Operations Research Problems Code MILP ICLR 2024 Formulation
2023.10 OptiMUS: Scalable Optimization Modeling with (MI)LP Solvers and Large Language Models Code MILP ICML 2024 Formulation
2023.10 AI-Copilot for Business Optimisation: A Framework and A Case Study in Production Scheduling Code JSSP arXiv Formulation
2023.11 Large Language Models as Evolutionary Optimizers Code 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 Code BPP Nature Algorithm
2024.02 ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution Code
Project-Page
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 Code
Project-Page
VRP PAKDD 2024 Interpretability
2024.03 Can Large Language Models Solve Robot Routing? Code
Project-Page
TSP,VRP arXiv Algorithm
2024.05 Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model Code TSP,BPP, FSSP ICML 2024 Algorithm
2024.05 ORLM: Training Large Language Models for Optimization Modeling Code General OPT arXiv Formulation
2024.05 Self-Guiding Exploration for Combinatorial Problems Code 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 Code TSP,mTSP arXiv Solution
2024.07 Solving General Natural-Language-Description Optimization Problems with Large Language Models Code MILP NAACL 2024 Formulation
2024.08 Diagnosing Infeasible Optimization Problems Using Large Language Models MILP INFOR Formulation
2024.08 LLMs can Schedule Code 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 arXiv Formulation
2024.10 LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch General OPT arXiv 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 Under Review Benchmark
2024.10 DRoC: Elevating Large Language Models for Complex Vehicle Routing via Decomposed Retrieval of Constraints 48VRPs Under Review 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

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
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 Code 16VRPs KDD 2024
2024.03 Towards a Generic Representation of Combinatorial Problems for Learning-Based Approaches Code SAT,TSP,COL,KP arXiv
2024.04 Cross-Problem Learning for Solving Vehicle Routing Problems Code TSP,OP,PCTSP IJCAI 2024
2024.05 MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Experts Code 16VRPs ICML 2024
2024.06 RouteFinder: Towards Foundation Models for Vehicle Routing Problems Code
Project-Page
24VRPs arXiv
2024.06 GOAL: A Generalist Combinatorial Optimization Agent Learner Code (A)TSP,4VRPs, OP,JSSP,UMSP, KP,MVC,MIS arXiv
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 Code 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 Under Review