Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/162495
COMPARTIR / EXPORTAR:
SHARE CORE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | Solving Max-SAT as Weighted CSP |
Autor: | Givry, Simon de; Larrosa, Javier; Meseguer, Pedro CSIC ORCID ; Schiex, Thomas | Palabras clave: | Constraint programming Constraint theory Formal logic Computer programming MAX-SAT problems |
Fecha de publicación: | 2003 | Editor: | Springer Nature | Citación: | Principles and Practice of Constraint Programming – CP 2003: 9th International Conference, CP 2003. Proceedings. LNCS 2833: 363- 376 (2003) | Resumen: | For the last ten years, a significant amount of work in the constraint community has been devoted to the improvement of complete methods for solving soft constraints networks. We wanted to see how recent progress in the weighted CSP (WCSP) field could compete with other approaches in related fields. One of these fields is propositional logic and the well-known Max-SAT problem. In this paper, we show how Max-SAT can be encoded as a weighted constraint network, either directly or using a dual encoding. We then solve Max-SAT instances using state-of-the-art algorithms for weighted Max-CSP, dedicated Max-SAT solvers and the state-of-the-art MIP solver CPLEX. The results show that, despite a limited adaptation to CNF structure, WCSP-solver based methods are competitive with existing methods and can even outperform them, especially on the hardest, most over-constrained problems. © Springer-Verlag 2003. | URI: | http://hdl.handle.net/10261/162495 | DOI: | 10.1007/978-3-540-45193-8_25 | Identificadores: | doi: 10.1007/978-3-540-45193-8_25 issn: 0302-9743 isbn: 978-3-540-20202-8 |
Aparece en las colecciones: | (IIIA) Comunicaciones congresos |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
accesoRestringido.pdf | 15,38 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
SCOPUSTM
Citations
62
checked on 02-abr-2024
Page view(s)
245
checked on 18-abr-2024
Download(s)
84
checked on 18-abr-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.