Análise de algoritmos tipo branch and bound para o problema de designação generalizada

• Processo: 00/04292-6
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2000
• Data de Término da vigência: 31 de agosto de 2002
• Área de conhecimento: Engenharias - Engenharia Elétrica - Sistemas Elétricos de Potência
• Pesquisador responsável: Francisco Villarreal Alvarado
• Beneficiário: Maira Pauline de Lima Alencar
• Instituição Sede: Faculdade de Engenharia (FEIS). Universidade Estadual Paulista (UNESP). Campus de Ilha Solteira. Ilha Solteira , SP, Brasil
• Assunto(s): Problemas de designação generalizada Programação linear inteira Algoritmos Branch-and-bound Branch-and-cut Branch-and-price
• Palavra(s)-Chave do Pesquisador: Branch And Bound | Branch And Cut | Branch And Price | Designacao Generalizada | Programacao Inteira | Programacao Linear

Resumo

O Projeto de mestrado consiste em realizar uma análise de algoritmos tipo branch and bound para o problema de designação generalizada e implementar um algoritmo branch and bound especializado para o problema antes mencionado. Na literatura existem várias propostas de algoritmos branch and bound para o problema de designação generalizada. Tipicamente, esses algoritmos apresentam excelente desempenho somente para problemas de pequeno e de medio porte. Numa primeira fase da pesquisa, deve-se análisar de maneira crítica três algoritmos de desempenho adequado e baseadas em estratégias diferentes (relaxação PLr-relaxação do modelo e a técnica de geração de colunas). Opcionalmente, também, pode-se analisar algoritmos de tipo branch and bound especiais como o chamado algoritmos branch and price. Na Segunda fase, deve-se desenvolver um algoritmo baseado nos trabalhos da fase I e realizar testes exaustivos. (AU)