DSpace
 

Researchspace >
General science, engineering & technology >
General science, engineering & technology >
General science, engineering & technology >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10204/3115

Title: Modeling and solving semiring constraint satisfaction problems by transformation to weighted semiring Max-SAT
Authors: Leenen, L
Anbulagan
Meyer, T
Ghose, A
Keywords: Weighted maximum satisfiability problem
Constraints satisfaction problems
Semiring constraint satisfaction framework
Issue Date: Dec-2007
Publisher: Springer-Verlag
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.
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
Description: Proceedings published in Lecture Notes in Computer Science no. 4830, pp202-212 Copyright: 2007 Springer-Verlag.
URI: http://hdl.handle.net/10204/3115
ISBN: 978-3-540-76926-2
Appears in Collections:Command control and information warfare
General science, engineering & technology

Files in This Item:

File Description SizeFormat
Leenen1_2007.pdf355.67 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback