Algoritmos paralelos em GPUs para problemas de programação quadrática binária irrestrita

Resumo

Empresas, indústrias, órgãos governamentais e não governamentais precisam resolver diariamente problemas de origem combinatória. Estratégias de decisão, soluções para problemas do estado e ordenação de processos são temas essenciais para a melhoria do desempenho em qualquer setor. Daí tem-se a importância do estudo de problemas de otimização combinatória.Existe uma vasta literatura sobre programação quadrática binária irrestrita e vários métodos (exatos e heurísticos) foram propostos ao longo dos últimos 20 anos. Os métodos heurísticos fornecem suporte para resolver instâncias grandes em um tempo satisfatório, enquanto os métodos exatos possibilitam encontrar soluções ótimas para as instâncias. Neste projeto mostramos como problemas de otimização combinatória podem ser transformados em problemas de programação quadrática binária irrestrita (UQP), e então os resolvemos com algoritmos implementados em unidades de processamento gráfico, em inglês Graphics Processing Units (GPUs), usando a arquitetura CUDA. Dentre os diversos problemas que trataremos neste projeto, destacamos os problemas de empacotamento. O problema de empacotar itens (caixas, boxes) em objetos maiores (pallets) é uma atividade rotineira em certas fábricas. O manufacturer's pallet loading problem é o problema de empacotar itens de dimensões idênticas. Este problema pode ser visto como o problema de encontrar um máximo conjunto independente em um grafo finito particular e este pode ser posto na forma UQP.Nossa proposta é resolver problemas utilizando métodos heurísticos e exatos de maneira sequencial e paralela, realizar comparações e obter com isto informações úteis que possam ajudar a resolver problemas reais. (AU)