Temperature dependent sampling in hard satisfiability problems
2008 (English)Article in journal (Other academic) Submitted
The solution sets of constraint satisfaction problems (CSPs)have been conjectured to to split up into clusters (connectedcomponents) when they are close to critically constrained,and this has been assumed to be related to computationalhardness. Simple stochastic local search (SLS) heuristics hashowever shown to be very efficient for many of these problems,and it has been unclear if this is related to clustering.In this work an SLS is used to sample the space of solutionsand the results are compared to the actual solution space generatedwith a complete solver. We show that different heuristicsfind different types of clusters. An increased greedinessresults in a sampling more uniform over the set of clusters,rather than over the set of solutions and the fastest solver visitsthe smaller cluster much more frequently than its solutionsdensity would imply. We also show that the level of randomness(temperature) is related in a non-trivial way to the abilityto escape from local minimas. This approach confirms thatclusters are important in understanding computational hardnessand may begin to explain the efficiency of SLSs in fragmentedsolution spaces.
Place, publisher, year, edition, pages
IdentifiersURN: urn:nbn:se:kth:diva-8494OAI: oai:DiVA.org:kth-8494DiVA: diva2:13833
QS 201203142008-05-192008-05-192012-03-14Bibliographically approved