21ago2026
10:00 Defesa de Mestrado Sala 85 do IC2
Tema
Algoritmos Exatos Combinatórios para Problemas de Empacotamento e Mochila
Aluno
Renan Fernando Franco da Silva
Orientador / Docente
Rafael Crivellari Saliba Schouery
Breve resumo
Esta dissertação investiga algoritmos exatos para problemas clássicos de otimização combinatória relacionados a corte, empacotamento e mochila. O foco está em métodos combinatórios que exploram diretamente a estrutura dos problemas e não dependem de resolvedores gerais de programação inteira ou linear. O primeiro estudo desenvolve um resolvedor exato para os Problemas da Mochila e da Mochila Limitada, baseado em programação dinâmica em núcleo e combinado com reduções, regras de dominância, relaxações surrogate e heurísticas primais. O segundo estudo investiga duas classes de instâncias introduzidas na literatura para os Problemas de Empacotamento e de Corte de Estoque como benchmarks difíceis para resolvedores exatos gerais. A primeira classe satisfaz a Integer Round-Up Property (IRUP) e é chamada Augmented IRUP (AI), enquanto a segunda não satisfaz essa propriedade e é chamada Augmented Non-IRUP (ANI). Esse segundo estudo mostra que a estrutura particular dessas classes pode ser explorada para obter algoritmos polinomiais para instâncias AI e algoritmos pseudopolinomiais para instâncias ANI, os quais também podem ser estendidos para o Problema de Skiving Stock. O terceiro estudo propõe um algoritmo combinatório branch-and-bound para os Problemas de Empacotamento e de Corte de Estoque, combinando um modelo arc-flow de satisfatibilidade, reduções combinatórias, relaxações de fluxo e heurísticas primais em um resolvedor exato independente. Em conjunto, esses resultados mostram que as propriedades estruturais de problemas de mochila, corte e empacotamento podem ser exploradas para obter algoritmos exatos teoricamente fundamentados, computacionalmente competitivos e independentes de resolvedores gerais de programação matemática.
Banca examinadora
Titulares:
| Rafael Crivellari Saliba Schouery | IC/UNICAMP |
| José Manuel Vasconcelos Valério de Carvalho | UMinho/Portugal |
| David Pisinger | DTU/Dinamarca |
Suplentes:
| Flávio Keidi Miyazawa | IC/UNICAMP |
| Teobaldo Leite Bulhões Júnior | DCC/UFPB |