Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-23T10:56:35.541Z Has data issue: false hasContentIssue false
  • English
  • Français

claspfolio 2: Advances in Algorithm Selection for Answer Set Programming

Published online by Cambridge University Press:  21 July 2014

HOLGER HOOS ,
MARIUS LINDAUER  and
TORSTEN SCHAUB
HOLGER HOOS
Affiliation:
University of British Columbia, Canada
MARIUS LINDAUER
Affiliation:
University of Freiburg, Germany University of Potsdam, Germany
TORSTEN SCHAUB
Affiliation:
University of Potsdam, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

Building on the award-winning, portfolio-based ASP solver claspfolio, we present claspfolio 2, a modular and open solver architecture that integrates several different portfolio-based algorithm selection approaches and techniques. The claspfolio 2 solver framework supports various feature generators, solver selection approaches, solver portfolios, as well as solver-schedule-based pre-solving techniques. The default configuration of claspfolio 2 relies on a light-weight version of the ASP solver clasp to generate static and dynamic instance features. The flexible open design of claspfolio 2 is a distinguishing factor even beyond ASP. As such, it provides a unique framework for comparing and combining existing portfolio-based algorithm selection approaches and techniques in a single, unified framework. Taking advantage of this, we conducted an extensive experimental study to assess the impact of different feature sets, selection approaches and base solver portfolios. In addition to gaining substantial insights into the utility of the various approaches and techniques, we identified a default configuration of claspfolio 2 that achieves substantial performance gains not only over clasp's default configuration and the earlier version of claspfolio, but also over manually tuned configurations of clasp.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Special Issue 4-5: 30th International Conference on Logic Programming , July 2014 , pp. 569 - 585
Copyright
Copyright © Cambridge University Press 2014 

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.)

References

