Um Estudo Empírico sobre Fluxo em Redes

• Processo: 22/10215-3
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de outubro de 2022
• Data de Término da vigência: 30 de setembro de 2024
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Mário César San Felice
• Beneficiário: Ricardo Araújo da Silva
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Assunto(s): Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Análise Empírica | Fluxo em redes | Fluxo Máximo | Programação linear e inteira | Otimização Combinatória

Resumo

No problema de fluxo máximo busca-se determinar como enviar a maior quantidade de fluxo possível entre dois vértices de uma rede que possui capacidades nos arcos, de modo que nenhuma capacidade seja excedida e nenhum fluxo se perca. Esse problema é bastante relevante por ser útil na modelagem de uma grande variedade de outros problemas.Este projeto tem como objetivos o estudo de algoritmos para o problema do fluxo máximo, bem como a implementação, testes e análise de desempenho desses algoritmos, além da produção de um relatório técnico com os principais resultados estudados e obtidos.Além disso, gostaríamos de apresentar os resultados empíricos obtidos em alguma conferência da área, pois, embora os algoritmos e suas complexidades de pior caso sejam bem conhecidos, o desempenho empírico dos mesmos em diferentes tipos de instâncias é menos abordado.Tendo oportunidade, pretendemos estender os estudos para outros problemas de fluxo em rede ou problemas NP-difíceis de corte.Destacamos que esta iniciação científica também objetiva introduzir o candidato à área de pesquisa científica e complementar sua formação em Engenharia de Computação, aprofundando seu conhecimento nas áreas de otimização combinatória e de projeto e análise de algoritmos.