research-article

Algorithm Selection for Combinatorial Search Problems: : A Survey

Author:

Lars KotthoffAuthors Info & Claims

AI Magazine, Volume 35, Issue 3

Pages 48 - 60

https://doi.org/10.1609/aimag.v35i3.2460

Published: 01 September 2014 Publication History

Abstract

The algorithm selection problem is concerned with selecting the best algorithm to solve a given problem instance on a case‐by‐case basis. It has become especially relevant in the last decade, with researchers increasingly investigating how to identify the most suitable existing algorithm for solving a problem instance 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 analyzes the different directions from which algorithm selection has been approached. This article contrasts and compares different methods for solving the problem as well as ways of using these solutions.

References

[1]

Aha, D. W. 1992. Generalizing from Case Studies: A Case Study. In Proceedings of the 9th International Workshop on Machine Learning, 1–10. San Francisco, CA: Morgan Kaufmann Publishers Inc.

Digital Library

[2]

Allen, J. A., and Minton, S. 1996. Selecting the Right Heuristic Algorithm: Runtime Performance Predictors. In Proceedings of the 11th Biennial Conference of the Canadian Society for Computational Studies of Intelligence, 41–53. Berlin: Springer‐Verlag.

[3]

Arbelaez, A., Hamadi, Y.; and Sebag, M. 2009. Online Heuristic Selection in Constraint Programming. Paper presented at the Symposium on Combinatorial Search, Lake Arrowhead, CA, July 8–10.

[4]

Beck, J. C., and Freuder, E. C. 2004. Simple Rules for Low‐Knowledge Algorithm Selection. In Proceedings of the First International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 50–64. Berlin: Springer. https://doi.org/10.1007/978-3-540-24664-0_4

[5]

Borrett, J. E., Tsang, E. P. K.; and Walsh, N. R. 1996. Adaptive Constraint Satisfaction: The Quickest First Principle. In Proceedings of the 12th European Conference on Artificial Intelligence (ECAI), 160–164. Chichester, UK: John Wiley and Sons.

[6]

Brodley, C. E. 1993. Addressing the Selective Superiority Problem: Automatic Algorithm/Model Class Selection. In Proceedings of the International Conference on Machine Learning, 17–24. San Francisco: Morgan Kaufmann Publishers, Inc.

[7]

Carbonell, J., Etzioni, O., Gil, Y., Joseph, R., Knoblock, C., Minton, S.; and Veloso, M. 1991. Prodigy: An Integrated Architecture for Planning and Learning. SIGART Bulletin 2(2): 51–55. https://doi.org/10.1145/122344.122353

Digital Library

[8]

Carchrae, T., and Beck, J. C. 2004. Low‐Knowledge Algorithm Control. In Proceedings of the 19th National Conference on Artificial Intelligence, 49–54. Palo Alto, CA: AAAI Press.

[9]

Caseau, Y., Laburthe, F.; and Silverstein, G. 1999. A Meta‐Heuristic Factory for Vehicle Routing Problems. In Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming, 144–158. Berlin: Springer‐Verlag.

Digital Library

[10]

Cook, D. J., and Varnell, R. C. 1997. Maximizing the Benefits of Parallel Search Using Machine Learning. In Proceedings of the 14th National Conference on Artificial Intelligence, 559–564. Palo Alto, CA: AAAI Press.

[11]

Demmel, J., Dongarra, J., Eijkhout, V., Fuentes, E., Petitet, A., Vuduc, R., Whaley, R. C.; and Yelick, K. 2005. Self‐Adapting Linear Algebra Algorithms and Software. In Proceedings of the IEEE 93(2): 293–312. https://doi.org/10.1109/JPROC.2004.84084

[12]

Epstein, S. L., and Freuder, E. C. 2001. Collaborative Learning for Constraint Solving. In Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, 46–60. Berlin: Springer‐Verlag.

Digital Library

[13]

Fink, E. 1997. Statistical Selection Among Problem‐Solving Methods. Technical Report CMU‐CS‐97‐101, Carnegie Mellon University, Pittsburgh, PA.

[14]

Fukunaga, A. S. 2008. Automated Discovery of Local Search Heuristics for Satisfiability Testing. Evolutionary Computation 16:31–61.

Digital Library

[15]

Fukunaga, A. S. 2002. Automated Discovery of Composite SAT Variable‐Selection Heuristics. In Proceedings of the 18th National Conference on Artificial Intelligence, 641–648. Menlo Park, CA: AAAI Press. https://doi.org/10.1162/evco.2008.16.1.31

[16]

Gagliolo, M., and Schmidhuber, J. 2008. Towards Distributed Algorithm Portfolios. In International Symposium on Distributed Computing and Artificial Intelligence, Advances In Soft Computing. Berlin: Springer.

