Modelling Max-CSP as Partial Max-SAT

View/ Open
Issue date
2008Suggested 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.
Metadata
Show full item recordAbstract
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.
Is part of
Lecture Notes in Computer Science, 2008, vol. 4996, p. 1-14European research projects
Collections
Related items
Showing items related by title, author, creator and subject.
-
Generating Hard Satisfiable Scheduling Instances
Argelich Romà, Josep; Béjar Torres, Ramón; Cabiscol i Teixidó, Alba; Fernàndez Camon, César; Manyà Serres, Felip; Gomes, Carla (European Conference on Planning, 2013)We present a random generator of partially complete round robin timetables that produces exclusively satisfiable instances, and provide experimental evidence that there is an easy-hard-easy pattern in the computational ... -
The first and second Max-SAT evaluations
Argelich Romà, Josep; Li, Chu-Min; Manyà Serres, Felip; Planes Cid, Jordi (IOS Press, 2008)We describe the organization and report on the results of the First and Second Max-SAT Evaluations, which were organized as affiliated events of the 2006 and 2007 editions of the International Conference on Theory and ... -
Analyzing the instances of the MaxSAT evaluation
Argelich Romà, Josep; Li, Chu-Min; Manyà Serres, Felip; Planes Cid, Jordi (Springer Verlag, 2011)The MaxSAT Evaluation [1] is an affiliated event of the SAT Conference that is held every year since 2006, and is devoted to empirically evaluate exact MaxSAT algorithms solving any of the following problems: MaxSAT, ...