Optimal decision trees for the algorithm selection problem: integer programming based approaches

Autor: Luiz Henrique de Campos Merschmann, Greet Van den Berghe, Haroldo Gambini Santos, Matheus Guedes Vilas Boas
Rok vydání: 2019
Předmět:
FOS: Computer and information sciences
G.4
Technology
Computer Science - Machine Learning
Mathematical optimization
Discrete Mathematics (cs.DM)
Linear programming
Computer science
Strategy and Management
0211 other engineering and technologies
Decision tree
Social Sciences
G.2.1
SOFTWARE
02 engineering and technology
G.2.3
Management Science and Operations Research
algorithm selection problem
Machine Learning (cs.LG)
Business & Economics
Management of Technology and Innovation
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
90Cxx
90C05
Data Structures and Algorithms (cs.DS)
Business and International Management
integer programming
PROGRESS
Integer programming
Science & Technology
021103 operations research
decision trees
Operations Research & Management Science
COIN-OR branch and cut
feature-based parameter tuning
data mining
Solver
Management
Computer Science Applications
Benchmark (computing)
020201 artificial intelligence & image processing
Computational problem
variable neighborhood search
Variable neighborhood search
Computer Science - Discrete Mathematics
Optimal decision
Zdroj: International Transactions in Operational Research. 28:2759-2781
ISSN: 1475-3995
0969-6016
DOI: 10.1111/itor.12724
Popis: Even though it is well known that for most relevant computational problems different algorithms may perform better on different classes of problem instances, most researchers still focus on determining a single best algorithmic configuration based on aggregate results such as the average. In this paper, we propose Integer Programming based approaches to build decision trees for the Algorithm Selection Problem. These techniques allow automate three crucial decisions: (i) discerning the most important problem features to determine problem classes; (ii) grouping the problems into classes and (iii) select the best algorithm configuration for each class. To evaluate this new approach, extensive computational experiments were executed using the linear programming algorithms implemented in the COIN-OR Branch & Cut solver across a comprehensive set of instances, including all MIPLIB benchmark instances. The results exceeded our expectations. While selecting the single best parameter setting across all instances decreased the total running time by 22%, our approach decreased the total running time by 40% on average across 10-fold cross validation experiments. These results indicate that our method generalizes quite well and does not overfit.
International Transactions in Operational Research. 2019
Databáze: OpenAIRE
Externí odkaz: