Controlling Continuous Relaxation for Combinatorial Optimization
This addresses practical issues in combinatorial optimization solvers for large-scale problems, though it is incremental as it builds on existing unsupervised learning approaches.
The paper tackles the problem of unsupervised learning-based solvers for combinatorial optimization getting stuck at local optima and requiring artificial rounding, by proposing a Continuous Relaxation Annealing (CRA) strategy that dynamically shifts from continuous to discrete solutions, significantly enhancing performance and outperforming existing methods in complex problems.
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.