Algoritmos exatos e heurísticos para o problema Perfect Awareness

• Processo: 19/22297-1
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de julho de 2020
• Data de Término da vigência: 28 de fevereiro de 2021
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Pedro Jussieu de Rezende
• Beneficiário: Felipe de Carvalho Pereira
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Otimização combinatória Programação linear inteira Programação heurística Algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos Heurísticos | Algoritmos Exatos | Grasp | Otimização Combinatória | Problema Perfect Awareness | Programação Linear Inteira | Otimização Combinatória

Resumo

Apresentamos uma proposta de pesquisa a ser desenvolvida durante o curso de mestrado em Ciência da Computação do Instituto de Computação da Unicamp. O tópico de pesquisa envolve o estudo de um problema de otimização combinatória NP-difícil denominado perfect awareness. Neste problema, considera-se uma rede social na qual uma informação é propagada entre indivíduos conectados. O objetivo é selecionar um conjunto inicial de disseminadores de menor tamanho possível, de modo que, ao fim do processo de propagação, todos os indivíduos sejam conhecedores da informação. Esta proposta traz uma contextualização do problema, assim como sua definição formal e uma revisão bibliográfica. É descrita ainda uma metodologia de trabalho que visa solucionar o problema através de algoritmos heurísticos baseados na meta-heurística GRASP e por meio de algoritmos exatos via programação linear inteira. Neste documento, também são elencados os objetivos do trabalho, os resultados preliminares e os esperados, e um cronograma de atividades.Um conjunto de experimentos inicial foi realizado e os resultados mostraram-se promissores, uma vez que uma das heurísticas implementadas superou o único algoritmo proposto na literatura para o problema até o momento. Diante disso, o principal objetivo deste trabalho é desenvolver novos algoritmos para resolver o problema perfect awareness e submetê-los a experimentos computacionais para que os resultados obtidos sejam comparados com os melhores algoritmos conhecidos para o problema. (AU)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

PEREIRA, FELIPE DE C.; DE REZENDE, PEDRO J.; DE SOUZA, CID C.; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Effective Heuristics for the Perfect Awareness Problem. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 10-pg., 2021-01-01. (14/12236-1, 19/22297-1, 18/26434-0)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

PEREIRA, Felipe de Carvalho. Um estudo computacional do Problema do Gnosticismo Perfeito. 2021. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.