Qualificação de doutorado do discente Samuel Brito, dia 02/06/17.

Qualificação de doutorado do discente Samuel Brito, dia 02/06/17, as 10:00 na Sala de Seminários DECOM - ICEB III, UFOP.

Banca: Prof. Dr. Marcone Jamilson Freitas Souza - UFOP; Prof. Dr. Luidi Gelabert Simonetti - UFF; Prof. Dr. Marcus Vinicius Soledade Poggi de Aragão - PUC-RIO.

Título: Reformulação Automática de Problemas de Programação Inteira

Resumo: Neste trabalho são abordadas implementações de rotinas de separação de cortes para problemas de Programação Inteira, cujo objetivo é melhorar os limites duais obtidos na relaxação linear e, consequentemente, acelerar a convergência para a solução ótima. Essas implementações envolvem a separação de cortes de clique, cobertura e Chvátal-Gomory. A rotina de separação de cliques utiliza um módulo para gerar todas desigualdades de cliques violadas, enquanto o processo de separação de cortes de cobertura faz uso da Programação Dinâmica para gerar um conjunto de coberturas mínimas. Para ambas as rotinas foram propostos e implementados módulos de extensão, que visam a inserção de novas variáveis nas desigualdades geradas a fim de reforçá-las. Essas rotinas obtiveram resultados significativamente melhores tanto na qualidade das soluções quanto no tempo de execução quando comparadas às rotinas implementadas pelo resolvedor CBC. Soluções com limites mais fortes também foram obtidas quando comparadas com o CPLEX. Entretanto, nessa comparação o tempo de execução gasto foi, na maioria das vezes, maior. A última rotina implementada foi uma abordagem para gerar cortes de Chvátal-Gomory, baseada em um modelo de Programação Inteira contido na literatura. Algumas alterações foram propostas e implementadas, de forma a facilitar a escrita de restrições para reforçar a formulação original. A partir dessas alterações, algumas restrições adicionais foram desenvolvidas e inseridas no modelo. Os experimentos computacionais mostraram uma ligeira melhoria dos limites em relação ao modelo original.