首个面向真实场景与超大规模的组合优化机器学习评估基准
FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization
- 构建涵盖8类问题的真实世界实例集，含竞赛级与工业级数据
- 在1000万节点的TSP问题上，传统算法仍优于多数ML方法
- 首次系统对比16种ML求解器，揭示其在复杂结构下的性能瓶颈
机器学习在组合优化领域展现出潜力，但现有进展多基于小规模、合成基准，难以反映真实世界结构与规模。核心问题在于ML方法通常在合成生成器上训练和评估，无法衡量其在不规则、竞赛级或工业级数据上的表现。本文提出FrontierCO，一个面向真实结构与极端规模的机器学习组合优化求解器评估基准。该基准涵盖路由、调度、设施选址、图问题等8类组合优化任务，实例来自竞赛和公开数据集（如DIMACS、TSPLib）。每项任务均提供易例（历史难题现可解）与难例（开放或计算密集），并配备标准化训练/验证资源。我们用FrontierCO评估16种代表性机器学习求解器——包括图神经网络、混合神经符号方法及大模型代理——并与先进经典求解器对比。结果发现，性能差距在结构复杂且实例庞大的情况下持续扩大（如TSP达1000万节点；MIS达800万节点），同时识别出部分场景下机器学习方法超越经典算法。通过聚焦真实结构与数量级更大的实例，FrontierCO为推进机器学习在组合优化中的应用提供了严谨评估基础。基准已开源：https://huggingface.co/datasets/CO-Bench/FrontierCO。
原文摘要 · Abstract (English)
Machine learning (ML) has shown promise for tackling combinatorial optimization (CO), but much of the reported progress relies on small-scale, synthetic benchmarks that fail to capture real-world structure and scale. A core limitation is that ML methods are typically trained and evaluated on synthetic instance generators, leaving open how they perform on irregular, competition-grade, or industrial datasets. We present FrontierCO, a benchmark for evaluating ML-based CO solvers under real-world structure and extreme scale. FrontierCO spans eight CO problems, including routing, scheduling, facility location, and graph problems, with instances drawn from competitions and public repositories (e.g., DIMACS, TSPLib). Each task provides both easy sets (historically challenging but now solvable) and hard sets (open or computationally intensive), alongside standardized training/validation resources. Using FrontierCO, we evaluate 16 representative ML solvers--graph neural approaches, hybrid neural-symbolic methods, and LLM-based agents--against state-of-the-art classical solvers. We find a persistent performance gap that widens under structurally challenging and large instance sizes (e.g., TSP up to 10M nodes; MIS up to 8M), while also identifying cases where ML methods outperform classical solvers. By centering evaluation on real-world structure and orders-of-magnitude larger instances, FrontierCO provides a rigorous basis for advancing ML for CO. Our benchmark is available at https://huggingface.co/datasets/CO-Bench/FrontierCO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。