Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2015 | OriginalPaper | Buchkapitel

From Sequential Algorithm Selection to Parallel Portfolio Selection

verfasst von : M. Lindauer, H. Hoos, F. Hutter

Erschienen in: Learning and Intelligent Optimization

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In view of the increasing importance of hardware parallelism, a natural extension of per-instance algorithm selection is to select a set of algorithms to be run in parallel on a given problem instance, based on features of that instance. Here, we explore how existing algorithm selection techniques can be effectively parallelized. To this end, we leverage the machine learning models used by existing sequential algorithm selectors, such as 3S, ISAC, SATzilla and ME-ASP, and modify their selection procedures to produce a ranking of the given candidate algorithms; we then select the top n algorithms under this ranking to be run in parallel on n processing units. Furthermore, we adapt the pre-solving schedules obtained by aspeed to be effective in a parallel setting with different time budgets for each processing unit. Our empirical results demonstrate that, using 4 processing units, the best of our methods achieves a 12-fold average speedup over the best single solver on a broad set of challenging scenarios from the algorithm selection library.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Nächstes Kapitel An Algorithm Selection Benchmark of the Container Pre-marshalling Problem
Fußnoten
2
Unfortunately, no implementation of CSHCpar and 3Spar is publicly available.
 
4
In its original version, ISAC is a combination of algorithm configuration and selection, but only the selection approach was used in later publications.
 
5
Since 3S [21] is not publicly available, using it was not an option.
 
6
Since the CSP-2010 scenario consists of only 2 algorithms, it already admits a perfect portfolio using two processing units. Therefore, we excluded it from our experiments.
 
7
Instance features typically consist of cheap syntactic features, such as number of variables and number of clauses, and probing features, i.e., extracting runtime statistics by running an algorithm for a short time on a given instance.
 
9
The original ISAC [15] uses g-means, which automatically determines the number of clusters. In preliminary experiments, we observed that the square root of the number of instances gives a good upper bound for the number of clusters; therefore, we did not used g-means but k-means with this cluster bound.
 
10
We note that we have to use a geometric average instead of an arithmetic average, because we aggregate over speedup factors. This can be seen when considering a case with speedups of 2 and 0.5, where the arithmetic average gives a misleading 1.25.
 
