Cakewalk Sampling

Understand

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.