Unsupervised Learning for Quadratic Assignment
This work addresses combinatorial optimization problems, which are critical in fields like logistics and scheduling, but it appears incremental as it builds on existing learning-based methods with a specific unsupervised approach.
The paper tackled the quadratic assignment problem, a fundamental NP-hard combinatorial optimization challenge, by introducing PLUME search, an unsupervised learning framework that improves solution quality, as demonstrated through experimental results showing consistent enhancements and generalization across different problem densities and sizes.
We introduce PLUME search, a data-driven framework that enhances search efficiency in combinatorial optimization through unsupervised learning. Unlike supervised or reinforcement learning, PLUME search learns directly from problem instances using a permutation-based loss with a non-autoregressive approach. We evaluate its performance on the quadratic assignment problem, a fundamental NP-hard problem that encompasses various combinatorial optimization problems. Experimental results demonstrate that PLUME search consistently improves solution quality. Furthermore, we study the generalization behavior and show that the learned model generalizes across different densities and sizes.