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:
- Resource Intensity: Training state-of-the-art NCO models requires massive datasets, leading to high storage costs and long training times.
- 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.
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.
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