Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-14T00:18:21.542Z Has data issue: false hasContentIssue false
  • English
  • Français

SUNNY-CP and the MiniZinc challenge*

Published online by Cambridge University Press:  10 August 2017

ROBERTO AMADINI ,
MAURIZIO GABBRIELLI  and
JACOPO MAURO
ROBERTO AMADINI
Affiliation:
Department of Computing and Information Systems, The University of Melbourne, Australia (e-mail: roberto.amadini@unimelb.edu.au)
MAURIZIO GABBRIELLI
Affiliation:
DISI, University of Bologna, Italy/FOCUS Research Team, Bologna, Italy (e-mail: gabbri@cs.unibo.it)
JACOPO MAURO
Affiliation:
Department of Informatics, University of Oslo, Norway (e-mail: jmauro@ifi.uio.no)
Get access Rights & Permissions [Opens in a new window]

Abstract

In Constraint Programming, a portfolio solver combines a variety of different constraint solvers for solving a given problem. This fairly recent approach enables to significantly boost the performance of single solvers, especially when multicore architectures are exploited. In this work, we give a brief overview of the portfolio solver sunny-cp, and we discuss its performance in the MiniZinc Challenge—the annual international competition for Constraint Programming solvers—where it won two gold medals in 2015 and 2016.

Keywords

Constraint ProgrammingAlgorithm SelectionAlgorith PortfoliosMiniZinc
Type
Technical Note
Information
Theory and Practice of Logic Programming , Volume 18 , Issue 1 , January 2018 , pp. 81 - 96
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

This work was supported by the EU project FP7-644298 HyVar: Scalable Hybrid Variability for Distributed, Evolving Software Systems

References

