Cakewalk Sampling
This work addresses the challenge of improving local search methods in combinatorial optimization for practitioners, though it appears incremental as it builds on existing sampling and local search techniques.
The authors tackled the problem of finding good local optima in combinatorial optimization by developing an adaptive sampling algorithm that adjusts distributions towards these optima. They demonstrated its effectiveness by outperforming related methods in recovering locally maximal cliques and achieving superior performance in k-medoid clustering when combined with greedy algorithms.
We study the task of finding good local optima in combinatorial optimization problems. Although combinatorial optimization is NP-hard in general, locally optimal solutions are frequently used in practice. Local search methods however typically converge to a limited set of optima that depend on their initialization. Sampling methods on the other hand can access any valid solution, and thus can be used either directly or alongside methods of the former type as a way for finding good local optima. Since the effectiveness of this strategy depends on the sampling distribution, we derive a robust learning algorithm that adapts sampling distributions towards good local optima of arbitrary objective functions. As a first use case, we empirically study the efficiency in which sampling methods can recover locally maximal cliques in undirected graphs. Not only do we show how our adaptive sampler outperforms related methods, we also show how it can even approach the performance of established clique algorithms. As a second use case, we consider how greedy algorithms can be combined with our adaptive sampler, and we demonstrate how this leads to superior performance in k-medoid clustering. Together, these findings suggest that our adaptive sampler can provide an effective strategy to combinatorial optimization problems that arise in practice.