A Comprehensive Evaluation of Contemporary ML-Based Solvers for Combinatorial Optimization
This work addresses the problem of evaluating ML-based solvers for combinatorial optimization in real-world scenarios, but it is incremental as it focuses on benchmarking rather than new solver development.
The authors tackled the lack of practical evaluation for ML-based solvers in combinatorial optimization by introducing FrontierCO, a comprehensive benchmark with industrial-scale instances, and found that it provides critical insights into the strengths and limitations of current methods, though no specific performance numbers are reported.
Machine learning (ML) has demonstrated considerable potential in supporting model design and optimization for combinatorial optimization (CO) problems. However, much of the progress to date has been evaluated on small-scale, synthetic datasets, raising concerns about the practical effectiveness of ML-based solvers in real-world, large-scale CO scenarios. Additionally, many existing CO benchmarks lack sufficient training data, limiting their utility for evaluating data-driven approaches. To address these limitations, we introduce FrontierCO, a comprehensive benchmark that covers eight canonical CO problem types and evaluates 16 representative ML-based solvers--including graph neural networks and large language model (LLM) agents. FrontierCO features challenging instances drawn from industrial applications and frontier CO research, offering both realistic problem difficulty and abundant training data. Our empirical results provide critical insights into the strengths and limitations of current ML methods, helping to guide more robust and practically relevant advances at the intersection of machine learning and combinatorial optimization. Our data is available at https://huggingface.co/datasets/CO-Bench/FrontierCO.