[17]

Gagliolo, M., and Schmidhuber, J. 2006. Learning Dynamic Algorithm Portfolios. Annals of Mathematics and Artificial Intelligence 47(3‐4): 295–328. https://doi.org/10.1007/s10472-006-9036-z

Digital Library

[18]

Gent, I., Jefferson, C., Kotthoff, L., Miguel, I., Moore, N., Nightingale, P.; and Petrie, K. 2010. Learning When To Use Lazy Learning In Constraint Solving. In Proceedings of the 19th European Conference on Artificial Intelligence, 873–878. Amsterdam, The Netherlands: IOS Press.

[19]

Gomes, C. P., and Selman, B. 1997. Algorithm Portfolio Design: Theory Versus Practice. In Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, 190–197. San Francisco: Morgan Kaufmann Publishers.

[20]

Guerri, A., and Milano, M. 2004. Learning Techniques for Automatic Algorithm Portfolio Selection. In Proceedings of the 16th Eureopean Conference on Artificial Intelligence, 475–479. Amsterdam, The Netherlands: IOS Press.

Digital Library

[21]

Haim, S., and Walsh, T. 2009. Restart Strategy Selection Using Machine Learning Techniques. In Proceedings of the 12th International Conference on Theory and Applications of Satisfiability Testing, 312–325. Berlin: Springer‐Verlag.

Digital Library

[22]

Hong, L., and Page, S. E. 2004. Groups of Diverse Problem Solvers can Outperform Groups of High‐Ability Problem Solvers. In Proceedings of the National Academy of Sciences of the United States of America 101(46): 16385–16389. https://doi.org/10.1073/pnas.0403723101

[23]

Horvitz, E., Ruan, Y., Gomes, C. P., Kautz, H. A., Selman, B.; and Chickering, D. M. 2001. A Bayesian Approach To Tackling Hard Computational Problems. In Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, 235–244. San Francisco: Morgan Kaufmann Publishers Inc.

Digital Library

[24]

Huberman, B. A., Lukose, R. M.; and Hogg, T. 1997. An Economics Approach to Hard Computational Problems. Science 275(5296): 51–54. https://doi.org/10.1126/science.275.5296.51

[25]

Kadioglu, S., Malitsky, Y., Sabharwal, A., Samulowitz, H.; and Sellmann, M. 2011. Algorithm Selection and Scheduling. In Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Sciencem 454–469. Berlin: Springer.

Digital Library

[26]

Kadioglu, S., Malitsky, Y.; and Sellmann, M. 2012. Non‐Model‐Based Search Guidance for Set Partitioning Problems. In Proceedings of the Twenty‐Sixth AAAI Conference on Artificial Intelligence. Palo Alto, CA: AAAI Press.

[27]

Kadioglu, S., Malitsky, Y., Sellmann, M.; and Tierney, K. 2010. ISAC — Instance‐Specific Algorithm Configuration. In Proceedings of the 19th European Conference on Artificial Intelligence, 751–756. Amsterdam, The Netherlands: IOS Press.

[28]

Kotthoff, L. 2012. Hybrid Regression‐Classification Models for Algorithm Selection. In Proceedings of the 20th European Conference on Artificial Intelligence, 480–485. Amsterdam, The Netherlands: IOS Press.

[29]

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.

Digital Library

[30]

Lagoudakis, M. G., and Littman, M. L. 2000. Algorithm Selection Using Reinforcement Learning. In Proceedings of the 17th International Conference on Machine Learning, 511–518. San Francisco: Morgan Kaufmann Publishers Inc.

Digital Library

[31]

Langley, P. 1983. Learning Search Strategies Through Discrimination. International Journal of Man‐Machine Studies 18(6): 513–541. https://doi.org/10.1016/S0020-7373(83)80030-

[32]

Leyton‐Brown, K., Nudelman, E.; and Shoham, Y. 2002. Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, 556–572. Berlin: Springer‐Verlag.

[33]

Lobjois, L., and Lemaître, M. 1998. Branch and Bound Algorithm Selection by Performance Prediction. In Proceedings of the 15th National Conference on Artificial Intelligence, 353–358. Menlo Park, CA: AAAI Press.

[34]

Malitsky, Y., Sabharwal, A., Samulowitz, H.; and Sellmann, M. 2013. Algorithm Portfolios Based on Cost‐Sensitive Hierarchical Clustering. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Palo Alto, CA: AAAI Press.

[35]

Minton, S. 1996. Automatically Configuring Constraint Satisfaction Programs: A Case Study. Constraints 1(1–2): 7–43. https://doi.org/10.1007/BF00143877

[36]

