Local-search techniques for boolean combinations of pseudo-boolean constraints

Lengning Liu, Mirosław Truszczyński

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

Some search problems are most directly specified by boolean combinations of pseudo-boolean constraints. We study a logic PL(PB) whose formulas are of this form, and design local-search methods to compute models of PL(PB)-theories. In our approach we view a PL(PB)-theory T as a data structure -a concise representation of a certain prepositional CNF theory cl(T) logically equivalent to T. We show that parameters needed by local-search algorithms for CNF theories, such as walksat, can be estimated on the basis of T, without the need to compute cl(T) explicitly. Since cl(T) is often much larger than T, running search based on T promises performance gains. Our experimental results confirm this expectation.

Original languageEnglish
Title of host publicationProceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
Pages98-103
Number of pages6
StatePublished - 2006
Event21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06 - Boston, MA, United States
Duration: Jul 16 2006Jul 20 2006

Publication series

NameProceedings of the National Conference on Artificial Intelligence
Volume1

Conference

Conference21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
Country/TerritoryUnited States
CityBoston, MA
Period7/16/067/20/06

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Local-search techniques for boolean combinations of pseudo-boolean constraints'. Together they form a unique fingerprint.

Cite this