Algorithm selection for combinatorial search problems: a survey

DOI10.1007/978-3-319-50137-6_7MaRDI QIDQ4988865zbMATH OpenOpenAlexFDO

Authors Lars Kotthoff

Publication date 20 May 2021

Published in Data Mining and Constraint Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.7959

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) General topics in the theory of algorithms (68W01)

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 paper contrasts and compares different methods for solving the problem as well as ways of using these solutions. It closes by identifying directions of current and future research.

Recommendations

• The algorithm selection competitions 2015 and 2017
• Combinatorial search: from algorithms to systems
• Summary of algorithm selection problems based on meta-learning
• ASlib: a benchmark library for algorithm selection
• Advanced Portfolio Techniques

Cited in

(22)

• Gorthaur-EXP3: bandit-based selection from a portfolio of recommendation algorithms balancing the accuracy-diversity dilemma
• Neural large neighborhood search for routing problems
• Variable ordering for decision diagrams: a portfolio approach
• Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art
• The algorithm selection competitions 2015 and 2017
• On the design of metaheuristics-based algorithm portfolios
• Deep learning assisted heuristic tree search for the container pre-marshalling problem
• Instance space analysis and algorithm selection for the job shop scheduling problem
• Instance-specific algorithm configuration
• Artificial Intelligence and Soft Computing - ICAISC 2004
• A PAC Approach to Application-Specific Algorithm Selection
• Combinatorial search: from algorithms to systems
• Computational Science and Its Applications – ICCSA 2004
• Speeding up neural network robustness verification via algorithm configuration and an optimised mixed integer linear programming solver portfolio
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
• Automated streamliner portfolios for constraint satisfaction problems
• Optimization of heuristic search using recursive algorithm selection and reinforcement learning
• One-shot learning for MIPs with SOS1 constraints
• Solving the strip packing problem with a decomposition framework and a generic solver: implementation, tuning, and reinforcement-learning-based hybridization
• Machine learning based algorithm selection and genetic algorithms for serial-batch scheduling
• Which algorithm to select in sports timetabling?
• Machine learning and data analysis method for predicting an efficient algorithm for heterogeneous multicore scheduling

This page was built for publication: Algorithm selection for combinatorial search problems: a survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4988865)