Efficient and Robust Neural Combinatorial Optimization via Wasserstein-Based Coresets

Xu Wang, Fuyou Miao, Wenjie Liu, Yan Xiong

TL;DR

This paper introduces a novel framework for Neural Combinatorial Optimization (NCO) that uses Wasserstein-based coresets to compress massive datasets into small, high-quality proxies. By focusing on dataset diversity and geometric invariance, the authors achieve faster training and significantly better robustness to distribution shifts compared to traditional uniform sampling.

What Problem Does This Paper Address?

Combinatorial Optimization (CO)—solving problems like the Traveling Salesperson Problem (TSP)—is essential for logistics, manufacturing, and routing. While Neural CO (NCO) methods offer fast, data-driven alternatives to traditional solvers, they hit two major walls:

  1. Resource Intensity: Training state-of-the-art NCO models requires massive datasets, leading to high storage costs and long training times.
  2. Brittleness (Distribution Shift): Models trained on one type of data (e.g., points from a normal distribution) often perform poorly when faced with real-world data that looks different (e.g., uniform or clustered distributions).

The authors aim to create a training framework that is both efficient (using less data) and robust (handling different data distributions gracefully).

Methods

The authors propose three key innovations to bridge the efficiency-robustness gap:

  • Wasserstein Distance under Rigid Transformations (RWD): They model CO instances as probability measures. Since a TSP solution doesn't change if you rotate or shift the entire map, they developed RWD—a metric that treats geometrically "rigid" transformations as the same instance. This simplifies the data space the model needs to learn.
  • Wasserstein-Based Coresets: Instead of random sampling, they use a coreset technique. A coreset is a small subset of data that acts as a mathematical proxy for the full dataset. Their algorithm, inspired by hierarchical clustering, ensures the coreset captures the diversity of the original data by picking representative "centers" from across the entire distribution.
  • Merge-and-Reduce Framework: To handle truly massive datasets where even building a coreset is slow, they adapted the construction to a "merge-and-reduce" framework. This allows for parallel computing, making the coreset construction time independent of the total dataset size.

The overall framework involves compressing the dataset into a coreset, training the model on this reduced set, and then using a tree-based alignment process during inference to match new test instances to the most similar training examples.

The efficient training and inference framework using coresets and alignment.

Datasets

The researchers evaluated their method across several classic CO problems:

  • TSP (Traveling Salesperson Problem): Tested on TSP100 through TSP1000, using synthetic 2D/3D data and the real-world TSPLIB benchmark.
  • MIS (Maximum Independent Set): Used Erdős-Rényi (ER) random graphs and the SATLIB benchmark.
  • CVRP (Capacitated Vehicle Routing Problem): Evaluated on CVRP100 and the CVRPLIB benchmark.

Key Insights and Ideas

  • Diversity Over Quantity: Randomly sampling 10% of your data (Uniform Sampling) often misses rare but important edge cases. Coresets explicitly seek out these diverse instances, which is why they provide better robustness to distribution shifts.
  • Geometry Matters: By making their distance metric (RWD) invariant to rotation and translation, the authors effectively "de-noised" the data, allowing the neural network to focus on the underlying combinatorial structure rather than irrelevant orientations.
  • Parallelizable Compression: The use of the merge-and-reduce framework is crucial for scalability, ensuring that as datasets grow to millions of instances, the coreset construction remains computationally feasible.

Key Results

The experimental results demonstrate that "less is more" when the data is chosen wisely:

  • Robustness: In TSP100 tests, when the test distribution shifted from Normal to Uniform, the coreset-trained model (CS-aligned) achieved significantly shorter tour lengths than uniform sampling (e.g., 92.01 vs 95.01 for a sample size of ~13k).
  • Efficiency: Models trained on coresets of only ~10% the size of the original dataset achieved performance comparable to or better than models trained on the full 128,000-instance dataset.
  • Generalization: Coreset-trained models generalized better to larger problem sizes. A model trained on TSP100 via coresets outperformed uniform sampling when tested on TSP1000.
Comparison of uniform sampling and the coreset method across different distributions.

Limitations and Future Work

While powerful, the authors note a few areas for growth:

  • Alignment Overhead: While the inference-time alignment process improves performance, it adds a small computational step.
  • Graph Structures: The current work focuses heavily on Euclidean point sets. The authors suggest that future work will extend these Wasserstein-based coresets to more complex, non-Euclidean graph structures.
  • Hyperparameter Sensitivity: The effectiveness of the coreset depends on choosing the right radius and doubling dimension, which might require some trial and error for new problem types.

Summary updated

Abstract

Combinatorial optimization (CO) is a fundamental tool in many fields. Many neural combinatorial optimization (NCO) methods have been proposed to solve CO problems. However, existing NCO methods typically require significant computational and storage resources, and face challenges in maintaining robustness to distribution shifts between training and test data. To address these issues, we model CO instances into probability measures, and introduce Wasserstein-based metrics to quantify the difference between CO instances. We then leverage a popular data compression technique, \emph{coreset}, to construct a small-size proxy for the original large dataset. However, the time complexity of constructing a coreset is linearly dependent on the size of the dataset. Consequently, it becomes challenging when datasets are particularly large. Further, we accelerate the coreset construction by adapting it to the merge-and-reduce framework, enabling parallel computing. Additionally, we prove that our coreset is a good representation in theory. {Subsequently}, to speed up the training process for existing NCO methods, we propose an efficient training framework based on the coreset technique. We train the model on a small-size coreset rather than on the full dataset, and thus save substantial computational and storage resources. Inspired by hierarchical Gonzalez’s algorithm, our coreset method is designed to capture the diversity of the dataset, which consequently improves robustness to distribution shifts. Finally, experimental results demonstrate that our training framework not only enhances robustness to distribution shifts but also achieves better performance with reduced resource requirements.
BibTeX
@inproceedings{wang2025efficient,
  author = {Xu Wang and Fuyou Miao and Wenjie Liu and Yan Xiong},
  title = {{Efficient and Robust Neural Combinatorial Optimization via Wasserstein-Based Coresets}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=F57HPKZ6KD},
}
Figure