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.

Problemas de agrupamento (clustering) surgem quando queremos particionar pontos de um conjunto em classes de equivalência de modo a minimizar uma determinada função custo. Uma das diversas aplicações é para problemas de aprendizado não supervisionado, que cada vez mais é usado em condições com relevância social, como predição de crimes e análise de candidatos a empregos. Nesse cenário, o particionamento justo adiciona restrições adicionais para assegurar igualdade em relação a gênero, condição social, etc. Neste seminário iremos discutir as principais ideias do artigo Fair Clustering Through Fairlets, que trouxe uma ideia inovadora que permite usar algoritmos da literatura sem alterações para o problema com justiça, apenas com a adição de um fator aproximativo. Como exemplos temos o problema do k-center e do k-means.

Clustering is a fundamental problem with applications in many different areas. For a given set of points in a metric space and an integer k, we seek to partition the given points into k clusters. For each computed cluster, one typically defines one point as the center of the cluster. A natural objective is to minimize the sum of the cluster center’s radii, where we assign the smallest radius r to each center such that each point in the cluster is at a distance of at most r from the center. The best-known polynomial time approximation ratio for this problem is 3.389. In the setting with outliers, i.e., we are given an integer m and allow up to m points that are not in any cluster, the best-known approximation factor is 12.365. This talk presents the core ideas that culminates in a recent approximation with a factor 3 + ε for the case without outliers, and briefly discusses how an approximation with the same factor can be devised when outliers are permitted.

O Problema de Corte de Estoque envolve cortar materiais de largura fixa W (como rolos de papel ou chapas de metal/madeira) para atender a um conjunto de pedidos por itens menores, cada um com um tamanho e uma demanda específica. O objetivo é atender a todas as demandas minimizando o número de materiais utilizados. Este problema é amplamente estudado na literatura e serve como um exemplo clássico para a introdução do algoritmo branch-and-price, que combina a técnica de branch-and-bound com uma formulação resolvida por geração de colunas. Esse seminário apresentará a descoberta de um aspecto pouco explorado na literatura e a proposta de um algoritmo de estado-da-arte para o problema, apesar deste problema já ser amplamente estudado. A palestra terá duração de 15 minutos, pois é uma prévia da apresentação que será feita no SBPO, onde concorrerá ao prêmio de melhor trabalho de iniciação científica.