Heurísticas GRASP para identificação de matrizes de rede em sistemas lineares

• Processo: 06/00952-8
• Linha de fomento: Bolsas no Brasil - Iniciação Científica
• Vigência (Início): 01 de setembro de 2006
• Vigência (Término): 31 de agosto de 2007
• Área do 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: João Marcos da Cunha Silva
• Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Otimização combinatória Heurística Meta-heurística Relaxação Lagrangeana Algoritmos

Resumo

Neste projeto estamos interessados em obter grandes matrizes de rede que ocorram como submatrizes da matriz de restrições dos modelos de Programação Inteira de alguns problemas clássicos de Otimização Combinatória como os de Partição, Cobertura e Empacotamento de subconjuntos. O objetivo é encontrar a maior submatriz de rede e para isso serão usados metaeurísticas baseadas na técnica GRASP. A qualidade das soluções geradas pelas heurísticas desenvolvidas será avaliada por meio de comparações com alguma outra heurística proposta na literatura e por limitantes duais e soluções ótimas obtidas por algoritmos a serem desenvolvidos um outro projeto de pesquisa que está sendo submetido simultaneamente. (AU)