Heuristicas para programação inteira com trajetorias de busca factiveis e infactiveis

Autor(es)

André Kazuo Takahata

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação
• Data de defesa: 2009-08-05

Membros da banca

Vinícius Amaral Armentano; Edson Luiz França Senne; Cid Carvalho de Souza

• Orientador: Vinícius Amaral Armentano

Resumo

Este trabalho trata do desenvolvimento de heurísticas de busca genéricas para obtenção de soluções de problemas de otimização combinatória formulados como modelos de programação linear inteira, com o uso do pacote de otimização XPRESS. Este é um tema recente, em que são conjugados a flexibilidade de heurísticas e os avanços dos solvers de otimização para a obtenção de soluções de alta qualidade em tempo reduzido. As heurísticas propostas são baseadas em arredondamentos gerados a partir de raios de um cone, cujo vértice é associado à solução ótima da relaxação de programação linear, e em trajetórias factíveis e infactíveis em relação à fronteira desta relaxação. A motivação para este enfoque é dada pelo apelo geométrico e no sucesso de estratégias similares em heurísticas para problemas combinatórios. O trabalho descreve a concepção e a implementação dessas heurísticas e apresenta resultados de testes em instâncias da literatura. (AU)

• Processo FAPESP: 07/01530-2 - Heurísticas para programação inteira com trajetórias de busca factíveis e infactíveis
• Beneficiário: André Kazuo Takahata
• Modalidade de apoio: Bolsas no Brasil - Mestrado