Heurísticas para programação inteira com trajetórias de busca factíveis e infactíveis

Resumo

Este projeto trata do desenvolvimento de heurísticas genéricas de busca que interagem com pacotes de otimização para solução de problemas de otimização combinatória formulados como programação linear inteira mista. Este é um tema recente que utiliza o expressivo avanço em pesquisa e desenvolvimento desses pacotes e a flexibilidade de heurísticas para obter soluções de alta qualidade em tempo computacional reduzido. As heurísticas são baseadas em arredondamento de soluções ao longo de um raio do cone com vértice associado à solução ótima da relaxação de programação linear, e em trajetórias factíveis e infactíveis com relação à fronteira desta relaxação. A motivação para este enfoque situa-se no apelo geométrico e no sucesso de heurísticas de busca local e meta-heurísticas para problemas combinatórios não formulados como problemas de programação inteira. O desenvolvimento envolve o projeto e implementação das heurísticas, e experimentos computacionais em problemas testes da literatura.