dc.contributor.author |
Leenen, L
|
|
dc.contributor.author |
Anbulagan
|
|
dc.contributor.author |
Meyer, T
|
|
dc.contributor.author |
Ghose, A
|
|
dc.date.accessioned |
2009-03-04T12:01:31Z |
|
dc.date.available |
2009-03-04T12:01:31Z |
|
dc.date.issued |
2007-12 |
|
dc.identifier.citation |
Leenen, L, Anbulagan, Meyer, T and Ghose, A. 2007. Modeling and solving semiring constraint satisfaction problems by transformation to weighted semiring Max-SAT. Advances in Artificial Intelligence: 20th Australian Joint Conference on Artificial Intelligence, Gold Coast, Australia, 2-6 December, pp 10. |
en |
dc.identifier.isbn |
978-3-540-76926-2 |
|
dc.identifier.uri |
http://hdl.handle.net/10204/3115
|
|
dc.description |
Proceedings published in Lecture Notes in Computer Science no. 4830, pp202-212
Copyright: 2007 Springer-Verlag. |
en |
dc.description.abstract |
The authors present a variant of the Weighted Maximum Satisfiability Problem (Weighted Max-SAT), which is a modeling of the Semiring Constraint Satisfaction framework. They show how to encode a Semiring Constraint Satisfaction Problem (SCSP) into an instance of a propositional Weighted Max-SAT, and call the encoding Weighted Semiring Max-SAT (WS-Max-SAT). The clauses in their encoding are highly structured and they exploit this feature to develop two algorithms for solving WS-Max-SAT: an incomplete algorithm based on the well-known GSAT algorithm for Max-SAT, and a branch-and-bound algorithm which is complete. The authors’ preliminary experiments show that the translation of SCSP into WSMax-SAT is feasible, and that their branch-and-bound algorithm performs surprisingly well. They aim in future to combine the natural flexible representation of the SCSP framework with the inherent efficiencies of SAT solvers by adjusting existing SAT solvers to solve WS-Max-SAT |
en |
dc.language.iso |
en |
en |
dc.publisher |
Springer-Verlag |
en |
dc.subject |
Weighted maximum satisfiability problem |
en |
dc.subject |
Constraints satisfaction problems |
en |
dc.subject |
Semiring constraint satisfaction framework |
en |
dc.title |
Modeling and solving semiring constraint satisfaction problems by transformation to weighted semiring Max-SAT |
en |
dc.type |
Conference Presentation |
en |
dc.identifier.apacitation |
Leenen, L., Anbulagan, Meyer, T., & Ghose, A. (2007). Modeling and solving semiring constraint satisfaction problems by transformation to weighted semiring Max-SAT. Springer-Verlag. http://hdl.handle.net/10204/3115 |
en_ZA |
dc.identifier.chicagocitation |
Leenen, L, Anbulagan, T Meyer, and A Ghose. "Modeling and solving semiring constraint satisfaction problems by transformation to weighted semiring Max-SAT." (2007): http://hdl.handle.net/10204/3115 |
en_ZA |
dc.identifier.vancouvercitation |
Leenen L, Anbulagan, Meyer T, Ghose A, Modeling and solving semiring constraint satisfaction problems by transformation to weighted semiring Max-SAT; Springer-Verlag; 2007. http://hdl.handle.net/10204/3115 . |
en_ZA |
dc.identifier.ris |
TY - Conference Presentation
AU - Leenen, L
AU - Anbulagan
AU - Meyer, T
AU - Ghose, A
AB - The authors present a variant of the Weighted Maximum Satisfiability Problem (Weighted Max-SAT), which is a modeling of the Semiring Constraint Satisfaction framework. They show how to encode a Semiring Constraint Satisfaction Problem (SCSP) into an instance of a propositional Weighted Max-SAT, and call the encoding Weighted Semiring Max-SAT (WS-Max-SAT). The clauses in their encoding are highly structured and they exploit this feature to develop two algorithms for solving WS-Max-SAT: an incomplete algorithm based on the well-known GSAT algorithm for Max-SAT, and a branch-and-bound algorithm which is complete. The authors’ preliminary experiments show that the translation of SCSP into WSMax-SAT is feasible, and that their branch-and-bound algorithm performs surprisingly well. They aim in future to combine the natural flexible representation of the SCSP framework with the inherent efficiencies of SAT solvers by adjusting existing SAT solvers to solve WS-Max-SAT
DA - 2007-12
DB - ResearchSpace
DP - CSIR
KW - Weighted maximum satisfiability problem
KW - Constraints satisfaction problems
KW - Semiring constraint satisfaction framework
LK - https://researchspace.csir.co.za
PY - 2007
SM - 978-3-540-76926-2
T1 - Modeling and solving semiring constraint satisfaction problems by transformation to weighted semiring Max-SAT
TI - Modeling and solving semiring constraint satisfaction problems by transformation to weighted semiring Max-SAT
UR - http://hdl.handle.net/10204/3115
ER -
|
en_ZA |