Set constraint model and automated encoding into SAT: application to the social golfer problem

Frédéric Lardeux (), Eric Monfroy (), Broderick Crawford () and Ricardo Soto ()

Annals of Operations Research, 2015, vol. 235, issue 1, 423-452

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. Copyright Springer Science+Business Media New York 2015

Keywords: Constraint programming; CSP; Set constraints; SAT encoding; Social golfer problem (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-015-1914-5 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:235:y:2015:i:1:p:423-452:10.1007/s10479-015-1914-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-1914-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().