Alviano, M., Dodaro, C., Faber, W., Leone, N., and Ricca, F. 2013. WASP: A native asp solver based on constraint learning. In Proceedings of the Twelfth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13), Cabalar, P. and Son, T., Eds. Lecture Notes in Artificial Intelligence, vol. 8148. Springer-Verlag, 54–66.Google Scholar
Ansótegui, C., Sellmann, M., and Tierney, K. 2009. A gender-based genetic algorithm for the automatic configuration of algorithms. In Proceedings of the Fifteenth International Conference on Principles and Practice of Constraint Programming (CP'09), Gent, I., Ed. Lecture Notes in Computer Science, vol. 5732. Springer-Verlag, 142–157.Google Scholar
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press.Google Scholar
Bessiere, C., Ed. 2007. Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming (CP'07). Lecture Notes in Computer Science, vol. 4741. Springer-Verlag.Google Scholar
Bishop, C. 2007. Pattern Recognition and Machine Learning (Information Science and Statistics), 1st ed. 2006. Corr. 2nd printing ed. Springer.Google Scholar
Calimeri, F., Ianni, G., and Ricca, F. 2011. Third ASP competition - file and language formats. Tech. rep., Università della Calabria.Google Scholar
Collautti, M., Malitsky, Y., Mehta, D. and O'Sullivan, B. 2013. SNAPP: Solver-based nearest neighbor for algorithm portfolios. In Proceedings of the Twenty-Fourth European Conference on Machine Learning (ECML'13), Zelezny, F., Ed. Lecture Notes in Computer Science. Springer-Verlag.Google Scholar
Dovier, A. and Santos Costa, V., Eds. 2012. Technical Communications of the Twenty-eighth International Conference on Logic Programming (ICLP'12). Vol. 17. Leibniz International Proceedings in Informatics (LIPIcs).Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., and Schneider, M. 2011. Potassco: The Potsdam answer set solving collection. AI Communications 24, 2, 107–124.CrossRefGoogle Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T., Schneider, M., and Ziller, S. 2011. A portfolio solver for answer set programming: Preliminary report. In Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11), Delgrande, J. and Faber, W., Eds. Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag, 352–357.Google Scholar
Giunchiglia, E., Lierler, Y., and Maratea, M. 2006. Answer set programming based on propositional satisfiability. Journal of Automated Reasoning 36, 4, 345–377.CrossRefGoogle Scholar
Helmert, M., Röger, G., and Karpas, E. 2011. Fast downward stone soup: A baseline for building planner portfolios. In ICAPS 2011 Workshop on Planning and Learning. 28–35.Google Scholar
Hoos, H. 2012. Programming by optimisation. Communications of the ACM 55, 70–80.Google Scholar
Hoos, H., Kaminski, R., Lindauer, M., and Schaub, T. 2014. aspeed: Solver scheduling via answer set programming. Theory and Practice of Logic Programming First View, 1–26. Available at http://arxiv.org/abs/1401.1024 CrossRefGoogle Scholar
Hoos, H., Kaufmann, B., Schaub, T., and Schneider, M. 2013. Robust benchmark set selection for boolean constraint solvers. See Pardalos and Nicosia (2013), 138–152.Google Scholar
Huberman, B., Lukose, R., and Hogg, T. 1997. An economic approach to hard computational problems. Science 275, 51–54.CrossRefGoogle ScholarPubMed
Hutter, F., Hoos, H., and Leyton-Brown, K. 2011. Sequential model-based optimization for general algorithm configuration. In Proceedings of the Fifth International Conference on Learning and Intelligent Optimization (LION'11). Lecture Notes in Computer Science, vol. 6683. Springer-Verlag, 507–523.Google Scholar
Hutter, F., Hoos, H., and Stützle, T. 2007. Automatic algorithm configuration based on local search. In Proceedings of the Twenty-second National Conference on Artificial Intelligence (AAAI'07). AAAI Press, 1152–1157.Google Scholar
Hutter, F., Xu, L., Hoos, H. H., and Leyton-Brown, K. 2012. Algorithm runtime prediction: The state of the art. Artificial Intelligence.Google Scholar
Janhunen, T. 2006. Some (in)translatability results for normal logic programs and propositional theories. Journal of Applied Non-Classical Logics 16, 1-2, 35–86.Google Scholar
Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., and Sellmann, M. 2011. Algorithm selection and scheduling. In Proceedings of the Seventeenth International Conference on Principles and Practice of Constraint Programming (CP'11), Lee, J., Ed. Lecture Notes in Computer Science, vol. 6876. Springer-Verlag, 454–469.Google Scholar
Kadioglu, S., Malitsky, Y., Sellmann, M., and Tierney, K. 2010. ISAC – instance-specific algorithm configuration. In Proceedings of the Nineteenth European Conference on Artificial Intelligence (ECAI'10), Coelho, H., Studer, R., and Wooldridge, M., Eds. IOS Press, 751–756.Google Scholar
Kotthoff, L. 2013. LLAMA: leveraging learning to automatically manage algorithms. Tech. rep., Cork Constraint Computation Centre. published at arXiv.Google Scholar
Kotthoff, L., Gent, I. P., and Miguel, I. 2012. An evaluation of machine learning in algorithm selection for search problems. AI Communications 25, 3, 257–270.Google Scholar
Liu, G., Janhunen, T., and Niemel, I. 2012. Answer set programming via mixed integer programming. In Proceedings of the Thirteenth International Conference on Principles of Knowledge Representation and Reasoning (KR'12), Brewka, G., Eiter, T., and McIlraith, S., Eds. AAAI Press, 32–42.Google Scholar
Malitsky, Y., Sabharwal, A., Samulowitz, H., and Sellmann, M. 2013. Boosting sequential solver portfolios: Knowledge sharing and accuracy prediction. See Pardalos and Nicosia (2013), 153–167.Google Scholar
Maratea, M., Pulina, L., and Ricca, F. 2012. Applying machine learning techniques to ASP solving. See Dovier and Santos Costa (2012), 37–48.Google Scholar
Maratea, M., Pulina, L., and Ricca, F. 2013. A multi-engine approach to answer-set programming. Theory and Practice of Logic Programming First View, 1–28.Google Scholar
Nguyen, M., Janhunen, T., and Niemelä, I. 2013. Translating answer-set programs into bit-vector logic. In Proceedings of the Nineteenth International Conference on Applications of Declarative Programming and Knowledge Management (INAP'11) and the Twenty-fifth Workshop on Logic Programming (WLP'11), Tompits, H., Abreu, S., Oetsch, J., Pührer, J., Seipel, D., Umeda, M., and Wolf, A., Eds. Lecture Notes in Computer Science, vol. 7773. Springer-Verlag, 105–116.Google Scholar
O'Mahony, E., Hebrard, E., Holland, A., Nugent, C. and O'Sullivan, B. 2008. Using case-based reasoning in an algorithm portfolio for constraint solving. In Proceedings of the Nineteenth Irish Conference on Artificial Intelligence and Cognitive Science (AICS'08), Bridge, D., Brown, K., O'Sullivan, B., and Sorensen, H., Eds.Google Scholar
Pardalos, P. and Nicosia, G., Eds. 2013. Proceedings of the Seventh International Conference on Learning and Intelligent Optimization (LION'13). Lecture Notes in Computer Science, vol. 7997. Springer-Verlag.Google Scholar
Pulina, L. and Tacchella, A. 2007. A multi-engine solver for quantified boolean formulas. See Bessiere (2007), 574–589.Google Scholar
Rice, J. 1976. The algorithm selection problem. Advances in Computers 15, 65–118.Google Scholar
Seipp, J., Braun, M., Garimort, J., and Helmert, M. 2012. Learning portfolios of automatically tuned planners. In Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling (ICAPS'12), McCluskey, L., Williams, B., Silva, J. R., and Bonet, B., Eds. AAAI.Google Scholar
Silverthorn, B., Lierler, Y., and Schneider, M. 2012. Surviving solver sensitivity: An ASP practitioner's guide. See Dovier and Santos Costa (2012), 164–175.Google Scholar
Simons, P., Niemelä, I., and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 1-2, 181–234.Google Scholar
Syrjänen, T. Lparse 1.0 user's manual.Google Scholar
Xu, L., Hoos, H., and Leyton-Brown, K. 2007. Hierarchical hardness models for SAT. See Bessiere (2007), 696–711.Google Scholar
Xu, L., Hoos, H., and Leyton-Brown, K. 2010. Hydra: Automatically configuring algorithms for portfolio-based selection. In Proceedings of the Twenty-fourth National Conference on Artificial Intelligence (AAAI'10), Fox, M. and Poole, D., Eds. AAAI Press, 210–216.Google Scholar
Xu, L., Hutter, F., Hoos, H., and Leyton-Brown, K. 2008. SATzilla: Portfolio-based algorithm selection for SAT. Journal of Artificial Intelligence Research 32, 565–606.Google Scholar
Xu, L., Hutter, F., Hoos, H., and Leyton-Brown, K. 2009. SATzilla2009: An automatic algorithm portfolio for SAT. In SAT 2009 competitive events booklet: preliminary version, Le Berre, D., Roussel, O., Simon, L., Manquinho, V., Argelich, J., Li, C., Manyà, F., and Planes, J., Eds. 53–55. Available at http://www.cril.univ-artois.fr/SAT09/solvers/booklet.pdf Google Scholar
Xu, L., Hutter, F., Hoos, H., and Leyton-Brown, K. 2011. Hydra-MIP: Automated algorithm configuration and selection for mixed integer programming. In RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion at the International Joint Conference on Artificial Intelligence (IJCAI'11).Google Scholar
Xu, L., Hutter, F., Hoos, H., and Leyton-Brown, K. 2012. Evaluating component solver contributions to portfolio-based algorithm selectors. In Proceedings of the Fifteenth International Conference on Theory and Applications of Satisfiability Testing (SAT'12), Cimatti, A. and Sebastiani, R., Eds. Lecture Notes in Computer Science, vol. 7317. Springer-Verlag, 228–241.Google Scholar