FrontierCO

FrontierCO是一个全面的基准数据集，涵盖了八种典型的组合优化问题类型，并评估了16种代表性的基于机器学习的求解器，包括图神经网络和大型语言模型（LLM）代理。该数据集具有来自工业应用和前沿组合优化研究的挑战性实例，提供了现实的问题难度和丰富的训练数据。通过使用FrontierCO，我们进行了广泛的评估，包括端到端神经求解器、神经增强的传统算法和基于LLM的代理方法，为比较神经和LLM求解器的相对优势和局限性提供了关键的见解。FrontierCO is a comprehensive benchmark dataset that covers eight typical combinatorial optimization problem types and supports the evaluation of 16 representative machine learning-based solvers, including graph neural networks and large language model (LLM) agents. This dataset contains challenging instances sourced from industrial applications and cutting-edge combinatorial optimization research, providing realistic problem difficulty levels and abundant training data. By leveraging FrontierCO, we performed extensive evaluations covering end-to-end neural solvers, neural-augmented traditional algorithms, and LLM-based agent approaches, which offer critical insights for comparing the relative strengths and limitations of neural and LLM solvers.

原始信息汇总

FrontierCO: 前沿组合优化基准数据集

概述

• 目的：评估基于ML的求解器在大规模和现实世界组合优化问题上的性能
• 特点：
  • 涵盖8个经典组合优化问题
  • 跨越5个应用领域
  • 提供训练和评估实例
  • 专门设计用于测试ML和LLM在解决NP难问题中的前沿能力

数据集结构

• 目录结构：

  FrontierCO/ ├── CFLP/ │ ├── easy_test_instances/ │ ├── hard_test_instances/ │ ├── valid_instances/ │ └── config.py ├── CPMP/ ├── CVRP/ ├── FJSP/ ├── MIS/ ├── MDS/ ├── STP/ ├── TSP/ └── ...

• 子目录内容：

  • easy_test_instances/：可被SOTA人工设计求解器解决的基准实例
  • hard_test_instances/：计算密集型或缺乏已知最优解的实例
  • valid_instances/：用于验证或开发的额外实例（如适用）
  • config.py：包含实例格式、求解器设置和参考解决方案的元数据

涵盖任务

1. MIS – 最大独立集
2. MDS – 最小支配集
3. TSP – 旅行商问题
4. CVRP – 带容量限制的车辆路径问题
5. CFLP – 带容量限制的设施选址问题
6. CPMP – 带容量限制的p中位问题
7. FJSP – 柔性作业车间调度问题
8. STP – 斯坦纳树问题

数据来源

• 公共存储库（如TSPLib、CVRPLib）
• DIMACS和PACE挑战赛
• 先前ML和优化研究中使用的合成实例生成器
• 从最近的SOTA求解器评估基准中手动筛选

使用方式

1. 克隆仓库并选择感兴趣的任务： bash git clone https://huggingface.co/datasets/CO-Bench/FrontierCO cd FrontierCO/CFLP

2. 加载数据实例： python from config import load_data instance = load_data(easy_test_instances/i1000_1.plc) print(instance)

3. 生成解决方案： python solution = my_solver_func(**instance)

4. 评估解决方案： python from config import eval_func score = eval_func(**instance, **solution) print("Evaluation score:", score)

引用

bibtex @misc{feng2025comprehensive, title={A Comprehensive Evaluation of Contemporary ML-Based Solvers for Combinatorial Optimization}, author={Shengyu Feng and Weiwei Sun and Shanda Li and Ameet Talwalkar and Yiming Yang}, year={2025}, }

许可证

• 许可证类型：MIT License

搜集汇总

数据集介绍

构建方式

FrontierCO数据集的构建基于对组合优化领域现有基准测试不足的深刻洞察，通过整合来自工业应用和前沿研究的挑战性实例，覆盖了八种经典组合优化问题类型。该数据集从权威资源库（如TSPLib、CVRPLib、SteinLib）、重要竞赛（如DIMACS Challenge和PACE Challenge）以及最新研究中精选实例，确保了数据的多样性和实际相关性。针对每种问题类型，数据集设计了两种不同难度的测试集：简单集包含已被现有方法解决的实例，用于验证机器学习求解器的有效性；困难集则聚焦于尚未解决的开放性问题，旨在评估求解器在真实复杂场景下的表现。此外，对于缺乏训练数据的问题，研究团队开发了脚本生成多样化的合成数据，以支持数据驱动方法的训练需求。

