Título: Problema de Formação de Equipe com Caminhos Positivos

Data: 23/10/2023

Horário: 10:00h

Local: Videoconferência

Resumo:

De maneira frequente informações obtidas de redes sociais têm sido utilizadas para resolver aplicações em Pesquisa Operacional, como o Problema de Formação de Equipes, cujo objetivo é encontrar um grupo de indivíduos que cobrem coletivamente um conjunto de habilidades e que podem trabalhar colaborativamente de forma eficaz. Na literatura, diferentes abordagens têm sido usadas para avaliar a sinergia entre membros de uma equipe, dando origem a várias versões desse problema. Neste trabalho, utilizamos a Teoria do Equilíbrio Estrutural para definir compatibilidade entre pares de indivíduos de uma rede social. Para tanto, as redes sociais são representadas por grafos de sinais, e a métrica de compatibilidade é definida a partir da análise de caminhos positivos (com número par de arestas negativas) entre pares de vértices distintos. Com isso, introduzimos e estudamos uma nova versão do problema, a ser chamada Problema de Formação de Equipes com Caminhos Positivos. Como trabalho preliminar, revisitamos o Problema de Caminho Positivo Mínimo em grafos direcionados e não direcionados de sinais, compilando e reescrevendo algoritmos, resultados de complexidade e formulações matemáticas. Para o problema principal, apresentamos duas formulações de Programação Linear Inteira e uma estratégia de decomposição das formulações, que resultou em ganho expressivo de desempenho computacional. Além disso, derivamos desigualdade válidas, algumas das quais contribuíram adicionalmente para a melhoria do desempenho do modelo decomposto. Os métodos, implementados utilizando a linguagem C++ e o solver CPLEX, foram aplicados em um conjunto de instâncias baseadas em redes sociais reais ou sintéticas. Uma análise dos experimentos computacionais realizados comprova a potencial eficiência da estratégia de decomposição e de desigualdades válidas propostas.

Banca:

• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
• Profa. Dra. Tatiane Fernandes Figueiredo (UFC - Coorientadora)
• Prof. Dr. Júlio César Silva Araújo UFC)
• Profa. Dra. Rosa Maria Videira de Figueiredo (Avignon Université)