Show simple item record

dc.contributor.authorArgelich Romà, Josep
dc.contributor.authorManyà Serres, Felip
dc.date.accessioned2016-06-23T07:58:13Z
dc.date.issued2005
dc.identifier.issn0302-9743
dc.identifier.urihttp://hdl.handle.net/10459.1/57269
dc.description.abstractWe 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.sponsorshipResearch 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.isoengca_ES
dc.publisherSpringer Verlagca_ES
dc.relationMIECI/PN2004-2007/TIN2004-07933-C3-03ca_ES
dc.relationMICYT/PN2000-2003/TIC2003-00950ca_ES
dc.relation.isformatofReproducció del document publicat a https://doi.org/10.1007/11499107_1ca_ES
dc.relation.ispartofLecture Notes in Computer Science, 2005, vol. 3569, p. 1-15ca_ES
dc.rights(c) Springer Verlag, 2005ca_ES
dc.titleSolving Over-Constrained Problems with SAT Technologyca_ES
dc.typearticleca_ES
dc.identifier.idgrec007826
dc.type.versionpublishedVersionca_ES
dc.rights.accessRightsinfo:eu-repo/semantics/restrictedAccessca_ES
dc.identifier.doihttps://doi.org/10.1007/11499107_1
dc.date.embargoEndDate10000-01-01


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record