A Comprehensive Evaluation of Contemporary ML-Based Solvers for Combinatorial Optimization

• URL: http://arxiv.org/abs/2505.16952v1
• Date: Thu, 22 May 2025 17:34:38 GMT
• Title: A Comprehensive Evaluation of Contemporary ML-Based Solvers for Combinatorial Optimization
• Authors: Shengyu Feng, Weiwei Sun, Shanda Li, Ameet Talwalkar, Yiming Yang,
• Abstract summary: We introduce FrontierCO, a benchmark that covers eight canonical optimization problem types and evaluates 16 representative ML-based solvers.<n>Our empirical results provide critical insights into the strengths and limitations of current machine learning and optimization methods.
• Score: 41.86009485086193
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• UniCO: Towards a Unified Model for Combinatorial Optimization Problems [30.524941693870534]
  Combinatorial Optimization (CO) encompasses a wide range of problems that arise in many real-world scenarios.<n>We introduce UniCO, a unified model for solving various CO problems.
  arXiv  Detail & Related papers  (2025-05-07T12:39:33Z)
• Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
  Off-CMAB is the first offline learning framework for CMAB.<n>Off-CMAB combines pessimistic reward estimations with solvers.<n>Experiments on synthetic and real-world datasets highlight the superior performance of CLCB.
  arXiv  Detail & Related papers  (2025-01-31T16:56:18Z)
• Optimizing Pretraining Data Mixtures with LLM-Estimated Utility [52.08428597962423]
  Large Language Models improve with increasing amounts of high-quality training data.<n>We find token-counts outperform manual and learned mixes, indicating that simple approaches for dataset size and diversity are surprisingly effective.<n>We propose two complementary approaches: UtiliMax, which extends token-based $200s by incorporating utility estimates from reduced-scale ablations, achieving up to a 10.6x speedup over manual baselines; and Model Estimated Data Utility (MEDU), which leverages LLMs to estimate data utility from small samples, matching ablation-based performance while reducing computational requirements by $simx.
  arXiv  Detail & Related papers  (2025-01-20T21:10:22Z)
• RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark [69.19502244910632]
  Deep reinforcement learning (RL) has shown significant benefits in solving optimization (CO) problems. We introduce RL4CO, a unified benchmark with in-depth library coverage of 23 state-of-the-art methods and more than 20 CO problems. Built on efficient software libraries and best practices in implementation, RL4CO features modularized implementation and flexible configuration of diverse RL algorithms, neural network architectures, inference techniques, and environments.
  arXiv  Detail & Related papers  (2023-06-29T16:57:22Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  We propose an easy-to-implement online reinforcement learning (online RL) framework called textttMEX. textttMEX integrates estimation and planning components while balancing exploration exploitation automatically. It can outperform baselines by a stable margin in various MuJoCo environments with sparse rewards.
  arXiv  Detail & Related papers  (2023-05-29T17:25:26Z)
• Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning [14.86600327306136]
  A general framework of unsupervised learning for optimization (CO) is to train a neural network (NN) whose output gives a problem solution by directly optimizing the CO objective. We propose a new objective of unsupervised learning for CO where the goal of learning is to search for good initialization for future problem instances rather than give direct solutions. We observe that even just the initial solution given by our model before fine-tuning can significantly outperform the baselines under various evaluation settings.
  arXiv  Detail & Related papers  (2023-01-08T22:14:59Z)
• Matrix Encoding Networks for Neural Combinatorial Optimization [5.524431376262751]
  A popular approach is to use a neural net to compute on the parameters of a given optimization (CO) problem. There is currently no neural net model that takes in such matrix-style relationship data as an input. In this paper, we show how conveniently it takes in and processes parameters of such complex CO problems.
  arXiv  Detail & Related papers  (2021-06-21T13:50:23Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• A Survey on Large-scale Machine Learning [67.6997613600942]
  Machine learning can provide deep insights into data, allowing machines to make high-quality predictions. Most sophisticated machine learning approaches suffer from huge time costs when operating on large-scale data. Large-scale Machine Learning aims to learn patterns from big data with comparable performance efficiently.
  arXiv  Detail & Related papers  (2020-08-10T06:07:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.