[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. / [en] Influence propagation has been the subject of extensive study due to its important role in social networks, epidemiology, and many other areas. Understanding the propagation mechanism is critical, e.g., to control the spread of fake news or to control an epidemic. In this work, we follow an optimization perspective, and attempt to identify the smallest group of users that needs to be converted to achieve an certain influence level over the entire network. We therefore formally study the generalized least cost influence problem, proposing mathematical programming algorithms to solve the challenging problem. We introduce new cutting plane and separation algorithms and embed them into a branch-and-cut algorithm. Our experimental results on classical benchmark instances demonstrates the method ability to solve small-to medium-scale benchmark instances, also finding optimal solutions for some open problems.

[pt] Esta tese generaliza a variante multi-período do clássico problema da Árvore de Steiner com coleta de prêmios (PCST), que visa encontrar um subgrafo conexo que maximize os prêmios recuperados de nós conectados menos o custo de utilização das arestas conectadas. Este trabalho adicionalmente: (a) permite que vértices sejam conectados à árvore em diferentes períodos de tempo; (b) impõe um orçamento pré-definido em arestas selecionadas em um horizonte específico de períodos de tempo; e (c) limita o comprimento total de arestas que podem ser adicionadas em um período de tempo. Um algoritmo branch-and-cut é fornecido para este problema, avaliando satisfatoriamente instâncias benchmark da literatura, adaptadas para uma configuração multi-período, de até aproximadamente 2000 vértices e 200 terminais em tempo razoável. / [en] This thesis generalizes the multi-period variant of the classical Prizecollecting Steiner Tree Problem, which aims at finding a connected subgraph that maximizes the revenues collected from connected nodes minus the costs to utilize the connecting edges. This work additionally: (a) allows vertices to be added to the tree at different time periods; (b) imposes a predefined budget on edges selected over a specific horizon of time periods; and (c) limits the total length of edges that can be added over a time period. A branch-and-cut algorithm is provided for this problem, satisfactorily evaluating benchmark instances from the literature, adapted to a multi-period setting, up to approximately 2000 vertices and 200 terminals in reasonable time.