Modelling Max-CSP as Partial Max-SAT

Thumbnail
View/Open
Issue date
2008
Author
Argelich Romà, Josep
Cabiscol i Teixidó, Alba
Lynce, Inês
Manyà Serres, Felip
Suggested citation
Argelich Romà, Josep; Cabiscol i Teixidó, Alba; Lynce, Inês; Manyà Serres, Felip; . (2008) . Modelling Max-CSP as Partial Max-SAT. Lecture Notes in Computer Science, 2008, vol. 4996, p. 1-14. http://hdl.handle.net/10459.1/56663.
Impact

Google Scholar logo  Google Scholar
Share
Export to Mendeley
Metadata
Show full item record
Abstract
We define a number of original encodings that map MaxCSP instances into partial Max-SAT instances. Our encodings rely on the well-known direct and support encodings from CSP into SAT. Then, we report on an experimental investigation that was conducted to compare the performance profile of our encodings on random binary Max-CSP instances. Moreover, we define a new variant of the support encoding from CSP into SAT which produces fewer clauses than the standard support encoding.
URI
http://hdl.handle.net/10459.1/56663
Is part of
Lecture Notes in Computer Science, 2008, vol. 4996, p. 1-14
Collections