Literatur
1.
Ansótegui, C., Malitsky, Y., Sellmann, M.: Maxsat by improved instance-specific algorithm configuration. In: Proceedings of AAAI 2014, pp. 2594–2600 (2014)
2.
Ansótegui, C., Sellmann, M., Tierney, K.: A gender-based genetic algorithm for the automatic configuration of algorithms. In: Gent, I.P. (ed.) CP 2009. LNCS, vol. 5732, pp. 142–157. Springer, Heidelberg (2009) CrossRef
3.
Arbelaez, A., Codognet, P.: From sequential to parallel local search for SAT. In: Middendorf, M., Blum, C. (eds.) EvoCOP 2013. LNCS, vol. 7832, pp. 157–168. Springer, Heidelberg (2013) CrossRef
4.
Baral, C.: Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, New York (2003) CrossRefMATH
5.
Gagliolo, M., Schmidhuber, J.: Towards distributed algorithm portfolios. In: Corchado, J.M., Rodríguez, S., Llinas, J., Molina, J.M. (eds.) DCAI 2008. Advances in Soft Computing, vol. 50, pp. 634–643. Springer, Heidelberg (2008)
6.
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., Schneider, M.: Potassco: the Potsdam answer set solving collection. AI Commun. 24(2), 107–124 (2011)MATHMathSciNet
7.
Hamadi, Y., Wintersteiger, C.: Seven challenges in parallel SAT solving. AI Mag. 34(2), 99–106 (2013)
8.
Hoos, H., Kaminski, R., Lindauer, M., Schaub, T.: aspeed: solver scheduling via answer set programming. TPLP 15, 117–142 (2015)
9.
Hoos, H., Lindauer, M., Schaub, T.: claspfolio 2: advances in algorithm selection for answer set programming. TPLP 14, 569–585 (2014)MATH
10.
Huberman, B., Lukose, R., Hogg, T.: An economic approach to hard computational problems. Science 275, 51–54 (1997)CrossRef
11.
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) CrossRef
12.
Hutter, F., Hoos, H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. JAIR 36, 267–306 (2009)MATH
13.
Hutter, F., Xu, L., Hoos, H., Leyton-Brown, K.: Algorithm runtime prediction: methods and evaluation. J. Artif. Intell. 206, 79–111 (2014)CrossRefMathSciNet
14.
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) CrossRef
15.
Kadioglu, S., Malitsky, Y., Sellmann, M., Tierney, K.: ISAC - instance-specific algorithm configuration. In: Proceedings of ECAI 2010, pp. 751–756 (2010)
16.
Kotthoff, L.: Algorithm selection for combinatorial search problems: a survey. AI Mag. 35(3), 48–60 (2014)
17.
Kotthoff, L.: Ranking algorithms by performance. In: Pardalos, P.M., Resende, M.G.C., Vogiatzis, C., Walteros, J.L. (eds.) LION 2014. LNCS, vol. 8426, pp. 16–20. Springer, Switzerland (2014)CrossRef
18.
Kotthoff, L., Gent, I., Miguel, I.: An evaluation of machine learning in algorithm selection for search problems. AI Commun. 25(3), 257–270 (2012)MathSciNet
19.
Lindauer, M., Hoos, H., Hutter, F., Schaub, T.: Autofolio: algorithm configuration for algorithm selection. In: Proceedings of Workshops at AAAI 2015 (2015)
20.
Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Parallel SAT solver selection and scheduling. In: Milano, M. (ed.) Principles and Practice of Constraint Programming. LNCS, pp. 512–526. Springer, Heidelberg (2012) CrossRef
21.
Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm portfolios based on cost-sensitive hierarchical clustering. In: Rossi, F. (ed.) Proceedings of IJCAI 2013, pp. 608–614 (2013)
22.
Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Parallel lingeling, ccasat, and csch-based portfolio. In: Proceedings of SAT Competition 2013, pp. 26–27 (2013)
23.
Maratea, M., Pulina, L., Ricca, F.: A multi-engine approach to answer-set programming. TPLP 14, 841–868 (2014)MathSciNet
24.
O’Mahony, E., Hebrard, E., Holland, A., Nugent, C., O’Sullivan, B.: Using case-based reasoning in an algorithm portfolio for constraint solving. In: Proceedings of AICS 2008 (2008)
25.
Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: machine learning in Python. JMLR 12, 2825–2830 (2011)MATH
26.
Pulina, L., Tacchella, A.: A self-adaptive multi-engine solver for quantified boolean formulas. Constraints 14(1), 80–116 (2009)CrossRefMATHMathSciNet
27.
Rice, J.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)
28.
Streeter, M., Golovin, D., Smith, S.: Combining multiple heuristics online. In: Proceedings of AAAI 2007, pp. 1197–1203 (2007)
29.
Tierney, K.: An algorithm selection benchmark of the container pre-marshalling problem. Tech. Rep. DS&OR Working Paper 1402, DS&OR Lab, University of Paderborn (2014)
30.
Xu, L., Hoos, H., Leyton-Brown, K.: Hydra: automatically configuring algorithms for portfolio-based selection. In: Proceedings of AAAI 2010, pp. 210–216 (2010)
31.
Xu, L., Hutter, F., Hoos, H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for SAT. JAIR 32, 565–606 (2008)MATH
32.
Xu, L., Hutter, F., Hoos, H., Leyton-Brown, K.: Evaluating component solver contributions to portfolio-based algorithm selectors. In: Cimatti, A., Sebastiani, R. (eds.) SAT 2012. LNCS, vol. 7317, pp. 228–241. Springer, Heidelberg (2012) CrossRef
33.
Xu, L., Hutter, F., Shen, J., Hoos, H., Leyton-Brown, K.: SATzilla2012: improved algorithm selection based on cost-sensitive classification models. In: Proceedings of SAT Challenge 2012, pp. 57–58 (2012)
34.
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) CrossRef
Metadaten
Titel
From Sequential Algorithm Selection to Parallel Portfolio Selection
verfasst von
M. Lindauer
H. Hoos
F. Hutter
Copyright-Jahr
2015
Buch
Learning and Intelligent Optimization

Print ISBN: 978-3-319-19083-9

Electronic ISBN: 978-3-319-19084-6

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-19084-6_1