Qualificação de doutorado do discente Danilo Santos, dia 18/07/18, na Sala de Seminários do DECOM.

Qualificação de doutorado do discente Danilo Santos, dia 18/07/18, na Sala de Seminários do DECOM.

Título: Geração de Planos de Corte Usando Recursos Computacionais Heterogêneos

Data: 18/07/2018 às 09:30

Resumo:
Neste trabalho é proposta uma nova abordagem para a separação de planos de corte em problemas de programação inteira com uso de recursos computacionais heterogêneos (CPU-GPU), com o objetivo de usar o alto poder de paralelismo das Unidades de Processamento Gráfico. Os métodos de separação de cortes podem auxiliar no resolvedores de programação linear de modo a acelerar o processo de convergência para a solução ótima ao melhorar os limites duais da relaxação linear dos problemas. A abordagem objetiva obter um grande número de desigualdades válidas violadas não redundantes do tipo mod-k com uso de duas fases. A primeira fase utiliza de um grupo definido de restrições baseado em características específicas do problema abordado, e o processo de separação verifica um conjunto de multiplicadores baseado nos coeficientes e lado direito de cada restrição original. A segunda fase baseia-se em um método de monte-carlo combinando restrições e cortes gerados na fase 1 de modo gerar desigualdades violadas à serem inseridas na formulação. Uma técnica de reforço de cortes é aplicada para melhorar os cortes obtidos nas duas fases. Experimentos iniciais foram realizado com o Problema de Escalonamento de Projetos com Restrição de Recursos. Nos resultados preliminares, é possível verificar que a abordagem ao utilizar os recursos da GPU obtém um grande diferencial ao comparar com a execução usando somente recursos de CPU. Outros experimentos foram realizados com finalidade de justificar a combinação da abordagem, mostrando a importância de cada fase e da utilização da técnica de reforço. Os resultados preliminares mostram que a abordagem é promissora, porém é necessário um aprimoramento dos métodos além de uma rotina de experimentos mais completa.

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@ufop.edu.br