Universitat de Lleida
    • English
    • català
    • español
  • English 
    • English
    • català
    • español
  • Login
Repositori Obert UdL
View Item 
  •   Home
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • View Item
  •   Home
  • Recerca
  • Informàtica i Enginyeria Industrial
  • Articles publicats (Informàtica i Enginyeria Industrial)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Exact Max-SAT solvers for over-constrained problems

Thumbnail
View/Open
Postprint (380.6Kb)
Issue date
2006
Author
Argelich Romà, Josep
Manyà Serres, Felip
Suggested citation
Argelich Romà, Josep; Manyà Serres, Felip; . (2006) . Exact Max-SAT solvers for over-constrained problems. Journal of Heuristics, 2006, vol. 12, núm. 4, p. 375-392. https://doi.org/10.1007/s10732-006-7234-9.
Impact


Web of Science logo    citations in Web of Science

Scopus logo    citations in Scopus

Google Scholar logo  Google Scholar
Share
Export to Mendeley
Metadata
Show full item record
Abstract
We present a new generic problem solving approach for over-constrained problems based on Max-SAT. We first define a Boolean clausal form formalism, called soft CNF formulas, 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, powerful inference techniques, good quality lower bounds, and original variable selection heuristics. Finally, we report an experimental investigation on a representative sample of instances (random 2-SAT, Max-CSP, graph coloring, pigeon hole and quasigroup completion) which provides experimental evidence that our approach is very competitive compared with the state-of-the-art approaches developed in the CSP and SAT communities.
URI
http://hdl.handle.net/10459.1/57408
DOI
https://doi.org/10.1007/s10732-006-7234-9
Is part of
Journal of Heuristics, 2006, vol. 12, núm. 4, p. 375-392
European research projects
Collections
  • Articles publicats (Informàtica i Enginyeria Industrial) [990]
  • Publicacions de projectes de recerca del Plan Nacional [2958]
  • Grup de Recerca en Energia i Intel·ligència Artificial (GREiA) (INSPIRES) [488]

Contact Us | Send Feedback | Legal Notice
© 2023 BiD. Universitat de Lleida
Metadata subjected to 
 

 

Browse

All of the repositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

Statistics

View Usage Statistics

D'interès

Política institucional d'accés obertDiposita les teves publicacionsDiposita dades de recercaSuport a la recerca

Contact Us | Send Feedback | Legal Notice
© 2023 BiD. Universitat de Lleida
Metadata subjected to