Busca avançada
Ano de início
Entree

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

Processo: 12/06027-5
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de junho de 2012
Vigência (Término): 31 de maio de 2013
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
Pesquisador responsável:Cláudio Nogueira de Meneses
Beneficiário:Eduardo Batista Gomes Moreira
Instituição-sede: Centro de Matemática, Computação e Cognição (CMCC). Universidade Federal do ABC (UFABC). Ministério da Educação (Brasil). Santo André , SP, Brasil
Vinculado ao auxílio:10/10133-0 - Problemas de corte, empacotamento, dimensionamento de lotes e programação da produção, e suas integrações em contextos industriais e logísticos, AP.TEM
Assunto(s):Otimização combinatória

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)