In this paper, we introduce and study mathematical programming formulations for the Least Cost Directed Perfect Awareness Problem (LDPAP), an NP-hard optimization problem that arises in the context of influence marketing. In the LDPAP, we seek to identify influential members of a given social network that can disseminate a piece of information and trigger its propagation throughout the network. The objective is to minimize the cost of recruiting the initial spreaders while ensuring that the information reaches everyone. This problem has been previously modeled as two different integer programming formulations that were tested on a collection of 300 small synthetic instances. In this work, we propose two new integer programming models and three constraint programming formulations for the LDPAP. We also present preprocessing techniques capable of significantly reducing the sizes of these models. To investigate and compare the efficiency and effectiveness of our approaches, we perform a series of experiments using the existing small instances and a new publicly available benchmark of 14 large instances. Our findings yield new optimal solutions to 185 small instances that were previously unsolved, tripling the total number of instances with known optima. Regarding both small and large instances, our contributions include a comprehensive analysis of the experimental results and an evaluation of the performance of each formulation in distinct scenarios, further advancing our understanding of the LDPAP toward the design of exact approaches for the problem.

Otimização Combinatória é de suma importância para aprimorar os processos da indústria e, nos últimos anos, vem ganhando espaço no quadro de desenvolvedores de grandes empresas. Para correta utilização das técnicas de algoritmos exatos, é importante entender as limitações que os próprios computadores impõem. Não é surpresa para ninguém que estes não possuem memória infinita, o que nos leva a problemas de precisão numérica e, consequentemente, erros aritméticos. Existem diversas técnicas que almejam justamente contornar tal limitação. Nesta palestra, exploraremos como /solvers/ de Programação Linear, como o Gurobi, erram ao reportar soluções supostamente ótimas que são, na realidade, inválidas. Entenderemos como este erro se apresenta ao implementarmos algoritmos de /branch-and-price/ e o que pode ser feito a respeito. Em especial, navegaremos pela literatura do assunto começando pelo resultado de Farley (1990), Held, Cook, e Sewell (2012) e Baldacci et al. (2024) utilizando o problema de coloração de grafos como exemplo. Além disso, tocaremos brevemente nas implicações para variáveis de corte, tópico de suma importância para algoritmos de /branch-cut-price/.

O longo tempo de espera para realização de cirurgias eletivas é um desafio global, especialmente após a pandemia de COVID-19. Este tempo é prolongado devido à complexidade do planejamento dessas cirurgias, o qual envolve fatores como a disponibilidade de equipes médicas, gerenciamento de cancelamentos e, principalmente, alocação de salas de cirurgia. Felizmente, podemos abordar este processo com técnicas de otimização e assim propor melhorias no planejamento realizado nos hospitais, considerando toda a complexidade das decisões a serem tomadas. Dito isso, neste seminário teremos uma visão geral deste problema de pesquisa, com a introdução de conceitos, exemplos e desafios relacionados.

Problemas de empacotamento geométrico são de grande interesse na área de otimização combinatória, tanto pelo seu apelo prático como pela sua grande importância teórica. Assim, eles têm sido estudados há séculos. Um exemplo notável é a conjectura de Kepler, datada de 1600, sobre o empacotamento de esferas num espaço euclidiano.O problema de empacotamento abordado nesta apresentação é o problema da mochila com hiperesferas. A entrada é um conjunto de hiperesferas associadas a lucros e um compartimento hiperretangular, a mochila. O objetivo é empacotar um subconjunto das hiperesferas dentro da mochila, maximizando o lucro total das hiperesferas empacotadas. Estamos particularmente interessados em algoritmos de aproximação para este problema e o principal resultado que apresentamos é um PTAS (Polynomial-time Approximation Scheme).

Uma arborescência é um digrafo conexo no qual todo vértice tem grau de entrada um, exceto pela raiz que tem grau de entrada zero. As folhas de T são os vértices com grau de saída zero. Se T é uma arborescência e é um subdigrafo gerador de um digrafo D, dizemos que T é uma arborescência geradora de D. Diversos artigos da literatura investigam arborescências geradoras com número mínimo e máximo de folhas. Neste seminário, apresentaremos alguns resultados estruturais e algorítmicos desses dois problemas. Nos basearemos nos artigos “Branching in Digraphs with Many and Few Leaves - Structural and Algorithmic Results” de Jørgen Bang-Jensen and Gregory Gutin e
“Minimum leaf out-branching and related problems” de Gregory Gutin, Igor Razgon, e Eun Jung Kima.

We propose an exact algorithm for the Graph Burning Problem (GBP), an NP-hard optimization problem that models the spread of influence on social networks. Given a graph G with vertex set V, the objective is to find a sequence of k vertices in V, namely, v_1, v_2, … , v_k, such that k is minimum and the union of the sets of vertices within a distance k−i from each v_i covers the entire vertex set V. We formulate the problem as a set covering integer programming model and design a row generation algorithm for the GBP. Our method exploits the fact that a very small number of covering constraints is often sufficient for solving the integer model, allowing the corresponding rows to be generated on demand. To date, the most efficient exact algorithm for the GBP, denoted here by GARCIA, is able to obtain optimal solutions for graphs with up to 14,000 vertices within two hours of execution. In comparison, our algorithm finds provably optimal solutions approximately 236 times faster, on average, than GARCIA. For larger graphs, memory space becomes a limiting factor for GARCIA. Our algorithm, however, solves real-world instances with more than 3 million vertices in less than 19 minutes, increasing the size of graphs for which optimal solutions are known by a factor of 200. Additionally, we conduct tests on the proposed algorithm using a series of challenging instances composed of grid graphs containing up to 5,000 vertices. As a result, we achieve novel optimal solutions and tight optimality gaps that have not been previously reported in the literature.

O Problema de Empacotamento Colorido nos propõe um conjunto de itens, cada um com tamanho e cor, que devem ser empacotados em recipientes (bins) de mesma capacidade e com a restrição que itens de mesma cor não podem ser empacotados lado a lado. O objetivo é minimizar o número de tais “bins” utilizadas. Neste seminário, mostraremos uma abordagem que utiliza a meta-heurística Variable Neighborhood Search (VNS), a qual é capaz de entregar soluções de boa qualidade (próximas do ótimo) em menos de um minuto, mesmo para situações com mais de 10 mil itens. Tais resultados são frutos da reduzida complexidade computacional das vizinhanças usadas em relação às tradicionais da literatura, o que foi alcançado utilizando ideias de convexidade e programação dinâmica.

The Freeze-Tag Problem (FTP) is a scheduling-like problem motivated by robot swarm activation introduced in 2002 by Arkin et al. This problem seeks an efficient way of activating a set of robots starting from a single initially active one. Activations are achieved through direct contact with active robots, and once a robot becomes active, it can assist in activating other still inactive ones. The complexity of FTP within any Euclidean space remained open until recently. In 2017, Abel et al. and Demaine with Rudoy showed the first results for this problem’s hardness in 2D and 3D, respectively. However, there were no results concerning the Manhattan distance until 2023, when Pedrosa and Silva proved this metric hardness for the 3D case. In this seminar, we will present the newer result with Manhattan distance. Also, we will present hardness results for trees with bounded degrees and show that FTP on unweighted graphs with at least a robot per node is NP-hard to approximate within a factor better than 3/2, even on graphs of diameter two.