Defesa de Mestrado de Thiago Macedo Gomes; dia 30/01/2014, as 14:00, Sala de Seminários.

Defesa de Mestrado de Thiago Macedo Gomes; dia 30/01/2014, as 14:00, Sala de Seminários.

Título: pRINS: Uma Matheurística Para Problemas Binários.

Banca: Prof. Dr. Marcone Jamilson Freitas Souza; Prof. Dr. Haroldo Gambini Santos; Prof. Dr. Nelson Maculan Filho; Profa. Dra. Laurqa Silvia Bahiense da Silva Leite.

Resumo: Uma importante tecnica para resolver problemas de otimização e por meio de Programação Inteira Mista (MIP, do inglês Mixed Integer Programming). Uma formulação MIP de um problema envolve um conjunto de variaveis, um conjunto de restrições sobre estas variaveis, um conjunto de restrições de integralidade e uma função objetivo linear a otimizar. Aplicações em otimização inteira são encontradas em diversas areas do conhecimento, incluindo-se roteamento de veículos, alocação de enfermeiros, programação de horarios, entre outros. O uso de metodos heurísticos tem sido empregado na resolução de problemas MIP como uma forma de acelerar o processo de busca na arvore de branching. Este trabalho propõe uma adaptação da heurística MIP Relaxation Induced Neighborhood Search (RINS), a qual explora a ideia deixar variaveis de mesmo valor na solução inteira e fracionaria corrente. O método proposto, denominado pRINS, explora explicitamente tecnicas de pre-processamento, procurando sistematicamente por um numero ideal de xações, visando a produzir sub-problemas de tamanho controlado.As variaveis a xar são organizadas por meio de um vetor de prioridade, onde foram propostas três maneiras de escolha destas variaveis, cada uma delas dando origem a uma variante do metodo. Em seguida os problemas são criados e resolvidos de modo semelhante ao metodo Variable Neighborhood Descent ate que um criterio de parada seja satisfeito. Os resultados das variantes do metodo foram comparados com os do resolvedor COIN-OR CBC stand-alone e com o metodo RINS original. Pelos resultados obtidos, o metodo proposto se mostrou com desempenho superior a essas duas técnicas.
PALAVRAS CHAVE. Matheursticas, MIP Heursticas, Otimizac~ao Inteira, RINS,
Programac~ao Matematica.