Probabilistic Techniques For Constraint Satisfaction Problems

Abstract

Constraint satisfaction problems (CSPs) are at the core of many tasks with direct practical relevance, such as hardware and software verification, planning, and scheduling to name a few. The two main solution paradigms for solving such problems are based on backtrack-style search and local search. However, recently, a new powerful technique, called survey propagation (SP), was introduced. SP can solve certain classes of problem instances with millions of variables and constraints. This discovery raised a question of whether the traditional techniques are the best one can do when tackling large and important constraint satisfaction problems. This dissertation discusses non-traditional approaches to solving CSPs. The techniques we use include probabilistic inference, statistical tools and a combination of systematic and local search. We provide a new derivation of SP based on purely combinatorial insights. Our method also enables us to derive SP-style procedures for a diverse range of constraint satisfaction problems, and provides insights into structure of solution spaces. The second part of the dissertation describes approaches to counting number of solutions of a CSP with the help of Belief Propagation and statistics. We also provide a novel hybrid algorithm for minimizing the number of violated constraints, which employs both systematic and local search, harnessing their complementary strengths. These methods are the most scalable algorithms for certain hard to solve classes of Boolean satisfiability (SAT), model counting (#SAT), and maximum satisfiability (MaxSAT) problems.