×

zbMATH — the first resource for mathematics

SUNNY: a lazy portfolio approach for constraint solving. (English) Zbl 1307.68077
Summary: Within the context of constraint solving, a portfolio approach allows one to exploit the synergy between different solvers in order to create a globally better solver. In this paper we present SUNNY: a simple and flexible algorithm that takes advantage of a portfolio of constraint solvers in order to compute – without learning an explicit model – a schedule of them for solving a given Constraint Satisfaction Problem (CSP). Motivated by the performance reached by SUNNY vs. different simulations of other state of the art approaches, we developed sunny-csp, an effective portfolio solver that exploits the underlying SUNNY algorithm in order to solve a given CSP. Empirical tests conducted on exhaustive benchmarks of MiniZinc models show that the actual performance of sunny-csp conforms to the predictions. This is encouraging both for improving the power of CSP portfolio solvers and for trying to export them to fields such as Answer Set Programming and Constraint Logic Programming.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68N17 Logic programming
68T05 Learning and adaptive systems in artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] AAAI (2010)
[2] CP (2007)
[3] DOI: 10.1016/0004-3702(77)90007-8 · Zbl 0341.68061 · doi:10.1016/0004-3702(77)90007-8
[4] ECAI (2010)
[5] CP (2011)
[6] ICLP pp 744– (2008)
[7] DOI: 10.1016/S0004-3702(00)00081-3 · Zbl 0969.68047 · doi:10.1016/S0004-3702(00)00081-3
[8] AI Commun. 24 pp 147– (2011)
[9] LPNMR pp 352– (2011)
[10] DOI: 10.1214/09-SS054 · Zbl 1190.62080 · doi:10.1214/09-SS054
[11] CPAIOR pp 380– (2004)
[12] CPAIOR (2013)
[13] ACM Comput. Surv. 41 (2008)
[14] SAT pp 422– (2013)
[15] DOI: 10.1016/S0065-2458(08)60520-3 · doi:10.1016/S0065-2458(08)60520-3
[16] DOI: 10.1007/s10601-008-9051-2 · Zbl 1183.68589 · doi:10.1007/s10601-008-9051-2
[17] CP pp 574– (2007)
[18] SAT pp 326– (2009)
[19] JELIA pp 484– (2012)
[20] CPAIOR (2012)
[21] IJCAI (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.