Max-SAT formalisms with hard and soft constraints

Article type: Other

Authors: Argelich, Josep

Affiliations: Universitat de Lleida, Lleida, Spain. E-mail: jargelich@diei.udl.cat

Abstract: The study of Max-SAT formalisms and the development of fast Max-SAT solvers have become very active research topics in the last few years. This PhD dissertation focus on the design, implementation and evaluation of solving techniques for two Max-SAT formalisms that incorporate the notion of partiality. The first one, called Block-SAT, is a new formalism that deals with blocks of clauses instead of individual clauses. The second one is Partial Max-SAT, which has become a standard in the community. For each formalism, we compare our solvers with state-of-the-art solvers using an exhaustive test suite. The empirical results provide evidence that the proposed solving techniques are competitive and often produce important speed-ups.

Keywords: Block-SAT, Partial Max-SAT, solvers

DOI: 10.3233/AIC-2010-0488

Journal: AI Communications, vol. 24, no. 1, pp. 101-103, 2011