Amadini, R., Biselli, F., Gabbrielli, M., Liu, T. and Mauro, J. 2015. SUNNY for algorithm selection: A preliminary study. In Proc. 30th Italian Conference on Computational Logic, Ancona, D., Maratea, M. and Mascardi, V., Eds. CEUR Workshop Proceedings, vol. 1459, July 1–3, 2015, Genova, Italy, CEUR-WS.org, 202–206.Google Scholar
Amadini, R., Gabbrielli, M. and Mauro, J. 2014a. An enhanced features extractor for a portfolio of constraint solvers. In Symposium on Applied Computing, SAC 2014, Cho, Y., Shin, S. Y., Kim, S., Hung, C., and Hong, J., Eds. March 24–28, 2014, ACM, Gyeongju, Republic of Korea, 1357–1359.Google Scholar
Amadini, R., Gabbrielli, M. and Mauro, J. 2014b. SUNNY: A lazy portfolio approach for constraint solving. In TPLP 14, 509–524.Google Scholar
Amadini, R., Gabbrielli, M. and Mauro, J. 2015a. A Multicore tool for constraint solving. In Proc. of the 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, Yang, Q. and Wooldridge, M., Eds. July 25–31, 2015, AAAI Press, Buenos Aires, Argentina, 232–238.Google Scholar
Amadini, R., Gabbrielli, M. and Mauro, J. 2015b. SUNNY-CP: A sequential CP portfolio solver. In Proc. of the 30th Annual ACM Symposium on Applied Computing, Wainwright, R. L., Corchado, J. M., Bechini, A. and Hong, J., Eds. April 13–17, 2015, ACM, Salamanca, Spain, 1861–1867.CrossRefGoogle Scholar
Amadini, R., Gabbrielli, M. and Mauro, J. 2015c. Why CP portfolio solvers are (under)utilized? Issues and challenges. In Proc. of Logic-Based Program Synthesis and Transformation – 25th International Symposium, LOPSTR 2015, Falaschi, M., Ed. Revised Selected Papers, Lecture Notes in Computer Science, July 13–15, 2015, vol. 9527. Springer, Siena, Italy, 349–364.Google Scholar
Amadini, R., Gabbrielli, M. and Mauro, J. 2016a. Parallelizing constraint solvers for hard RCPSP instances. In Learning and Intelligent Optimization – 10th International Conference, LION 10, Festa, P., Sellmann, M. and Vanschoren, J., Eds. Revised Selected Papers, Lecture Notes in Computer Science, May 29–June 1, 2016, vol. 10079. Springer, Ischia, Italy, 227–233.CrossRefGoogle Scholar
Amadini, R., Gabbrielli, M. and Mauro, J. 2016b. Portfolio approaches for constraint optimization problems. Annals of Mathematics and Artificial Intelligence 76, 1–2, 229–246.Google Scholar
Amadini, R. and Stuckey, P. J. 2014. Sequential time splitting and bounds communication for a portfolio of optimization solvers. In Proc. of Principles and Practice of Constraint Programming – 20th International Conference, CP 2014, O'Sullivan, B., Ed. Lecture Notes in Computer Science, September 8–12, 2014, vol. 8656. Springer, Lyon, France, 108–124.Google Scholar
Belov, G., Stuckey, P. J., Tack, G. and Wallace, M. 2016. Improved linearization of constraint programming models. In Proc. of Principles and Practice of Constraint Programming – 22nd International Conference, CP 2016, Rueher, M., Ed. Lecture Notes in Computer Science, September 5–9, 2016, vol. 9892. Springer, Toulouse, France, 49–65.Google Scholar
Chevaleyre, Y., Endriss, U., Lang, J. and Maudet, N. 2007. A short introduction to computational social choice. In Proc. of SOFSEM 2007: Theory and Practice of Computer Science, 33rd Conference on Current Trends in Theory and Practice of Computer Science, van Leeuwen, J., Italiano, G. F., van der Hoek, W., Meinel, C., Sack, H. and Plasil, F., Eds. Lecture Notes in Computer Science, January 20–26, 2007, vol. 4362. Springer, Harrachov, Czech Republic, 51–69.Google Scholar
Chuffed. 2016. Chuffed Solver. URL: https://github.com/geoffchu/chuffed.Google Scholar
coseal. 2014. Algorithm Selection Library. URL: http://www.coseal.net/.Google Scholar
de Cat, B., Bogaerts, B., Devriendt, J. and Denecker, M. 2013. Model expansion in the presence of function symbols using constraint programming. In Proc. of IEEE 25th International Conference on Tools with Artificial Intelligence, November 4–6, 2013, IEEE Computer Society, Herndon, VA, USA, 1068–1075.Google Scholar
Gomes, C. P. and Selman, B. 2001. Algorithm portfolios. Artificial Intelligence 126, 1–2, 43–62.CrossRefGoogle Scholar
Hebrard, E., O'Mahony, E. and O'Sullivan, B. 2010. Constraint programming and combinatorial optimisation in numberjack. In Proc. of Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010, Lodi, A., Milano, M. and Toth, P., Eds. Lecture Notes in Computer Science, June 14–18, 2010, vol. 6140. Springer, Bologna, Italy, 181–185.Google Scholar
Hutter, F., Xu, L., Hoos, H. H. and Leyton-Brown, K. 2014. Algorithm runtime prediction: Methods & evaluation. Artificial Intelligence 206, 79–111.CrossRefGoogle Scholar
iZplus. 2016. iZplus Solver Description. URL: https://www.minizinc.org/challenge2016/description_izplus.txt.Google Scholar
JaCoP. 2016. JaCoP Solver. URL: http://jacop.osolpro.com/.Google Scholar
Kotthoff, L. 2014. Algorithm selection for combinatorial search problems: A survey. AI Magazine 35, 3, 48–60.CrossRefGoogle Scholar
Kotthoff, L. 2015. ICON challenge on algorithm selection. CoRR abs/1511.04326.Google Scholar
Lindauer, M., Bergdoll, R. and Hutter, F. 2016. An empirical study of per-instance algorithm scheduling. In Proc. of Learning and Intelligent Optimization – 10th International Conference, LION 10, Festa, P., Sellmann, M. and Vanschoren, J., Eds. Revised Selected Papers, Lecture Notes in Computer Science, May 29–June 1, 2016, vol. 10079. Springer, Ischia, Italy, 253–259.Google Scholar
Malitsky, Y., Sabharwal, A., Samulowitz, H. and Sellmann, M. 2012. Parallel SAT Solver Selection and Scheduling. In Proc. of Principles and Practice of Constraint Programming – 18th International Conference, CP 2012, Milano, M., Ed. Lecture Notes in Computer Science, October 8–12, 2012, vol. 7514. Springer, Québec City, Canada, 512–526.Google Scholar
MiniZinc. 2016. MiniZinc Software. URL: https://www.minizinc.org/software.html.Google Scholar
Mistral. 2016. Mistral Solver. URL: https://github.com/ehebrard/Mistral-2.0.Google Scholar
Nethercote, N., Stuckey, P. J., Becket, R., Brand, S., Duck, G. J. and Tack, G. 2007. MiniZinc: Towards a standard CP modelling language. In Proc. of Principles and Practice of Constraint Programming – CP 2007, 13th International Conference, CP 2007, Bessiere, C., Ed. Lecture Notes in Computer Science, September 23–27, 2007, vol. 4741. Springer, Providence, RI, USA, 529–543.Google Scholar
O'Mahony, E., Hebrard, E., Holland, A., Nugent, C. and O'Sullivan, B. 2008, August. Using case-based reasoning in an algorithm portfolio for constraint solving. In Irish conference on artificial intelligence and cognitive science (pp. 210-216).Google Scholar
Opturion CPX. 2016. Opturion CPX Solver. URL: http://www.opturion.com/.Google Scholar
OR-Tools. 2016. OR-Tools Solver. URL: https://github.com/google/or-tools.Google Scholar
Prud'homme, C., Fages, J.-G. and Lorca, X. 2016. Choco Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S.Google Scholar
Rice, J. R. 1976. The Algorithm Selection Problem. Advances in Computers 15, 65–118.CrossRefGoogle Scholar
Rossi, F., Beek, P. V. and Walsh, T. 2006. Handbook of Constraint Programming (Foundations of Artificial Intelligence). Elsevier Science Inc., New York, NY, USA.Google Scholar
Sabharwal, A. and Samulowitz, H. 2014. Insights into Parallelism with Intensive Knowledge Sharing. In Proc. of Principles and Practice of Constraint Programming – 20th International Conference, CP 2014, O'Sullivan, B., Ed. Lecture Notes in Computer Science, September 8–12, 2014, vol. 8656. Springer, Lyon, France, 655–671.Google Scholar
Smith-Miles, K. 2008. Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Computing Surveys 41, 1, 6:1–6:25.Google Scholar
Stuckey, P. J., Feydy, T., Schutt, A., Tack, G. and Fischer, J. 2014. The MiniZinc challenge 2008–2013. AI Magazine 35, 2, 55–60.Google Scholar
Veksler, M. and Strichman, O. 2016. Learning general constraints in CSP. Artificial Intelligence 238, 135–153.Google Scholar
Zhou, N. and Kjellerstrand, H. 2016. The Picat-SAT Compiler. In Practical Aspects of Declarative Languages – 18th International Symposium, PADL 2016, Gavanelli, M. and Reppy, J. H., Eds. Lecture Notes in Computer Science, January 18–19, 2016, vol. 9585. Springer, St. Petersburg, FL, USA, 48–62.Google Scholar