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.