[en] A NEW BRANCH-AND-CUT ALGORITHM FOR THE GENERALIZED LEAST COST INFLUENCE PROBLEM IN NETWORKS

• Ano de defesa: 2020
• Autor(a) principal: VINICIUS FERREIRA DE SOUZA
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] PROGRAMACAO INTEIRA MISTA; [pt] BRANCH-AND-CUT; [pt] PROPAGACAO DE INFLUENCIA; [en] MIXED INTEGER PROGRAMMING; [en] BRANCH-AND-CUT; [en] INFLUENCE PROPAGATION
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=50960&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=50960&idi=2; http://doi.org/10.17771/PUCRio.acad.50960

[pt] A propagação de influências tem sido objeto de extensos estudos devido a seu importante impacto em redes sociais, epidemiologia e muitas outras áreas. A compreensão do mecanismo de propagação é crítica, por exemplo, para controlar a disseminação de notícias falsas ou controlar uma epidemia. Neste trabalho, seguimos uma perspectiva de otimização e identificamos o menor grupo de usuários que precisam ser convertidos para atingir um certo nível de influência em toda a rede. Portanto, estudamos formalmente o problema de influência de menor custo generalizado, propondo algoritmos de programação matemática para resolver este problema. Introduzimos novos algoritmos de planos de corte e separação, e os incorporamos em um algoritmo de branch-and-cut. Nossos resultados experimentais em instâncias da literatura demonstram a capacidade do método de resolver pequenas e médias instâncias, bem como diminuir o gap da melhor solução conhecida e inclusive encontrando também soluções ótimas para alguns problemas em aberto.