25 nov 2024
10:00 Defesa de Mestrado Sala 53 do IC2
Tema
Algoritmos Exatos e Heurísticas para o Posicionamento de Propagandas em Banners
Aluno
Jorge Menezes dos Santos
Orientador / Docente
Rafael Crivellari Saliba Schouery
Breve resumo
Neste trabalho, propomos e abordamos um problema de disposição e posicionamento de propagandas em banners digitais, denominado MAXSPACE-P. O MAXSPACE-P é uma variante do problema de otimização combinatória, NP-Difícil, MAXSPACE. A sua ideia chave é valorizar o fator de atração conferido por propagandas que aparecem primeiro em uma página web, no topo de um banner digital. Para tratar o problema, desenvolvemos três formulações de programação linear inteira mista, juntamente com algumas desigualdades válidas e rotinas de pré-processamento. Também foram desenvolvidas duas heurísticas: uma baseada em Busca Tabu e outra baseada em Geração de Colunas. Avaliamos o desempenho dos algoritmos propostos com um conjunto de instâncias da literatura. Em nossos experimentos computacionais, a formulação matemática que mais se sobressaiu resolveu cerca de 38% das instâncias pequenas, apresentando um gap médio final de 0,09%, sendo esse o único tipo de instância em que elas puderam ser executadas devido à exigência de recursos computacionais elevados para executar instâncias maiores. Do ponto de vista das heurísticas, a heurística baseada em geração de colunas foi o segundo melhor algoritmo, dentre os cinco propostos para as instâncias pequenas, ficando atrás apenas da Formulação Posicional. Para as instâncias de tamanho médio e grande, a Busca Tabu obteve os melhores resultados e se mostrou uma boa alternativa, dada a dificuldade de aplicar as formulações matemáticas em instâncias grandes.
Banca examinadora
Titulares:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| Pedro Henrique Del Bianco Hokama | IMC/UNIFEI |
| Santiago Valdés Ravelo | IC/UNICAMP |
Suplentes:
| Flávio Keidi Miyazawa | IC/UNICAMP |
| Uéverton dos Santos Souza | IC/UFF |