MATHEURÍSTICAS PARA O PROBLEMA DE SAFE SET

O Problema do safe set está relacionado ao problema de particionamento de um grafo em componentes conexas, com restrições específicas sobre o peso das partes da partição. O safe set é um conjunto de vértices de um grafo, no qual cada componente conexo do subgrafo induzido pelo conjunto possui peso igual ou maior ao peso de cada uma das componentes conexos do subgrafo induzido pelos vértices que não pertencem ao safe set, e que é a ele adjacente. O Problema do safe set busca justamente encontrar em um grafo um safe set de peso mínimo. Este problema possui diversas aplicações práticas, como a alocação de refúgios temporários em grandes edifícios comerciais. Neste caso, cada sala segura deve estar acessível aos usuários das salas adjacentes e, portanto, sua capacidade deve ser pelo menos igual às capacidades das salas conectadas a ela. Devido às suas restrições, o Problema do safe set é NP-difícil. Portanto, é de grande importância buscar heurísticas para obter soluções viáveis para esse problema em tempo computacional razoável. Nesse cenário insere-se este trabalho, que tem como objetivo aplicar técnicas de metaheurísticas baseadas em programação matemática (matheurísticas), para construir soluções viáveis para o Problema do safe set de maneira computacionalmente eficiente. Para tanto, estão sendo desenvolvidas estratégias baseadas em matheurísticas, como a Large Neighborhood Search e a Relax and Fix, e avaliadas em uma série de instâncias da literatura. Para isso, foi realizada a implementação de um algoritmo Branch-and-Bound a partir de um modelo de programação linear inteira para o Problema do safe set, proposto por Hosteins. A implementação desse algoritmo foi realizada usando-se o resolvedor SCIP, para analisar o desempenho das estratégias escolhidas. Pretende-se, assim, avaliar inicialmente a qualidade das soluções geradas pelas matheurísticas utilizadas, comparando-as com os resultados da literatura. Em seguida, deseja-se avaliar se a incorporação dessas matheurísticas no algoritmo Branch-and-Bound resulta em uma melhora em sua eficiência.