Data e horário: Segunda-feira, 14/09, das 11:15 às 11:45
Local: Auditório - Bloco V
Chair: Evelin Heringer Manoel Krulikovski
Título: O Método de Trajetória Dual para Fixação de Variáveis com Aplicação ao Problema de Recobrimento de Conjuntos
Resumo: A resolução de problemas de programação inteira pode ser computacionalmente custosa, sobretudo em instâncias de grande porte. Neste trabalho, propomos o Dual Path Fixing (DPF), uma técnica de fixação de variáveis que explora soluções duais intermediárias geradas durante a execução do algoritmo Simplex. Diferentemente do método clássico de reduced cost fixing (RCF), que emprega apenas a solução dual ótima da relaxação linear, o DPF aproveita toda a trajetória de soluções duais factíveis, permitindo identificar oportunidades adicionais de fixação sem custo computacional significativo. Como aplicação, estudamos o Problema de Recobrimento de Conjuntos, um problema clássico de programação inteira com diversas aplicações práticas. Para coletar as soluções duais intermediárias, adaptamos o solver GLPK 5.0. A validação experimental foi realizada em 60 instâncias, incluindo casos derivados do problema de localização de pontos de pouso de emergência e instâncias do benchmark OR-Library. Os resultados mostram que o DPF fixa tantas ou mais variáveis que o RCF em todas as instâncias avaliadas. Além disso, sua combinação iterativa com a eliminação de linhas dominadas reduziu, em média, 69,8% das variáveis nas instâncias de pontos de pouso de emergência e 91,8% nas instâncias da OR-Library.
Data e horário: Segunda-feira, 14/09, das 11:45 às 12:15
Local: Auditório - Bloco V
Chair: Emerson Vitor Castelani
Título: On a Geometric Graph-Covering Problem Related to Optimal Safaty-Landing-Site Location
Resumo: O desenvolvimento de sistemas de transporte aéreo urbano tem atraído o interesse de grandes empresas nos últimos anos. Um problema que surge do seu desenvolvimento é a necessidade de locais para pouso de emergência, que devem cumprir certas exigências de segurança. Neste contexto, propomos formulações de programação inteira para o problema de localização ótima de Pontos de Pouso de Emergência (Safety Landing Sites – SLSs). Foram desenvolvidos dois modelos para o problema. O primeiro modelo, baseado em recobrimento de conjuntos, considera que os locais candidatos são finitos e representados por pontos discretos, e é formulado como um problema de programação linear binária. O segundo modelo, trata do caso mais geral, no qual os SLS devem estar contidos em regiões convexas, sendo formulado como um problema de programação inteira mista com restrições cônicas de segunda ordem. Foi desenvolvido um algoritmo gerador de instâncias, as quais foram utilizadas nos experimentos numéricos que validam a aplicabilidade dos modelos. Por fim, introduzimos o strong fixing para os dois modelos, uma técnica que permite fixar o valor de variáveis, aprimorando a técnica clássica conhecida como reduced-cost fixing. O strong fixing demonstrou ser altamente eficaz na redução do tamanho de problemas inteiros nos nossos experimentos.
Data e horário: Segunda-feira, 14/09, das 12:15 às 13:00
Local: Auditório - Bloco V
Chair: Cássio Machiaveli Oishi
Título: Lattice Coding for Reliable and Efficient Communication
Resumo: Lattice codes provide a powerful framework for designing communication schemes that combine favorable geometric properties with algebraic structure. In this talk, we present the main results of the thesis Lattice Coding for Reliable and Efficient Communication, focusing on two communication problems: reliable transmission over the additive white Gaussian noise (AWGN) channel and index coding with receiver side information. For the AWGN channel, we introduce an extension of Construction π_A to the noncommutative setting of Hurwitz quaternion integers. The resulting multilevel lattice codes enable efficient multistage decoding and yield sequences of lattices with arbitrarily small decoding error probability under suitable noise conditions. We then discuss lattice index coding schemes based on Construction π_A, including bounds on the side information gain and explicit constructions achieving uniform gain under suitable arithmetic conditions. These results illustrate how algebraic and geometric structures can be exploited to design reliable and computationally efficient communication schemes.