Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

Unsupervised Learning for Quadratic Assignment

Created by
  • Haebom

Author

Yimeng Min, Carla P. Gomes

Outline

PLUME search is a data-driven framework that improves search efficiency in combinatorial optimization problems through unsupervised learning. Unlike supervised learning or reinforcement learning, it uses a non-autoregressive approach to learn directly from problem instances via a permutation-based loss function. In this paper, we evaluate its performance on the quadratic assignment problem, a fundamental NP-hard problem encompassing various combinatorial optimization problems. Experimental results demonstrate that PLUME search consistently improves solution quality. We also investigate whether the learned model generalizes to different densities and sizes.

Takeaways, Limitations

Takeaways: A novel combinatorial optimization approach based on unsupervised learning is presented, achieving better solution quality than existing methods in quadratic assignment problems, and demonstrating generalization performance across a variety of problem sizes and densities.
Limitations: Currently, only the quadratic assignment problem has been evaluated, and further research is needed to determine generalization performance for other types of combinatorial optimization problems. The limitations of the non-autoregressive approach may limit optimization for certain problem types.
👍