Leenen, LAnbulaganMeyer, TGhose, A2009-03-042009-03-042007-12Leenen, 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.978-3-540-76926-2http://hdl.handle.net/10204/3115Proceedings published in Lecture Notes in Computer Science no. 4830, pp202-212 Copyright: 2007 Springer-Verlag.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-SATenWeighted maximum satisfiability problemConstraints satisfaction problemsSemiring constraint satisfaction frameworkConference PresentationLeenen, 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/3115Leenen, 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/3115Leenen 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 .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 -