eCommons

 

Probabilistic Techniques For Constraint Satisfaction Problems

Other Titles

Author(s)

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.

Journal / Series

Volume & Issue

Description

Sponsorship

Date Issued

2009-10-13T20:09:10Z

Publisher

Keywords

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record