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.

Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptation

Created by
  • Haebom

Author

Haoyu Lei, Kaiwen Zhou, Yinchuan Li, Zhitang Chen, Farzan Farnia

Outline

This paper presents a method for solving NP-complete problems using a diffusion model based on neural combinatorial optimization (NCO). To address the challenges of existing NCO methods, including their size and cross-problem generalization, and their high training costs, we propose DIFU-Ada, a framework that adapts at the inference stage without training. DIFU-Ada utilizes predefined guidance functions to enable conditional generation and zero-shot cross-problem transfer and size generalization without additional training. We understand the cross-problem transferability through theoretical analysis, and experimentally demonstrate that a diffusion solver trained solely on the traveling salesman problem (TSP) achieves competitive zero-shot transfer performance on TSP variants such as PCTSP and OP.

Takeaways, Limitations

•
Takeaways:
◦
We propose a novel framework (DIFU-Ada) that adapts at the inference stage without training, thereby solving the problems of high training cost and poor generalization performance of existing diffusion-based NCOs (Limitations).
◦
Experimental verification of improved transfer and size generalization performance in zero-shot cross problem.
◦
A theoretical analysis further enhances our understanding of cross-problem transferability.
•
Limitations:
◦
The effectiveness of the proposed method is limited to TSP and its variant problems, and its generalization performance to other types of combinatorial optimization problems requires further study.
◦
The design of the predefined guidance function may affect performance, and further research is needed to design the optimal guidance function.
◦
Generalization performance evaluations are needed for problems of various sizes, and there is a possibility of bias toward problems of a certain size.
👍
Made with Slashpage