Reheated Gradient-based Discrete Sampling for Combinatorial Optimization
This addresses computational inefficiency in combinatorial optimization solvers, which is an incremental improvement for researchers and practitioners in optimization and AI.
The paper tackles the problem of 'wandering in contours' in gradient-based discrete sampling for combinatorial optimization, where solutions with similar objective values are sampled inefficiently, and introduces a reheating mechanism that demonstrates superiority over existing methods across diverse problems.
Recently, gradient-based discrete sampling has emerged as a highly efficient, general-purpose solver for various combinatorial optimization (CO) problems, achieving performance comparable to or surpassing the popular data-driven approaches. However, we identify a critical issue in these methods, which we term ''wandering in contours''. This behavior refers to sampling new different solutions that share very similar objective values for a long time, leading to computational inefficiency and suboptimal exploration of potential solutions. In this paper, we introduce a novel reheating mechanism inspired by the concept of critical temperature and specific heat in physics, aimed at overcoming this limitation. Empirically, our method demonstrates superiority over existing sampling-based and data-driven algorithms across a diverse array of CO problems.