Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Santos, Haroldo Gambini | - |
Autor(es): dc.contributor | Blum, Christian Clemens | - |
Autor(es): dc.contributor | Merschmann, Luiz Henrique de Campos | - |
Autor(es): dc.contributor | Silva, Rodrigo César Pedrosa | - |
Autor(es): dc.contributor | Toffolo, Túlio Ângelo Machado | - |
Autor(es): dc.creator | Vilas Boas, Matheus Guedes | - |
Data de aceite: dc.date.accessioned | 2025-08-21T15:35:01Z | - |
Data de disponibilização: dc.date.available | 2025-08-21T15:35:01Z | - |
Data de envio: dc.date.issued | 2020-04-08 | - |
Data de envio: dc.date.issued | 2020-04-08 | - |
Data de envio: dc.date.issued | 2019 | - |
Fonte completa do material: dc.identifier | http://www.repositorio.ufop.br/handle/123456789/12041 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1018941 | - |
Descrição: dc.description | Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. | - |
Descrição: dc.description | 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 thesis, we propose Integer Programming based approaches to build decision trees for the Algorithm Selection Problem. These techniques allow the automation of 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. We tested our approach from different perspectives: (i) univariate approach, where for each branch node, only one cutoff point of a feature is chosen and (ii) multivariate approach, where for each branch node, weights for multiple features are used (oblique decision trees). Considering the current scenario where the number of cores per machine has increased considerably, we also propose a new approach based on recommendation of concurrent algorithms. To evaluate our approaches, extensive computational experiments were executed using a dataset that considers the linear programming algorithms implemented in the COIN-OR Branch & Cut solver across a comprehensive set of instances, including all MIPLIB benchmark instances. We also conducted experiments with the scenarios/- datasets of the Open Algorithm Selection Challenge (OASC) held in 2017. Considering the first dataset and a 10-fold cross validation experiment, while selecting the single best solver across all instances decreased the total running time by 2%, our univariate approach decreased the total running time by 68% and using the multivariate approach, the total running time is decreased by 72%. An even greater performance gain can be obtained using concurrent algorithms, something not yet explored in the literature. For our experiments, using three algorithm configurations per leaf node, the total running time is decreased by 85%. These results indicate that our method generalizes quite well and does not overfit. Considering the results obtained using the scenarios of the OASC, the experimental results showed that our decision trees can produce better results than less interpretable models, such as random forest, which has been extensively used for algorithm recommendation. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | aberto | - |
Direitos: dc.rights | Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 04/04/2020 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação. | - |
Palavras-chave: dc.subject | Algoritmos de computador | - |
Palavras-chave: dc.subject | Mineração de dados - computação | - |
Palavras-chave: dc.subject | Programação inteira | - |
Título: dc.title | Decision trees for the algorithm selection problem : integer programming based approaches. | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositório Institucional - UFOP |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: