On the use of walkSAT based algorithms for MLN inference in some realistic applications

International audienceWalkSAT is a local search algorithm conceived for solving SAT problems, which is also used for sampling possible worlds from a logical formula. This algorithm is used by Markov Logic Networks to perform slice sampling and give probabilities from a knowledge base defined with soft and hard constraints. In this paper, we will show that local search strategies, such as WalkSAT, may perform as poorly as a pure random walk on a category of problems that are quite common in industrial fields. We will also give some insights into the reasons that make random search algorithms intractable for these problems