Controlling Continuous Relaxation for Combinatorial Optimization

Autor:	Ichikawa, Yuma
Rok vydání:	2023
Předmět:	Statistics - Machine Learning Computer Science - Machine Learning Statistics - Computation Statistics - Methodology
Druh dokumentu:	Working Paper
Popis:	Unsupervised learning (UL)-based solvers for combinatorial optimization (CO) train a neural network that generates a soft solution by directly optimizing the CO objective using a continuous relaxation strategy. These solvers offer several advantages over traditional methods and other learning-based methods, particularly for large-scale CO problems. However, UL-based solvers face two practical issues: (I) an optimization issue, where UL-based solvers are easily trapped at local optima, and (II) a rounding issue, where UL-based solvers require artificial post-learning rounding from the continuous space back to the original discrete space, undermining the robustness of the results. This study proposes a Continuous Relaxation Annealing (CRA) strategy, an effective rounding-free learning method for UL-based solvers. CRA introduces a penalty term that dynamically shifts from prioritizing continuous solutions, effectively smoothing the non-convexity of the objective function, to enforcing discreteness, eliminating artificial rounding. Experimental results demonstrate that CRA significantly enhances the performance of UL-based solvers, outperforming existing UL-based solvers and greedy algorithms in complex CO problems. Additionally, CRA effectively eliminates artificial rounding and accelerates the learning process. Comment: 22 pages, 9 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2309.16965 Zobrazit plný text záznamu View this record from Arxiv