特点

FrontierCO数据集以其规模性、真实性和挑战性著称。首先，它突破了传统基准测试的小规模限制，包含从数千节点到数百万节点不等的实例，真实反映了工业级问题的复杂度。其次，数据集强调实例的结构复杂性而非单纯规模，例如采用超立方图或SAT归约生成的MIS实例，迫使模型必须理解深层次的组合结构。再者，数据集通过严格筛选确保每个实例要么无法被现有最优算法高效解决，要么尚无已知最优解，从而将评估推向组合优化的前沿领域。此外，数据集为所有测试实例提供标准化最佳已知解（BKS），并通过统一的计算环境消除评估偏差，为不同求解器提供公平比较平台。

使用方法

使用FrontierCO进行评测时，研究团队提供了完整的工具链支持，包括数据加载器、评估函数和面向LLM智能体的抽象求解模板。评估采用归一化的原始间隙（primal gap）作为核心指标，允许最大1小时的单实例求解时间，所有实验在统一的CPU/GPU配置下执行以确保可比性。针对神经求解器，数据集提供标准化的训练集和验证集；对于基于LLM的符号求解器，则提供包含自然语言问题描述和Python接口模板的开发集。用户可通过对比求解器在简单集和困难集上的表现差异，系统评估其泛化能力和实际应用潜力。值得注意的是，数据集特别设计了防止启发式黑客攻击的评估机制，确保求解器的性能提升源于真正的算法创新而非对特定实例特征的过拟合。

背景与挑战

背景概述

FrontierCO是由卡内基梅隆大学计算机科学学院的Shengyu Feng、Weiwei Sun等研究人员于2025年推出的组合优化基准测试数据集。该数据集旨在解决当前机器学习求解器在组合优化领域评估中存在的三大局限：规模限制、现实性不足和数据匮乏问题。作为首个覆盖8种经典组合优化问题类型（包括最大独立集、旅行商问题等）的大规模基准，FrontierCO整合了工业应用场景的真实案例和前沿研究难题，同时提供了丰富的训练数据支持。该数据集通过构建不同难度的测试集（简单集和困难集），系统评估了16种代表性机器学习求解器的性能，为机器学习与组合优化的交叉研究提供了重要的实证基础。

当前挑战

FrontierCO主要面临两个层面的挑战：在领域问题层面，组合优化问题固有的NP难特性导致求解器需要处理指数级增长的解空间，特别是在大规模现实场景中（如百万节点规模的图问题），传统机器学习方法面临严重的泛化能力退化问题。在构建过程层面，数据集需要平衡实例的多样性与评估的严谨性：一方面需从TSPLib等经典库中筛选具有现实代表性的案例，另一方面要为缺乏训练数据的问题（如设施选址问题）设计合成数据生成方案。此外，确保最优解的参考质量（通过SOTA算法验证）和评估标准的统一性（如原始间隙指标）也是构建过程中的关键挑战。

常用场景

经典使用场景

FrontierCO数据集在组合优化领域的研究中扮演了关键角色，尤其适用于评估基于机器学习的求解器在解决复杂组合优化问题时的性能。该数据集涵盖了八种经典的组合优化问题类型，包括最大独立集（MIS）、旅行商问题（TSP）和设施选址问题（CFLP）等，为研究者提供了一个统一的测试平台。通过提供工业级应用场景和前沿研究中的挑战性实例，FrontierCO能够有效验证求解器在真实世界中的表现。

实际应用

在实际应用中，FrontierCO数据集被广泛用于优化物流、资源分配和调度等工业问题。例如，在物流领域，该数据集中的车辆路径问题（CVRP）实例可用于优化配送路线，降低运输成本。在制造业中，灵活作业车间调度问题（FJSP）实例则有助于提高生产效率和资源利用率。通过在这些实际场景中测试求解器的性能，FrontierCO为工业界提供了可靠的解决方案评估工具。

衍生相关工作

FrontierCO数据集催生了一系列相关研究，特别是在神经求解器和基于大语言模型（LLM）的符号求解器领域。例如，DiffUCO和SDDS等神经求解器利用该数据集验证了其在最大独立集问题上的性能。同时，FunSearch和Self-Refine等LLM-based方法通过FrontierCO展示了其在自动算法设计中的潜力。这些工作不仅扩展了机器学习在组合优化中的应用范围，还为未来的研究方向提供了重要参考。