Local-Search Techniques for Boolean Combinations of Pseudo-Boolean Constraints
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 propositional 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.
Cite
Text
Liu and Truszczynski. "Local-Search Techniques for Boolean Combinations of Pseudo-Boolean Constraints." AAAI Conference on Artificial Intelligence, 2006.Markdown
[Liu and Truszczynski. "Local-Search Techniques for Boolean Combinations of Pseudo-Boolean Constraints." AAAI Conference on Artificial Intelligence, 2006.](https://mlanthology.org/aaai/2006/liu2006aaai-local/)BibTeX
@inproceedings{liu2006aaai-local,
title = {{Local-Search Techniques for Boolean Combinations of Pseudo-Boolean Constraints}},
author = {Liu, Lengning and Truszczynski, Miroslaw},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2006},
pages = {98-103},
url = {https://mlanthology.org/aaai/2006/liu2006aaai-local/}
}