×

Why CP portfolio solvers are (under)utilized? Issues and challenges. (English) Zbl 1473.68184

Falaschi, Moreno (ed.), Logic-based program synthesis and transformation. 25th international symposium, LOPSTR 2015, Siena, Italy, July 13–15, 2015. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 9527, 349-364 (2015).
Summary: It is well recognized that a single, arbitrarily efficient solver can be significantly outperformed by a portfolio solver exploiting a combination of possibly slower on-average different solvers. Despite the success of portfolio solvers within the context of solving competitions, they are rarely used in practice. In this paper we give an overview of the main limitations that hinder the practical adoption and development of portfolio solvers within the Constraint Programming (CP) paradigm, discussing also possible ways to overcome them and potential extensions outside the CP field.
For the entire collection see [Zbl 1326.68017].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDF BibTeX XML Cite
Full Text: DOI Link

References:

[1] Abío, I., Stuckey, P.J.: Encoding linear constraints into SAT. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 75–91. Springer, Heidelberg (2014) · Zbl 06461405
[2] Amadini, R., Gabbrielli, M., Mauro J.: An enhanced features extractor for a portfolio of constraint solvers. In: SAC, pp. 1357–1359. ACM (2014)
[3] Amadini, R., Gabbrielli, M., Mauro, J.: SUNNY: a lazy portfolio approach for constraint solving. TPLP 14(4–5), 509–524 (2014) · Zbl 1307.68077
[4] Amadini, R., Gabbrielli, M., Mauro J.: A multicore tool for constraint solving. In: IJCAI, pp. 232–238. AAAI Press (2015)
[5] Amadini, R., Gabbrielli, M., Mauro, J.: Portfolio approaches for constraint optimization problems. In: AMAI, pp. 1–18 (2015) · Zbl 1335.90077
[6] Amadini, R., Gabbrielli, M., Mauro, J.: SUNNY-CP: a sequential CP portfolio solver. In: SAC, pp. 1861–1867. ACM (2015)
[7] Amadini, R., Stuckey, P.J.: Sequential time splitting and bounds communication for a portfolio of optimization solvers. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 108–124. Springer, Heidelberg (2014) · Zbl 06461407
[8] Arbelaez, A., Hamadi, Y., Sebag, M.: Online heuristic selection in constraint programming. In: SoCS (2009)
[9] Arbelaez, A., Hamadi, Y., Sebag, M.: Continuous search in constraint programming. In: ICTAI, pp. 219–243. IEEE Computer Society (2010)
[10] Audemard, G., Hoessen, B., Jabbour, S., Lagniez, J-M., Piette, C.: PeneLoPe, a parallel clause-freezer solver. In: SAT Challenge, pp. 43–44 (2012)
[11] Barahona, P., Hölldobler, S., Nguyen, V.-H.: Representative encodings to translate finite CSPs into SAT. In: Simonis, H. (ed.) CPAIOR 2014. LNCS, vol. 8451, pp. 251–267. Springer, Heidelberg (2014) · Zbl 1407.68445
[12] Le Berre, D., Simon, L.: Preface to the special volume on the SAT 2005 competitions and evaluations. In: JSAT, 2(1–4), (2006)
[13] Bischl, B., Kerschke, P., Kotthoff, L., Lindauer, M.T., Malitsky, Y., Fréchette, A., Hoos, H.H., Hutter, F., Leyton-Brown, K., Tierney, K., Vanschoren, J.: Aslib: A benchmark library for algorithm selection. CoRR, abs/1506.02465
(2015) · Zbl 1357.68202
[14] Cenamor, I., de la Rosa, T., Fernández, F.: IBACOP and IBACOP2 Planner (2014). http://www.plg.inf.uc3m.es/ icenamor/files/IBaCoPPlanner.pdf
[15] Chu, G., de la Banda, M.G., Stuckey, P.J.: Automatically exploiting subproblem equivalence in constraint programming. In: Lodi, A., Milano, M., Toth, P. (eds.) CPAIOR 2010. LNCS, vol. 6140, pp. 71–86. Springer, Heidelberg (2010) · Zbl 1285.68153
[16] Cipriano, R., Dovier, A., Mauro, J.: Compiling and executing declarative modeling languages to gecode. In: Garcia de la Banda, M., Pontelli, E. (eds.) ICLP 2008. LNCS, vol. 5366, pp. 744–748. Springer, Heidelberg (2008) · Zbl 05496739
[17] claspfolio: http://www.cs.uni-potsdam.de/claspfolio/
[18] Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification, 2nd edn. Wiley-Interscience, New York (2000)
[19] Fawcett, C., Vallati, M., Hutter, F., Hoffmann, J., Hoos, H.H., Leyton-Brown, K.: Improved features for runtime prediction of domain-independent planners. In: ICAPS. AAAI (2014)
[20] Frisch, A.M., Harvey, W., Jefferson, C., Martínez-Hernández, B., Miguel, I.: Essence: a constraint language for specifying combinatorial problems. Constraints 13(3), 268–306 (2008) · Zbl 1147.68424
[21] FullContact. How We Used Immutable Servers to Simplify Our Cloud Infrastructure. (2014) http://www.fullcontact.com/blog/immutable-servers-benefits/
[22] Van Gelder, A.: Careful ranking of multiple solvers with timeouts and ties. In: Sakallah, K.A., Simon, L. (eds.) SAT 2011. LNCS, vol. 6695, pp. 317–328. Springer, Heidelberg (2011) · Zbl 1331.68213
[23] Gent, I.P., Walsh, T.: CSPlib: a benchmark library for constraints. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 480–481. Springer, Heidelberg (1999)
[24] Geschwender, D., Hutter, F., Kotthoff, L., Malitsky, Y., Hoos, H.H., Leyton-Brown, K.: Algorithm configuration in the cloud: a feasibility study. In: Pardalos, P.M., Resende, M.G.C., Vogiatzis, C., Walteros, J.L. (eds.) Learning and Intelligent Optimization. Lecture Notes in Computer Science, pp. 41–46. Springer, Heidelberg (2014)
[25] Gomes, C.P., Selman, B.: Algorithm portfolios. Artif. Intell. 126(1–2), 43–62 (2001) · Zbl 0969.68047
[26] Guo, H., Hsu, W.H.: A machine learning approach to algorithm selection for NP-hard optimization problems: a case study on the MPE problem. Ann. OR 156(1), 61–82 (2007) · Zbl 1145.68043
[27] Guyon, I., Elisseeff, A.: An introduction to variable and feature selection. J. Mach Learn. Res. 3, 1157–1182 (2003) · Zbl 1102.68556
[28] Hamadi, Y., Jabbour, S., Sais, L.: ManySAT: a parallel SAT solver. JSAT 6(4), 245–262 (2009) · Zbl 1193.68227
[29] Hebrard, E., O’Mahony, E., O’Sullivan, B.: Constraint programming and combinatorial optimisation in numberjack. In: Lodi, A., Milano, M., Toth, P. (eds.) CPAIOR 2010. LNCS, vol. 6140, pp. 181–185. Springer, Heidelberg (2010) · Zbl 05724364
[30] Hoos, H.H., Kaminski, R., Lindauer, M.T., Schaub, T.: aspeed: solver scheduling via answer set programming. In: TPLP (2015) · Zbl 1379.68283
[31] Hoos, H.H., Kaufmann, B., Schaub, T., Schneider, M.: Robust benchmark set selection for boolean constraint solvers. In: Nicosia, G., Pardalos, P. (eds.) LION 7. LNCS, vol. 7997, pp. 138–152. Springer, Heidelberg (2013)
[32] Lindauer, M., Hoos, H., Hutter, F.: From sequential algorithm selection to parallel portfolio selection. In: Jourdan, L., Dhaenens, C., Marmion, M.-E. (eds.) LION 9 2015. LNCS, vol. 8994, pp. 1–16. Springer, Heidelberg (2015)
[33] Hurley, B., Kotthoff, L., Malitsky, Y., O’Sullivan, B.: Proteus: a hierarchical portfolio of solvers and transformations. In: Simonis, H. (ed.) CPAIOR 2014. LNCS, vol. 8451, pp. 301–317. Springer, Heidelberg (2014) · Zbl 06298800
[34] Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configuration. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 507–523. Springer, Heidelberg (2011) · Zbl 06058615
[35] Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Intell. Res. (JAIR) 36, 267–306 (2009) · Zbl 1192.68831
[36] Hutter, F., Xu, L., Hoos, H.H., Leyton-Brown, K.: Algorithm runtime prediction: the state of the art. CoRR, abs/1211.0906
(2012)
[37] International planning competition: http://ipc.icaps-conference.org/
[38] Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm selection and scheduling. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 454–469. Springer, Heidelberg (2011) · Zbl 05949385
[39] Kadioglu, S., Malitsky, Y., Sellmann, M., Tierney, K.: ISAC - instance-specific algorithm configuration. In: Coelho, H., Studer, R., Wooldridge, M. (eds.) ECAI, Frontiers in Artificial Intelligence and Applications, vol. 215 pp. 751–756. IOS Press (2010)
[40] Kiziltan, Z., Mauro, J.: Service-oriented volunteer computing for massively parallel constraint solving using portfolios. In: Lodi, A., Milano, M., Toth, P. (eds.) CPAIOR 2010. LNCS, vol. 6140, pp. 246–251. Springer, Heidelberg (2010) · Zbl 05724369
[41] Kotthoff, L.: LLAMA: leveraging learning to automatically manage algorithms. CoRR, abs/1306.1031
(2013)
[42] Kotthoff, L.: Algorithm selection for combinatorial search problems: a survey. AI Mag. 35(3), 48–60 (2014)
[43] Kotthoff, L.: Reliability of computational experiments on virtualised hardware. J. Exp. Theor. Artif. Intell. 26(1), 33–49 (2014)
[44] Kroer, C., Malitsky, Y.: Feature filtering for instance-specific algorithm configuration. In: ICTAI, pp. 849–855. IEEE (2011)
[45] Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Parallel SAT solver selection and scheduling. In: Milano, M. (ed.) CP 2012. LNCS, vol. 7514, pp. 512–526. Springer, Heidelberg (2012) · Zbl 06122861
[46] Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm portfolios based on cost-sensitive hierarchical clustering. In: IJCAI. AAAI (2013)
[47] Maratea, M., Pulina, L., Ricca, F.: Multi-engine ASP solving with policy adaptation. J. Logic Comput. 1–22 (2013) · Zbl 1328.68042
[48] Maratea, M., Pulina, L., Ricca, F.: A multi-engine approach to answer-set programming. TPLP 14(6), 841–868 (2014)
[49] Max-SAT 2013: http://maxsat.ia.udl.cat/introduction/
[50] Morris, K.: Immutable server web page (2013). http://martinfowler.com/bliki/ImmutableServer.html
[51] mzn2feat-1.0 web page: http://www.cs.unibo.it/ amadini/mzn2feat-1.0.tar.bz2
[52] Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007) · Zbl 05318838
[53] Ohrimenko, O., Stuckey, P.J., Codish, M.: Propagation via lazy clause gener. Constraints 14(3), 357–391 (2009) · Zbl 1192.68654
[54] O’Mahony, E., Hebrard, E., Holland, A., Nugent C., O’Sullivan, B.: Using case-based reasoning in an algorithm portfolio for constraint solving. In: AICS 2008 (2009)
[55] Pulina, L., Tacchella, A.: A multi-engine solver for quantified boolean formulas. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 574–589. Springer, Heidelberg (2007) · Zbl 05318841
[56] Pulina, L., Tacchella, A.: A self-adaptive multi-engine solver for quantified boolean formulas. Constraints 14(1), 80–116 (2009) · Zbl 1183.68589
[57] Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)
[58] Roussel, O.: ppfolio. http://www.cril.univ-artois.fr/ roussel/ppfolio/
[59] Roussel O., Lecoutre, C.: XML representation of constraint networks: format XCSP 2.1. CoRR, abs/0902.2362
(2009)
[60] Sabharwal, A., Samulowitz, H.: Insights into parallelism with intensive knowledge sharing. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 655–671. Springer, Heidelberg (2014) · Zbl 06461444
[61] Samulowitz, H., Reddy, C., Sabharwal, A., Sellmann, M.: Snappy: a simple algorithm portfolio. In: Järvisalo, M., Van Gelder, A. (eds.) SAT 2013. LNCS, vol. 7962, pp. 422–428. Springer, Heidelberg (2013) · Zbl 06195214
[62] SAT Challenge 2012: http://baldur.iti.kit.edu/SAT-Challenge-2012/
[63] Zinc Interface library(zinc). https://sicstus.sics.se/sicstus/docs/4.1.0/html/sicstus/lib_002dzinc.html#lib_002dzinc
[64] Smith-Miles, K.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. 41(1) (2009)
[65] Stojadinovic M., Maric, F.: Instance-based selection of CSP solvers using short training. In: Pragmatics of SAT (2014)
[66] Stojadinovic, M., Maric, F.: meSAT: multiple encodings of CSP to SAT. Constraints 19(4), 380–403 (2014) · Zbl 1316.90049
[67] Stuckey, P.J., Becket, R., Fischer, J.: Philosophy of the miniZinc challenge. Constraints 15(3), 307–316 (2010) · Zbl 1208.68207
[68] Tamura, N., Taga, A., Kitagawa, S., Banbara, M.: Compiling finite linear CSP into SAT. Constraints 14(2), 254–272 (2009) · Zbl 1186.68076
[69] Telelis, O., Stamatopoulos, P.: Combinatorial optimization through statistical instance-based learning. In: ICTAI, pp. 203–209 (2001)
[70] Valenzano, R.A., Nakhost, H., Müller, M., Schaeffer, J., Sturtevant, N.R.: ArvandHerd: parallel planning with a portfolio. In: ECAI, pp. 786–791 (2012)
[71] Xu, L., Hutter, F., Shen, J., Hoos, H., Leyton-Brown, K.: SATzilla2012: improved algorithm selection based on cost-sensitive classification models. In: SAT Challenge (2012)
[72] Lin, X., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for SAT. JAIR 32, 565–606 (2008) · Zbl 1182.68272
[73] Yun, X., Epstein, S.L.: Learning algorithm portfolios for parallel execution. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, vol. 7219, pp. 323–338. Springer, Heidelberg (2012) · Zbl 06105746
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.