Uso de cortes canonicos no metodo de ramificacao local para problemas inteiros 0-1 mistos.

• Processo: 04/12890-1
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2005
• Data de Término da vigência: 30 de junho de 2006
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Rafael Francisco dos Santos
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Otimização combinatória Programação linear inteira
• Palavra(s)-Chave do Pesquisador: Cortes Canonicos | Otimizacao Combinatoria | Programacao Inteira | Ramificacao Local

Resumo

Diversos problemas de Programação Inteira Mista (MIP) são NP-difíceis e, apesar do notável avanço dos resolvedores de MIP, em muitos casos, a simples obtenção de uma solução de boa qualidade ainda é um desafio. Em artigo recente de Fischetti e Lodi [1] propôs-se um método heurístico para MIPs 0-1 que pode ser inserido no contexto geral de um algoritmo Branch-and-Bound de um resolvedor comercial. O método tem como objetivo acelerar a busca por soluções sub-ótimas, explorando a eficiência dos resolvedores no tratamento de "pequenos" subproblemas. Isso é feito introduzindo-se desigualdades inválidas no modelo original, as quais são denominadas de ramificações locais. Analisando-se o método de ramificação local, nota-se que ele acrescenta planos de cortes superficiais (descartam poucas soluções) e que estes cortes ocorrem com grande freqüência. Assim, é possível que a introdução de cortes mais profundos possam melhorar a eficiência do método, mesmo que isso implique em maior esforço para resolver os subproblemas. Ocorre que os cortes de ramificações locais são casos especiais dos cortes canônicos para MIPs com variáveis binárias introduzidos por Balas e Jeroslow [2]. Assim, o objetivo deste trabalho é estender o método de ramificação local incorporando a ele cortes canônicos que sejam mais profundos do que aqueles usados na versão proposta por em [1] e verificar sua eficiência computacional. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

SANTOS, Rafael Francisco dos. Uso de cortes canonicos no metodo de ramificação local para problemas inteiros 0-1 mistos. 2006. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.