TY - GEN
T1 - Local-search techniques for boolean combinations of pseudo-boolean constraints
AU - Liu, Lengning
AU - Truszczyński, Mirosław
PY - 2006
Y1 - 2006
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33750740738&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33750740738&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:33750740738
SN - 1577352815
SN - 9781577352815
T3 - Proceedings of the National Conference on Artificial Intelligence
SP - 98
EP - 103
BT - Proceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
T2 - 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
Y2 - 16 July 2006 through 20 July 2006
ER -