Title
Set constraint model and automated encoding into SAT: application to the social golfer problem
Date Issued
01 December 2015
Access level
open access
Resource Type
journal article
Author(s)
Pontificia Universidad Católica de Valparaiso
Publisher(s)
Springer New York LLC
Abstract
On the one hand, constraint satisfaction problems allow one to expressively model problems. On the other hand, propositional satisfiability problem (SAT) solvers can handle huge SAT instances. We thus present a technique to expressively model set constraint problems and to encode them automatically into SAT instances. We apply our technique to the social golfer problem and we also use it to break symmetries of the problem. Our technique is simpler, more expressive, and less error-prone than direct modeling. The SAT instances that we automatically generate contain less clauses than improved direct instances such as in Triska and Musliu (Ann Oper Res 194(1):427–438, 2012), and with unit propagation they also contain less variables. Moreover, they are well-suited for SAT solvers and they are solved faster as shown when solving difficult instances of the social golfer problem.
Start page
423
End page
452
Volume
235
Issue
1
Language
English
OCDE Knowledge area
Informática y Ciencias de la Información
Subjects
Scopus EID
2-s2.0-84948077628
Source
Annals of Operations Research
ISSN of the container
02545330
Sources of information:
Directorio de Producción Científica
Scopus