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:
Introduction to Combinatorial Optimisation in Numberjack Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Algorithm Selection for Combinatorial Search Problems: A Survey

verfasst von : Lars Kotthoff

Erschienen in: Data Mining and Constraint Programming

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The Algorithm Selection Problem is concerned with selecting the best algorithm to solve a given problem on a case-by-case basis. It has become especially relevant in the last decade, as researchers are increasingly investigating how to identify the most suitable existing algorithm for solving a problem instead of developing new algorithms. This survey presents an overview of this work focusing on the contributions made in the area of combinatorial search problems, where Algorithm Selection techniques have achieved significant performance improvements. We unify and organise the vast literature according to criteria that determine Algorithm Selection systems in practice. The comprehensive classification of approaches identifies and analyses the different directions from which Algorithm Selection has been approached. This chapter contrasts and compares different methods for solving the problem as well as ways of using these solutions.

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
Vorheriges Kapitel Learning Modulo Theories
Nächstes Kapitel Advanced Portfolio Techniques
Literatur
1.
Aha, D.W.: Generalizing from case studies: a case study. In: Proceedings of the 9th International Workshop on Machine Learning, pp. 1–10. Morgan Kaufmann Publishers Inc, San Francisco (1992)
2.
Allen, J.A., Minton, S.: Selecting the right heuristic algorithm: runtime performance predictors. In: McCalla, G. (ed.) AI 1996. LNCS, vol. 1081, pp. 41–53. Springer, Heidelberg (1996). doi:10.​1007/​3-540-61291-2_​40 CrossRef
3.
Amadini, R., Gabbrielli, M., Mauro, J.: SUNNY: a lazy portfolio approach for constraint solving. TPLP 14(4–5), 509–524 (2014)MATH
4.
Ansel, J., Chan, C., Wong, Y.L., Olszewski, M., Zhao, Q., Edelman, A., Amarasinghe, S.: PetaBricks: a language and compiler for algorithmic choice. SIGPLAN Not. 44(6), 38–49 (2009)CrossRef
5.
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). doi:10.​1007/​978-3-642-04244-7_​14 CrossRef
6.
Arbelaez, A., Hamadi, Y., Sebag, M.: Online heuristic selection in constraint programming. In: Symposium on Combinatorial Search (2009)
7.
Armstrong, W., Christen, P., McCreath, E., Rendell, A.P.: Dynamic algorithm selection using reinforcement learning. In: International Workshop on Integrating AI and Data Mining, pp. 18–25, December 2006
8.
Balasubramaniam, D., Gent, I.P., Jefferson, C., Kotthoff, L., Miguel, I., Nightingale, P.: An automated approach to generating efficient constraint solvers. In: 34th International Conference on Software Engineering, pp. 661–671, June 2012
9.
Bauer, E., Kohavi, R.: An empirical comparison of voting classification algorithms: bagging, boosting, and variants. Mach. Learn. 36(1–2), 105–139 (1999)CrossRef
10.
Beck, J.C., Fox, M.S.: Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics. Artif. Intell. 117(1), 31–81 (2000)MathSciNetCrossRefMATH
11.
12.
Bhowmick, S., Eijkhout, V., Freund, Y., Fuentes, E., Keyes, D.: Application of machine learning in selecting sparse linear solvers. Technical report, Columbia University (2006)
13.
Bhowmick, S., Toth, B., Raghavan, P.: Towards low-cost, high-accuracy classifiers for linear solver selection. In: Allen, G., Nabrzyski, J., Seidel, E., Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds.) ICCS 2009. LNCS, vol. 5544, pp. 463–472. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-01970-8_​45 CrossRef
14.
Borrett, J.E., Tsang, E.P.K.: A context for constraint satisfaction problem formulation selection. Constraints 6(4), 299–327 (2001)MathSciNetCrossRefMATH
15.
Borrett, J.E., Tsang, E.P.K., Walsh, N.R.: Adaptive constraint satisfaction: The quickest first principle. In: ECAI, pp. 160–164 (1996)
16.
Bougeret, M., Dutot, P., Goldman, A., Ngoko, Y., Trystram, D.: Combining multiple heuristics on discrete resources. In: IEEE International Symposium on Parallel and Distributed Processing, pp. 1–8. IEEE Computer Society, Washington, DC (2009)
17.
Brazdil, P.B., Soares, C.: A comparison of ranking methods for classification algorithm selection. In: López de Mántaras, R., Plaza, E. (eds.) ECML 2000. LNCS (LNAI), vol. 1810, pp. 63–75. Springer, Heidelberg (2000). doi:10.​1007/​3-540-45164-1_​8 CrossRef
18.
19.
Brewer, E.A.: High-level optimization via automated statistical modeling. In: Proceedings of the 5th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming PPOPP 1995, pp. 80–91. ACM, New York (1995)
20.
Brodley, C.E.: Addressing the selective superiority problem: automatic algorithm/model class selection. In: ICML, pp. 17–24 (1993)
21.
Cahill, E.: Knowledge-based algorithm construction for real-world engineering PDEs. Math. Comput. Simul. 36(4–6), 389–400 (1994)MathSciNetCrossRef
22.
Carbonell, J., Etzioni, O., Gil, Y., Joseph, R., Knoblock, C., Minton, S., Veloso, M.: PRODIGY: an integrated architecture for planning and learning. SIGART Bull. 2, 51–55 (1991)CrossRef
23.
Carchrae, T., Beck, J.C.: Low-knowledge algorithm control. In: AAAI, pp. 49–54 (2004)
24.
Carchrae, T., Beck, J.C.: Applying machine learning to Low-knowledge control of optimization algorithms. Comput. Intell. 21(4), 372–387 (2005)MathSciNetCrossRef
25.
Caseau, Y., Laburthe, F., Silverstein, G.: A meta-heuristic factory for vehicle routing problems. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 144–158. Springer, Heidelberg (1999). doi:10.​1007/​978-3-540-48085-3_​11
26.
Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: 12th International Joint Conference on Artificial Intelligence, pp. 331–337. Morgan Kaufmann Publishers Inc, San Francisco, CA, USA (1991)
27.
Cicirello, V.A., Smith, S.F.: The max k-armed bandit: a new model of exploration applied to search heuristic selection. In: Proceedings of the 20th National Conference on Artificial Intelligence, pp. 1355–1361. AAAI Press (2005)
28.
Cook, D.J., Varnell, R.C.: Maximizing the benefits of parallel search using machine learning. In: Proceedings of the 14th National Conference on Artificial Intelligence, pp. 559–564. AAAI Press (1997)
29.
Demmel, J., Dongarra, J., Eijkhout, V., Fuentes, E., Petitet, A., Vuduc, R., Whaley, R.C., Yelick, K.: Self-adapting linear algebra algorithms and software. Proc. IEEE 93(2), 293–312 (2005)CrossRef
30.
31.
Domingos, P.: How to get a free lunch: a simple cost model for machine learning applications. In: AAAI98/ICML98 Workshop on the Methodology of Applying Machine Learning, pp. 1–7. AAAI Press (1998)
32.
Domshlak, C., Karpas, E., Markovitch, S.: To max or not to max: online learning for speeding up optimal planning. In: AAAI (2010)
33.
Elsayed, S.A.M., Michel, L.: Synthesis of search algorithms from high-level CP models. In: Proceedings of the 9th International Workshop on Constraint Modelling and Reformulation, September 2010
34.
35.
36.
Epstein, S.L., Freuder, E.C., Wallace, R., Morozov, A., Samuels, B.: The adaptive constraint engine. In: Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 525–540. Springer, Heidelberg (2002). doi:10.​1007/​3-540-46135-3_​35 CrossRef
37.
Ewald, R., Schulz, R., Uhrmacher, A.M.: Selecting simulation algorithm portfolios by genetic algorithms. In: IEEE Workshop on Principles of Advanced and Distributed Simulation PADS 2010, IEEE Computer Society, Washington, DC (2010)
38.
Fawcett, C., Vallati, M., Hutter, F., Hoffmann, J., Hoos, H., Leyton-Brown, K.: Improved features for runtime prediction of domain-independent planners. In: ICAPS (2014)
39.
Fink, E.: Statistical selection among problem-solving methods. Technical report CMU-CS-97-101. Carnegie Mellon University (1997)
40.
Fink, E.: How to solve it automatically: selection among problem-solving methods. In: Proceedings of the 4th International Conference on Artificial Intelligence Planning Systems, pp. 128–136. AAAI Press (1998)
41.
Fukunaga, A.S.: Genetic algorithm portfolios. IEEE Congr. Evol. Comput. 2, 1304–1311 (2000)
42.
Fukunaga, A.S.: Automated discovery of composite SAT variable-selection heuristics. In: 18th National Conference on Artificial Intelligence, pp. 641–648. American Association for Artificial Intelligence, Menlo Park (2002)
43.
Fukunaga, A.S.: Automated discovery of local search heuristics for satisfiability testing. Evol. Comput. 16, 31–61 (2008)CrossRef
44.
Gagliolo, M., Schmidhuber, J.: A neural network model for inter-problem adaptive online time allocation. In: Duch, W., Kacprzyk, J., Oja, E., Zadrożny, S. (eds.) ICANN 2005. LNCS, vol. 3697, pp. 7–12. Springer, Heidelberg (2005). doi:10.​1007/​11550907_​2
45.
Gagliolo, M., Schmidhuber, J.: Impact of censored sampling on the performance of restart strategies. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 167–181. Springer, Heidelberg (2006). doi:10.​1007/​11889205_​14 CrossRef
46.
Gagliolo, M., Schmidhuber, J.: Learning dynamic algorithm portfolios. Ann. Math. Artif. Intell. 47(3–4), 295–328 (2006)MathSciNetMATH
47.
Gagliolo, M., Schmidhuber, J.: Towards distributed algorithm portfolios. In: Corchado, J.M., Rodríguez, S., Llinas, J., Molina, J.M. (eds.) Advances in Soft Computing. AINSC, vol. 50, pp. 634–643. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-85863-8_​75
48.
Gagliolo, M., Schmidhuber, J.: Algorithm portfolio selection as a bandit problem with unbounded losses. Ann. Math. Artif. Intell. 61(2), 49–86 (2011)MathSciNetCrossRefMATH
49.
Gagliolo, M., Zhumatiy, V., Schmidhuber, J.: Adaptive online time allocation to search algorithms. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) ECML 2004. LNCS (LNAI), vol. 3201, pp. 134–143. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-30115-8_​15 CrossRef
50.
Garrido, P., Riff, M.: DVRP: a hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic. J. Heuristics 16, 795–834 (2010)CrossRefMATH
51.
Gebruers, C., Guerri, A., Hnich, B., Milano, M.: Making choices using structure at the instance level within a case based reasoning framework. In: CPAIOR, pp. 380–386 (2004)
52.
Gebruers, C., Hnich, B., Bridge, D., Freuder, E.: Using CBR to select solution strategies in constraint programming. In: Proceedings of ICCBR 2005, pp. 222–236 (2005)
53.
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T., Schneider, M.T., Ziller, S.: A portfolio solver for answer set programming: preliminary report. In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS (LNAI), vol. 6645, pp. 352–357. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-20895-9_​40 CrossRef
54.
Gent, I., Jefferson, C., Kotthoff, L., Miguel, I., Moore, N., Nightingale, P., Petrie, K.: Learning when to use lazy learning in constraint solving. In: 19th European Conference on Artificial Intelligence, pp. 873–878, August 2010
55.
Gent, I., Kotthoff, L., Miguel, I., Nightingale, P.: Machine learning for constraint solver design - a case study for the alldifferent constraint. In: 3rd Workshop on Techniques for implementing Constraint Programming Systems (TRICS), pp. 13–25 (2010)
56.
Gerevini, A.E., Saetti, A., Vallati, M.: An automatically configurable portfolio-based planner with macro-actions: PbP. In: Proceedings of the 19th International Conference on Automated Planning and Scheduling, pp. 350–353 (2009)
57.
Gomes, C.P., Selman, B.: Algorithm portfolio design: theory vs. practice. In: UAI, pp. 190–197 (1997)
58.
Gomes, C.P., Selman, B.: Practical aspects of algorithm portfolio design. In: Proceedings of 3rd ILOG International Users Meeting (1997)
59.
60.
Gratch, J., DeJong, G.: COMPOSER: a probabilistic solution to the utility problem in speed-up learning. In: AAAI, pp. 235–240 (1992)
61.
Guerri, A., Milano, M.: Learning techniques for automatic algorithm portfolio selection. In: ECAI, pp. 475–479 (2004)
62.
Guo, H.: Algorithm selection for sorting and probabilistic inference: a machine learning-based approach. Ph.D. thesis, Kansas State University (2003)
63.
Guo, H., Hsu, W.H.: A learning-based algorithm selection meta-reasoner for the real-time MPE problem. In: Webb, G.I., Yu, X. (eds.) AI 2004. LNCS (LNAI), vol. 3339, pp. 307–318. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-30549-1_​28 CrossRef
64.
65.
Hogg, T., Huberman, B.A., Williams, C.P.: Phase transitions and the search problem. Artif. Intell. 81(1–2), 1–15 (1996)MathSciNetCrossRef
66.
Hong, L., Page, S.E.: Groups of diverse problem solvers can outperform groups of high-ability problem solvers. Proc. Natl. Acad. Sci. U.S.A. 101(46), 16385–16389 (2004)CrossRef
67.
Hoos, H., Lindauer, M., Schaub, T.: claspfolio 2: Advances in algorithm selection for answer set programming. TPLP 14(4–5), 569–585 (2014)MATH
68.
Hoos, H.H.: Programming by optimization. Commun. ACM 55(2), 70–80 (2012)CrossRef
69.
Hoos, H.H., Kaminski, R., Lindauer, M., Schaub, T.: aspeed: Solver scheduling via answer set programming. Theory Pract. Logic Program. FirstView 15, 1–26 (2014)
70.
Horvitz, E., Ruan, Y., Gomes, C.P., Kautz, H.A., Selman, B., Chickering, D.M.: A Bayesian approach to tackling hard computational problems. In: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, pp. 235–244. Morgan Kaufmann Publishers Inc., San Francisco (2001)
71.
Hough, P.D., Williams, P.J.: Modern machine learning for automatic optimization algorithm selection. In: Proceedings of the INFORMS Artificial Intelligence and Data Mining Workshop, November 2006
72.
Howe, A.E., Dahlman, E., Hansen, C., Scheetz, M., Mayrhauser, A.: Exploiting competitive planner performance. In: Biundo, S., Fox, M. (eds.) ECP 1999. LNCS (LNAI), vol. 1809, pp. 62–72. Springer, Heidelberg (2000). doi:10.​1007/​10720246_​5 CrossRef
73.
Huberman, B.A., Lukose, R.M., Hogg, T.: An economics approach to hard computational problems. Science 275(5296), 51–54 (1997)CrossRef
74.
Hurley, B., Kotthoff, L., Malitsky, Y., O’Sullivan, B.: Proteus: a hierarchical portfolio of solvers and transformations. In: CPAIOR, May 2014
75.
Hutter, F., Hamadi, Y., Hoos, H.H., Leyton-Brown, K.: Performance prediction and automated tuning of randomized and parametric algorithms. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 213–228. Springer, Heidelberg (2006). doi:10.​1007/​11889205_​17 CrossRef
76.
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). doi:10.​1007/​978-3-642-25566-3_​40 CrossRef
77.
78.
Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Int. Res. 36(1), 267–306 (2009)MATH
79.
Hutter, F., Hoos, H.H., Stützle, T.: Automatic algorithm configuration based on local search. In: Proceedings of the 22nd National Conference on Artificial Intelligence, pp. 1152–1157. AAAI Press (2007)
80.
Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm selection and scheduling. In: 17th International Conference on Principles and Practice of Constraint Programming, pp. 454–469 (2011)
81.
Kadioglu, S., Malitsky, Y., Sellmann, M., Tierney, K.: ISAC instance-specific algorithm configuration. In: 19th European Conference on Artificial Intelligence, pp. 751–756. IOS Press (2010)
82.
Kamel, M.S., Enright, W.H., Ma, K.S.: ODEXPERT: an expert system to select numerical solvers for initial value ODE systems. ACM Trans. Math. Softw. 19(1), 44–62 (1993)CrossRefMATH
83.
Kotthoff, L.: Hybrid regression-classification models for algorithm selection. In: 20th European Conference on Artificial Intelligence, pp. 480–485, August 2012
84.
Kotthoff, L.: Algorithm selection for combinatorial search problems: a survey. AI Mag. 35(3), 48–60 (2014)
85.
Kotthoff, L., Gent, I.P., Miguel, I.: An evaluation of machine learning in algorithm selection for search problems. AI Commun. 25(3), 257–270 (2012)MathSciNet
86.
Kotthoff, L., Kerschke, P., Hoos, H., Trautmann, H.: Improving the state of the art in inexact TSP solving using per-instance algorithm selection. In: Dhaenens, C., Jourdan, L., Marmion, M.-E. (eds.) LION 2015. LNCS, vol. 8994, pp. 202–217. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-19084-6_​18 CrossRef
87.
Kotthoff, L., Miguel, I., Nightingale, P.: Ensemble classification for constraint solver configuration. In: 16th International Conference on Principles and Practices of Constraint Programming, pp. 321–329, September 2010
88.
Kroer, C., Malitsky, Y.: Feature filtering for Instance-Specific algorithm configuration. In: Proceedings of the 23rd International Conference on Tools with Artificial Intelligence (2011)
89.
Kuefler, E., Chen, T.-Y.: On using reinforcement learning to solve sparse linear systems. In: Bubak, M., Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds.) ICCS 2008. LNCS, vol. 5101, pp. 955–964. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-69384-0_​100 CrossRef
90.
Lagoudakis, M.G., Littman, M.L.: Algorithm selection using reinforcement learning. In: Proceedings of the 17th International Conference on Machine Learning, pp. 511–518. Morgan Kaufmann Publishers Inc., San Francisco (2000)
91.
Lagoudakis, M.G., Littman, M.L.: Learning to select branching rules in the DPLL procedure for satisfiability. In: LICS/SAT, pp. 344–359 (2001)
92.
Langley, P.: Learning effective search heuristics. In: IJCAI, pp. 419–421 (1983)
93.
Langley, P.: Learning search strategies through discrimination. Int. J. Man-Mach. Stud. 18, 513–541 (1983)CrossRef
94.
Leite, R., Brazdil, P., Vanschoren, J., Queiros, F.: Using active testing and meta-level information for selection of classification algorithms. In: 3rd PlanLearn Workshop, August 2010
95.
Leyton-Brown, K., Nudelman, E., Shoham, Y.: Learning the empirical hardness of optimization problems: the case of combinatorial auctions. In: Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 556–572. Springer, Heidelberg (2002). doi:10.​1007/​3-540-46135-3_​37 CrossRef
96.
Leyton-Brown, K., Nudelman, E., Shoham, Y.: Empirical hardness models: methodology and a case study on combinatorial auctions. J. ACM 56, 1–52 (2009)MathSciNetCrossRefMATH
97.
Lindauer, M., Hoos, H., Hutter, F.: From sequential algorithm selection to parallel portfolio selection. In: Dhaenens, C., Jourdan, L., Marmion, M.-E. (eds.) LION 2015. LNCS, vol. 8994, pp. 1–16. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-19084-6_​1 CrossRef
98.
Lindauer, M., Hoos, H.H., Hutter, F., Schaub, T.: AutoFolio: algorithm configuration for algorithm selection. In: Twenty-Ninth AAAI Workshops on Artificial Intelligence, January 2015
99.
Little, J., Gebruers, C., Bridge, D., Freuder, E.: Capturing constraint programming experience: a case-based approach. In: Modref (2002)
100.
Lobjois, L., Lemaître, M.: Branch and bound algorithm selection by performance prediction. In: Proceedings of the 15th National/10th Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence, pp. 353–358. American Association for Artificial Intelligence, Menlo Park (1998)
101.
Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Non-model-based algorithm portfolios for SAT. In: Sakallah, K.A., Simon, L. (eds.) SAT 2011. LNCS, vol. 6695, pp. 369–370. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-21581-0_​33 CrossRef
102.
Malitsky, Y., Sabharwal, A., Samulowitz, H., Sellmann, M.: Algorithm portfolios based on cost-sensitive hierarchical clustering. In: IJCAI, August 2013
103.
Minton, S.: An analytic learning system for specializing heuristics. In: Proceedings of the 13th International Joint Conference on Artifical Intelligence IJCAI 1993, pp. 922–928. Morgan Kaufmann Publishers Inc., San Francisco (1993)
104.
Minton, S.: Integrating heuristics for constraint satisfaction problems: a case study. In: Proceedings of the 11th National Conference on Artificial Intelligence, pp. 120–126. AAAI (1993)
105.
Minton, S.: Automatically configuring constraint satisfaction programs: a case study. Constraints 1, 7–43 (1996)MathSciNetCrossRef
106.
107.
Nareyek, A.: Choosing search heuristics by non-stationary reinforcement learning. In: Nareyek, A. (ed.) Metaheuristics: Computer Decision-Making. Applied Optimization, vol. 86, pp. 523–544. Kluwer Academic Publishers, New York (2001)CrossRef
108.
109.
Nudelman, E., Leyton-Brown, K., Hoos, H.H., Devkar, A., Shoham, Y.: Understanding random SAT: beyond the clauses-to-variables ratio. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 438–452. Springer, Heidelberg (2004). doi:10.​1007/​978-3-540-30201-8_​33 CrossRef
110.
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 the 19th Irish Conference on Artificial Intelligence and Cognitive Science (2008)
111.
Opitz, D., Maclin, R.: Popular ensemble methods: an empirical study. J. Artif. Intell. Res. 11, 169–198 (1999)MATH
112.
Paparrizou, A., Stergiou, K.: Evaluating simple fully automated heuristics for adaptive constraint propagation. In: ICTAI (2012)
113.
Petrik, M.: Statistically optimal combination of algorithms. In: Local Proceedings of SOFSEM 2005 (2005)
114.
Petrik, M., Zilberstein, S.: Learning parallel portfolios of algorithms. Ann. Math. Artif. Intell. 48(1–2), 85–106 (2006)MathSciNetMATH
115.
Petrovic, S., Qu, R.: Case-based reasoning as a heuristic selector in hyper-heuristic for course timetabling problems. In: KES, pp. 336–340 (2002)
116.
Pfahringer, B., Bensusan, H., Giraud-Carrier, C.G.: Meta-Learning by landmarking various learning algorithms. In: 17th International Conference on Machine Learning ICML 2000, pp. 743–750, Morgan Kaufmann Publishers Inc., San Francisco (2000)
117.
118.
Pulina, L., Tacchella, A.: A self-adaptive multi-engine solver for quantified boolean formulas. Constraints 14(1), 80–116 (2009)MathSciNetCrossRefMATH
119.
Rao, R.B., Gordon, D., Spears, W.: For every generalization action, is there really an equal and opposite reaction? Analysis of the conservation law for generalization performance. In: Proceedings of the 12th International Conference on Machine Learning, pp. 471–479. Morgan Kaufmann (1995)
120.
Rice, J.R.: The algorithm selection problem. Adv. Comput. 15, 65–118 (1976)CrossRef
121.
Rice, J.R., Ramakrishnan, N.: How to get a free lunch (at no cost). Techical report 99–014, Purdue University, April 1999
122.
Roberts, M., Howe, A.E.: Directing a portfolio with learning. In: AAAI 2006 Workshop on Learning for Search (2006)
123.
Roberts, M., Howe, A.E.: Learned models of performance for many planners. In: ICAPS 2007 Workshop AI Planning and Learning (2007)
124.
Roberts, M., Howe, A.E., Wilson, B., des Jardins, M.: What makes planners predictable? In: ICAPS, pp. 288–295 (2008)
125.
Sakkout, H., Wallace, M.G., Richards, E.B.: An instance of adaptive constraint propagation. In: Freuder, E.C. (ed.) CP 1996. LNCS, vol. 1118, pp. 164–178. Springer, Heidelberg (1996). doi:10.​1007/​3-540-61551-2_​73
126.
Samulowitz, H., Memisevic, R.: Learning to solve QBF. In: Proceedings of the 22nd National Conference on Artificial Intelligence, pp. 255–260. AAAI Press (2007)
127.
Sayag, T., Fine, S., Mansour, Y.: Combining multiple heuristics. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 242–253. Springer, Heidelberg (2006). doi:10.​1007/​11672142_​19 CrossRef
128.
Schapire, R.E.: The strength of weak learnability. Mach. Learn. 5(2), 197–227 (1990)
129.
Sillito, J.: Improvements to and estimating the cost of solving constraint satisfaction problems. Master’s thesis, University of Alberta (2000)
130.
Silverthorn, B., Miikkulainen, R.: Latent class models for algorithm portfolio methods. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence (2010)
131.
Smith, T.E., Setliff, D.E.: Knowledge-based constraint-driven software synthesis. In: Knowledge-Based Software Engineering Conference, pp. 18–27, September 1992
132.
Smith-Miles, K., Lopes, L.: Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res. 39(5), 875–889 (2012)MathSciNetCrossRefMATH
133.
Smith-Miles, K.A.: Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Comput. Surv. 41, 6: 1–6: 25 (2008)CrossRef
134.
Smith-Miles, K.A.: Towards insightful algorithm selection for optimisation using meta-learning concepts. In: IEEE International Joint Conference on Neural Networks, pp. 4118–4124, June 2008
135.
Soares, C., Brazdil, P.B., Kuba, P.: A meta-learning method to select the kernel width in support vector regression. Mach. Learn. 54(3), 195–209 (2004)CrossRefMATH
136.
Stergiou, K.: Heuristics for dynamically adapting propagation in constraint satisfaction problems. AI Commun. 22(3), 125–141 (2009)MathSciNetMATH
137.
Stern, D.H., Samulowitz, H., Herbrich, R., Graepel, T., Pulina, L., Tacchella, A.: Collaborative expert portfolio management. In: AAAI, pp. 179–184 (2010)
138.
Streeter, M.J., Golovin, D., Smith, S.F.: Combining multiple heuristics online. In: Proceedings of the 22nd National Conference on Artificial Intelligence, pp. 1197–1203. AAAI Press (2007)
139.
Streeter, M.J., Golovin, D., Smith, S.F.: Restart schedules for ensembles of problem instances. In: Proceedings of the 22nd National Conference on Artificial Intelligence, pp. 1204–1210. AAAI Press (2007)
140.
Streeter, M.J., Smith, S.F.: New techniques for algorithm portfolio design. In: UAI, pp. 519–527 (2008)
141.
Terashima-Marín, H., Ross, P., Valenzuela-Rendón, M.: Evolution of constraint satisfaction strategies in examination timetabling. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 635–642. Morgan Kaufmann (1999)
142.
Tolpin, D., Shimony, S.E.: Rational deployment of CSP heuristics. In: IJCAI, pp. 680–686 (2011)
143.
Tsang, E.P.K., Borrett, J.E., Kwan, A.C.M.: An attempt to map the performance of a range of algorithm and heuristic combinations. In: Proceedings of AISB 1995, pp. 203–216. IOS Press (1995)
144.
Utgoff, P.E.: Perceptron trees: a case study in hybrid concept representations. In: National Conference on Artificial Intelligence, pp. 601–606 (1988)
145.
Vassilevska, V., Williams, R., Woo, S.L.M.: Confronting hardness using a hybrid approach. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms SODA 2006, pp. 1–10. ACM, New York (2006)
146.
Vrakas, D., Tsoumakas, G., Bassiliades, N., Vlahavas, I.: Learning rules for adaptive planning. In: Proceedings of the 13th International Conference on Automated Planning and Scheduling, pp. 82–91 (2003)
147.
Wang, J., Tropper, C.: Optimizing time warp simulation with reinforcement learning techniques. In: Proceedings of the 39th Conference on Winter simulation WSC 2007, pp. 577–584. IEEE Press, Piscataway (2007)
148.
Watson, J.: Empirical modeling and analysis of local search algorithms for the job-shop scheduling problem. Ph.D. thesis, Colorado State University, Fort Collins, CO, USA (2003)
149.
Weerawarana, S., Houstis, E.N., Rice, J.R., Joshi, A., Houstis, C.E.: PYTHIA: a knowledge-based system to select scientific algorithms. ACM Trans. Math. Softw. 22(4), 447–468 (1996)CrossRefMATH
150.
Wei, W., Li, C.M., Zhang, H.: Switching among non-weighting, clause weighting, and variable weighting in local search for SAT. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 313–326. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-85958-1_​21 CrossRef
151.
Wilson, D., Leake, D., Bramley, R.: Case-based recommender components for scientific problem-solving environments. In: Proceedings of the 16th International Association for Mathematics and Computers in Simulation World Congress (2000)
152.
Wolpert, D.H.: Stacked generalization. Neural Netw. 5, 241–259 (1992)CrossRef
153.
Wolpert, D.H.: The supervised learning no-free-lunch theorems. In: Proceedings of the 6th Online World Conference on Soft Computing in Industrial Applications, pp. 25–42 (2001)
154.
Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1(1), 67–82 (1997)CrossRef
155.
Wu, H., van Beek, P.: On portfolios for backtracking search in the presence of deadlines. In: Proceedings of the 19th IEEE International Conference on Tools with Artificial Intelligence, pp. 231–238. IEEE Computer Society, Washington, DC (2007)
156.
Xu, L., Hoos, H.H., Leyton-Brown, K.: Hierarchical hardness models for SAT. In: CP, pp. 696–711 (2007)
157.
Xu, L., Hoos, H.H., Leyton-Brown, K.: Hydra: automatically configuring algorithms for portfolio-based selection. In: 24th Conference of the Association for the Advancement of Artificial Intelligence (AAAI 2010), pp. 210–216 (2010)
158.
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla-07: the design and analysis of an algorithm portfolio for SAT. In: CP, pp. 712–727 (2007)
159.
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla: portfolio-based algorithm selection for SAT. J. Artif. Intell. Res. (JAIR) 32, 565–606 (2008)MATH
160.
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: SATzilla2009: an automatic algorithm portfolio for SAT. In: 2009 SAT Competition (2009)
161.
Xu, L., Hutter, F., Hoos, H.H., Leyton-Brown, K.: 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) (2011)
162.
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). doi:10.​1007/​978-3-642-31612-8_​18 CrossRef
163.
Yu, H., Rauchwerger, L.: An adaptive algorithm selection framework for reduction parallelization. IEEE Trans. Parallel Distrib. Syst. 17(10), 1084–1096 (2006)CrossRef
164.
Yu, H., Zhang, D., Rauchwerger, L.: An adaptive algorithm selection framework. In: Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, pp. 278–289. IEEE Computer Society, Washington, DC (2004)
165.
Yun, X., Epstein, S.L.: Learning algorithm portfolios for parallel execution. In: Hamadi, Y., Schoenauer, M. (eds.) Proceedings of the 6th International Conference Learning and Intelligent Optimisation LION. LNCS, vol. 7219, pp. 323–338. Springer, Heidelberg (2012)CrossRef
Metadaten
Titel
Algorithm Selection for Combinatorial Search Problems: A Survey
verfasst von
Lars Kotthoff
Copyright-Jahr
2016
Buch
Data Mining and Constraint Programming

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

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

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-50137-6_7