| dc.contributor.author | Argelich Romà, Josep | |
| dc.contributor.author | Manyà Serres, Felip | |
| dc.date.accessioned | 2016-06-23T07:58:13Z | |
| dc.date.issued | 2005 | |
| dc.identifier.issn | 0302-9743 | |
| dc.identifier.uri | http://hdl.handle.net/10459.1/57269 | |
| dc.description.abstract | We present a new generic problem solving approach for overconstrained
problems based on Max-SAT. We first define a clausal form
formalism that deals with blocks of clauses instead of individual clauses,
and that allows one to declare each block either as hard (i.e., must be
satisfied by any solution) or soft (i.e., can be violated by some solution).
We then present two Max-SAT solvers that find a truth assignment
that satisfies all the hard blocks of clauses and the maximum number
of soft blocks of clauses. Our solvers are branch and bound algorithms
equipped with original lazy data structures; the first one incorporates
static variable selection heuristics while the second one incorporates dynamic
variable selection heuristics. Finally, we present an experimental
investigation to assess the performance of our approach on a representative
sample of instances (random 2-SAT, Max-CSP, and graph coloring). | ca_ES |
| dc.description.sponsorship | Research partially supported by projects TIN2004-07933-C3-03 and TIC2003-00950 funded by the Ministerio de Educación y Ciencia. The second author is supported by a grant Ramón y Cajal. | ca_ES |
| dc.language.iso | eng | ca_ES |
| dc.publisher | Springer Verlag | ca_ES |
| dc.relation | MIECI/PN2004-2007/TIN2004-07933-C3-03 | ca_ES |
| dc.relation | MICYT/PN2000-2003/TIC2003-00950 | ca_ES |
| dc.relation.isformatof | Versió postprint del document publicat a https://doi.org/10.1007/11499107_1 | ca_ES |
| dc.relation.ispartof | Lecture Notes in Computer Science, 2005, vol. 3569, p. 1-15 | ca_ES |
| dc.rights | (c) Springer Verlag, 2005 | ca_ES |
| dc.title | Solving Over-Constrained Problems with SAT Technology | ca_ES |
| dc.type | article | ca_ES |
| dc.identifier.idgrec | 007826 | |
| dc.type.version | acceptedVersion | ca_ES |
| dc.rights.accessRights | info:eu-repo/semantics/openAccess | ca_ES |
| dc.identifier.doi | https://doi.org/10.1007/11499107_1 | |
