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)
Volume4996
EditorialSpringer
Conference LocationGuangzhou, China
Paginación1-14
Palabras claveMax-CSP, Max-SAT
Resumen

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.