🚀 AutoCOBench: Automatically Formulating and Solving Combinatorial Optimization Problems

AutoCOBench is a novel framework and benchmark that automates both the formulation and solution of Combinatorial Optimization Problems (COPs) from natural language input, balancing formulation automation with solver adaptability.

AutoCOBench workflow: From natural language to optimized solutions

---

🚀 Quick Start

Installation

1. Clone the repository:

   git clone git@github.com:tsinghua-fib-lab/LLMSolver.git
   cd LLMSolver

2. Install dependencies:

   # Create virtual environment
   conda create -n autoco_bench python 3.10
   conda activate autoco_bench
   
   # Install base dependencies
   pip install -r requirements.txt
   
   # Install PyTorch extensions (these must be installed separately)
   # Replace ${CUDA} with the appropriate version for your environment: cpu, cu118, cu126, or cu128
   pip install torch-scatter torch-sparse -f https://data.pyg.org/whl/torch-2.6.0+${CUDA}.html

3. (Optional) Install LKH for VRP solvers:

   pip install lkh
   cd solver/cvrp/lkh_solver
   tar -zvxf LKH-3.0.13.tgz
   cd LKH-3.0.13
   make

Quick Example

Here's a minimal example to run a solver on a VRP instance:

from solver.cvrp.solver_pool import SolverPool
from envs.cvrp.mtvrp import MTVRPEnv, MTVRPGenerator
import torch

# Setup solver pool
device = torch.device("cuda" if torch.cuda.is_available() else "cpu")
solver_pool = SolverPool(
    lkh_path="path/to/LKH", 
    lkh_num_runs=30, 
    policy_dir="path/to/model_checkpoints", 
    device=device
)

# Generate and solve VRP instance
generator = MTVRPGenerator(num_loc=30, variant_preset="cvrp")
env = MTVRPEnv(generator, check_solution=False)
td_data = env.generator(1)
td_test = env.reset(td_data)

# Solve and get results
actions = solver_pool.solve(td_test.clone(), solver_name="lkh")
rewards = env.get_reward(td_test.clone().cpu(), actions.clone().cpu())
print(f"Solution: {actions}")
print(f"Reward: {rewards}")

See example/test_solver.py for more detailed examples.

---

🛠️ Project Structure

autocobench/
├── benchmark/          # Benchmark datasets
├── envs/              # Problem environment definitions
├── solver/            # Various solver implementations
├── recognition/       # LLM recognition pipeline
├── utils/            # Utility functions
└── assets/           # Resource files

---

🎯 Supported Problems

AutoCOBench spans 43 common COP types, each with thousands of instances annotated with natural language descriptions and structured representations.

Domain	Problem Types	Count
🚚 VRP	CVRP, OVRP, VRPB, VRPL, VRPTW, OVRPTW, OVRPB, OVRPL, VRPBL, VRPBTW, VRPLTW, OVRPBL, OVRPBTW, OVRPLTW, VRPBLTW, OVRPBLTW, VRPMB, OVRPMB, VRPMBL, VRPMBTW, OVRPMBL, OVRPMBTW, VRPMBLTW, OVRPMBLTW	24
⏰ SP	JSSP, FJSSP, FSSP, HFSSP, OSSP, ASP	6
📦 BPP	2DOFBPP, 2DOFBPPR, 2DONBPP, 2DONBPPR, 3DOFBPP, 3DOFBPPR, 3DONBPP, 3DONBPPR	8
🕸️ GP	MIS, MVC, Max Cut, Max Clique	4
🎒 Knapsack	Knapsack	1

---

🔧 Supported Solvers

Vehicle Routing Problems (VRP)

• LKH - Lin-Kernighan-Helsgaun heuristic
• PyVRP - Python-based VRP solver
• OR-Tools - Google's optimization tools
• RouteFinder - Towards Foundation Models for Vehicle Routing Problems.

Bin Packing Problems (BPP)

• Genetic Algorithm - Evolutionary approach for 2D/3D bin packing
• PCT - Online 3D Bin Packing on Packing Configuration Trees

Knapsack Problems (KP)

• Dynamic Programming - Optimal solution for standard knapsack
• POMO - POMO: Policy Optimization with Multiple Optima for Reinforcement Learning

Graph Problems (GP)

• Gurobi
• FastT2T - Training-to-Testing Solving Framework for Combinatorial Optimization
• DiffUCO - A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization

Scheduling Problems (SP)

• Job Shop Scheduling Benchmark: MILP, CP-SAT, Dispatching Rules, Genetic Algorithm, L2D, FJSP-DRL and DANIEL

---

🧠 LLM-based Recognition Pipeline

The recognition module provides a complete pipeline:

• 🔍 Classifier: Automatically classifies problem type from natural language description
• ✅ Checker: Verifies and validates the classification accuracy
• 📊 Extractor: Extracts structured problem data for solver input

---

📊 Benchmarks & Datasets

• Extensive Coverage: Datasets for VRP, BPP, KP, and more in benchmark
• Ready-to-Use: Data templates and JSON problem definitions
• Natural Language: Thousands of instances with human-readable descriptions
• Structured Data: Machine-readable problem representations

---

🙏 Acknowledgments

Our work builds upon the following excellent projects and research:

• LKH, PyVRP, OR-Tools, RouteFinder
• PCT, POMO, Gurobi, FastT2T, DiffUCO
• Job Shop Scheduling Benchmark

---

📄 License

This project is licensed under the Apache License 2.0 - see the LICENSE file for details.

---

Made with ❤️ by the AutoCOBench Team