Nikolic, M., Maric, F.; and Janicic, P. 2009. Instance‐Based Selection of Policies for SAT Solvers. In Proceedings of the 12th International Conference on Theory and Applications of Satisfiability Testing, SAT '09, 326–340. Berlin: Springer‐Verlag.

Digital Library

[37]

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 19th Irish Conference on Artificial Intelligence and Cognitive Science. Lecture Notes in Computer Science. Berlin: Springer.

[38]

Petrik, M. 2005. Statistically Optimal Combination of Algorithms. Paper presented at the 31st Conference on Current Trends in Theory and Practice of Computer Science. Liptovsky Jan, Slovakia, January 22–28.

[39]

Pulina, L., and Tacchella, A. 2009. A Self‐Adaptive Multi‐Engine Solver for Quantified Boolean Formulas. Constraints 14(1): 80–116.

Digital Library

[40]

Pulina, L., and Tacchella, A. 2007. A Multi‐Engine Solver for Quantified Boolean Formulas. In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 574–589. Berlin: Springer. https://doi.org/10.1007/s10601-008-9051-2

Digital Library

[41]

Rice, J. R. 1976. The Algorithm Selection Problem. Advances in Computers 15:65–118. https://doi.org/10.1016/S0065-2458(08)60520-3

[42]

Roberts, M., and Howe, A. E. 2006. Directing A Portfolio With Learning. Paper presented at the AAAI 2006 Workshop on Learning for Search, Boston, MA, July 16.

[43]

Sakkout, H. E., Wallace, M. G.; and Richards, E. B. 1996. An Instance of Adaptive Constraint Propagation. In Proceedings of the Second International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 164–178. Berlin: Springer Verlag.

[44]

Samulowitz, H., and Memisevic, R. 2007. Learning to Solve QBF. In Proceedings of the 22nd National Conference on Artificial Intelligence, 255–260. Palo Alto, CA: AAAI Press.

Digital Library

[45]

Silverthorn, B., and Miikkulainen, R. 2010. Latent Class Models for Algorithm Portfolio Methods. In Proceedings of the 24th AAAI Conference on Artificial Intelligence. Palo Alto, CA: AAAI Press.

Digital Library

[46]

Smith‐Miles, K. A. 2008. Cross‐Disciplinary Perspectives on Meta‐Learning for Algorithm Selection. ACM Computing Surveys 41(1), Article 6. https://doi.org/10.1145/1456650.1456656

[47]

Stergiou, K. 2009. Heuristics for Dynamically Adapting Propagation In Constraint Satisfaction Problems. AI Communications 22(3): 125–141.

Digital Library

[48]

Streeter, M. J., Golovin, D.; and Smith, S. F. 2007. Combining Multiple Heuristics Online. In Proceedings of the 22nd National Conference on Artificial Intelligence, 1197–1203. Palo Alto, CA: AAAI Press.

Digital Library

[49]

Vrakas, D., Tsoumakas, G., Bassiliades, N.; and Vlahavas, I. 2003. Learning Rules for Adaptive Planning. In Proceedings of the 13th International Conference on Automated Planning and Scheduling, 82–91. Menlo Park, CA: AAAI Press.

[50]

Weerawarana, S., Houstis, E. N., Rice, J. R., Joshi, A.; and Houstis, C. E. 1996. Pythia: A Knowledge‐Based System to Select Scientific Algorithms. ACM Transactions on Mathematical Software 22(4): 447–468. https://doi.org/10.1145/235815.235820

Digital Library

[51]

Wolpert, D. H., and Macready, W. G. 1997. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation 1(1): 67–82. https://doi.org/10.1109/4235.585893

Digital Library

[52]

