Uma abordagem de programacao linear inteira para o problema da clique maxima com peso nas arestas.

• Processo: 96/00884-9
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de maio de 1996
• Data de Término da vigência: 30 de abril de 1997
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Elder Magalhaes Macambira
• Instituição Sede: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Combinatória Programação linear
• Palavra(s)-Chave do Pesquisador: Clique Maxima | Combinatoria | Programacao Linear

Resumo

O objetivo desse trabalho é estudar o problema da clique máxima com peso nas arestas. Esse estudo será desenvolvido em dois tipos de abordagem. A principal delas irá se concentrar na tentativa de obter soluções exatas para o problema. Para isso, faremos uso de técnicas de PLI. Nosso objetivo é implementar um algoritmo branch-and-cut, o que nos levará a fazer um estudo aprofundado no politopo associado ao problema. Numa outra abordagem iremos desenvolver novas heurísticas para o problema capazes de obter melhores soluções que aquelas obtidas pelas heurísticas existentes na literatura. (AU)

Publicações acadêmicas

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

MACAMBIRA, Elder Magalhaes. Uma abordagem de programação linear inteira para o problema de clique maxima com peso nas arestas. 1997. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.