TítuloModelling Max-CSP as Partial Max-SAT
Publication TypeConference Paper
Year of Publication2008
AuthorsArgerlich J., Cabiscol A, Lynce I, Manyà F
Conference Name11th International Conference on Theory and Applications of Satisfiability Testing (SAT-2008)
Conference LocationGuangzhou, China
Palabras claveMax-CSP, Max-SAT

We define a number of original encodings that map Max-CSP 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.