Publications

Modelling Max-CSP as Partial Max-SAT

Publication Type:

Conference Paper

Authors:

J. Argerlich; Alba Cabiscol; Ines Lynce; Felip Manyà

Source:

11th International Conference on Theory and Applications of Satisfiability Testing (SAT-2008), Springer, Volume 4996, Guangzhou, China, p.1-14 (2008)

Keywords:

Max-SAT; Max-CSP

Abstract:

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.

»