Xu, L., Hutter, F., Hoos, H. H.; and Leyton‐Brown, K. 2012. Evaluating Component Solver Contributions to Portfolio‐Based Algorithm Selectors. In Proceedings of the 15th International Conference on Theory and Applications of Satisfiability Testing (SAT'12), Lecture Notes in Computer Science 228–241. Berlin: Springer.

Digital Library

[53]

Xu, L., Hutter, F., Hoos, H. H.; and Leyton‐Brown, K. 2011. Hydra‐Mip: Automated Algorithm Configuration and Selection for Mixed Integer Programming. Paper presented at the RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion at the International Joint Conference on Artificial Intelligence, Barcelona, Spain, July 16.

[54]

Xu, L., Hoos, H. H.; and Leyton‐Brown, K. 2010. Hydra: Automatically Configuring Algorithms for Portfolio‐Based Selection. In Proceedings of the 24th Conference of the Association for the Advancement of Artificial Intelligence (AAAI‐10), 210–216. Palo Alto, CA: AAAI Press.

[55]

Xu, L., Hutter, F., Hoos, H. H.; and Leyton‐Brown, K. 2009. SATzilla2009: An Automatic Algorithm Portfolio for SAT. Paper presented at the 2009 SAT Competition, Swansea, Wales, UK, 30 June–3 July.

[56]

Xu, L., Hutter, F., Hoos, H. H.; and Leyton‐Brown, K. 2008. SATzilla: Portfolio‐Based Algorithm Selection for SAT. Journal of Artificial Intelligence Research 32:565–606.

Digital Library

[57]

Xu, L., Hoos, H. H.; and Leyton‐Brown, K. 2007. Hierarchical Hardness Models for SAT. In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 696–711. Berlin: Springer

Digital Library

[58]

Yun, X., and Epstein, S. L. 2012. Learning Algorithm Portfolios for Parallel Execution. In Proceedings of the 6th International Conference Learning and Intelligent Optimisation Lion, 323–338. Berlin: Springer.

Cited By

Jiang HWang YTian YZhang XXiao J(2021)Feature Construction for Meta-heuristic Algorithm Recommendation of Capacitated Vehicle Routing ProblemsACM Transactions on Evolutionary Learning and Optimization10.1145/34475401:1(1-28)Online publication date: 26-Apr-2021
https://dl.acm.org/doi/10.1145/3447540
Beham AWagner SAffenzeller MTakadama K(2018)Algorithm selection on generalized quadratic assignment problem landscapesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205585(253-260)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205585
Kotthoff LHurley BO'Sullivan B(2017)The ICON Challenge on Algorithm SelectionAI Magazine10.1609/aimag.v38i2.272238:2(91-93)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1609/aimag.v38i2.2722
Show More Cited By

Recommendations

A discrete gravitational search algorithm for solving combinatorial optimization problems

Metaheuristics are general search strategies that, at the exploitation stage, intensively exploit areas of the solution space with high quality solutions and, at the exploration stage, move to unexplored areas of the solution space when necessary. The ...
A Multi-state Gravitational Search Algorithm for Combinatorial Optimization Problems
CICSYN '15: Proceedings of the 2015 7th International Conference on Computational Intelligence, Communication Systems and Networks

The binary-based algorithms including the binary gravitational search algorithm (BGSA) were designed to solve discrete optimization problems. Many improvements of the binary-based algorithms have been reported. In this paper, a variant of GSA called ...
A variable neighbourhood search structure based-genetic algorithm for combinatorial optimisation problems

In this paper, a variable-neighbourhood-genetic-based-algorithm is proposed for the MAX-SAT problem. Most of the work published earlier on variable neighbourhood search VNS starts from the first neighbourhood and moves on to higher neighbourhoods ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image AI Magazine

AI Magazine Volume 35, Issue 3

Fall 2014

110 pages

ISSN:0738-4602

EISSN:2371-9621

DOI:10.1002/aaai.v35.3

Issue’s Table of Contents

© 2014 The Authors. AI Magazine published by John Wiley & Sons Ltd on behalf of Association for the Advancement of Artificial Intelligence.

Publisher

John Wiley & Sons, Inc.

United States

American Association for Artificial Intelligence

United States

Publication History

Published: 01 September 2014

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jiang HWang YTian YZhang XXiao J(2021)Feature Construction for Meta-heuristic Algorithm Recommendation of Capacitated Vehicle Routing ProblemsACM Transactions on Evolutionary Learning and Optimization10.1145/34475401:1(1-28)Online publication date: 26-Apr-2021
https://dl.acm.org/doi/10.1145/3447540
Beham AWagner SAffenzeller MTakadama K(2018)Algorithm selection on generalized quadratic assignment problem landscapesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205585(253-260)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205585
Kotthoff LHurley BO'Sullivan B(2017)The ICON Challenge on Algorithm SelectionAI Magazine10.1609/aimag.v38i2.272238:2(91-93)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1609/aimag.v38i2.2722
Bossek JTrautmann H(2016)Understanding Characteristics of Evolved Instances for State-of-the-Art Inexact TSP Solvers with Maximum Performance DifferenceAI*IA 2016 Advances in Artificial Intelligence10.1007/978-3-319-49130-1_1(3-12)Online publication date: 29-Nov-2016
https://dl.acm.org/doi/10.1007/978-3-319-49130-1_1
Lieder FPlunkett DHamrick JRussell SHay NGriffiths T(2014)Algorithm selection by rational metareasoning as a model of human strategy selectionProceedings of the 28th International Conference on Neural Information Processing Systems - Volume 210.5555/2969033.2969147(2870-2878)Online publication date: 8-Dec-2014
https://dl.acm.org/doi/10.5555/2969033.2969147

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents