Qualificação de doutorado do discente Matheus Guedes, dia 05/10/17.

Qualificação de doutorado do discente Matheus Guedes, dia 05/10/17, Sala Multimídia ICEB.

Título: Optimal Decision Trees for Feature Based Parameter Tunning

Banca: Prof. Dr. Christian Clemens Blum; Prof. Dr. Puca Huachi Vaz Penna; Prof. Dr. Alan Robert Resende de Freitas

Resumo

In this thesis we propose a hybrid approach for the Feature Based Parameter Tuning Problem (FBPTP) of Mixed-Integer Programming (MIP) solvers. Integer Programming (IP) is the most successful technique for solving hard combinatorial optimization problems. Modern IP solvers are very complex programs composed of many different procedures whose execution is embedded in the Branch & Bound framework. The activation of these procedures as well the definition of exploration strategies for the search tree can be done by setting different parameters. The diversity of models that can be formulated as MIP problems can be exploited to devise better parameter settings for groups of problems, considering lessons learned from previous experiments. Decision trees can be used to define the best parameter settings for different problem types. However the construction of optimal decision trees is a NP-Hard problem. Thus, we propose an Integer Programming Model to construct optimal decision trees for FBPTP. A Variable Neighborhood Search heuristic is employed to accelerate the production of high quality solutions. Computational experiments in a diverse set of 308 benchmark instances using the open source COIN-OR CBC solver were performed with different parameter sets and encouraging computational results were obtained for the open source MIP solver COIN-OR CBC: executions in the test sets considering decisions based on our decision trees built using training sets prove the effectiveness of the proposed method compared to default settings, an improvement of 7% in solver's performance was obtained both in execution times as well in the number of solved instances.

Data: Quinta-feira (05/10), às 15 horas, na Sala Multimídia do ICEB.

Departamento de Computação  |  ICEB  |  Universidade Federal de Ouro Preto
Campus Universitário Morro do Cruzeiro  |  CEP 35400-000  |  Ouro Preto - MG, Brasil
Telefone: +55 31 3559-1692  |  decom@iceb.ufop.br