Desenvolvimento de um algoritmo paralelo de fase I para o problema de multifluxo: uma aplicação ao problema de roteamento de dados e estudo do problema ciclagem no algoritmo fluxo em redes com custo não linear

• Processo: 00/02088-2
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de maio de 2000
• Data de Término da vigência: 30 de abril de 2002
• Área de conhecimento: Engenharias - Engenharia de Produção - Pesquisa Operacional
• Pesquisador responsável: Cassilda Maria Ribeiro
• Beneficiário: Luciano Nascimento Moreira
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Assunto(s): Rede de fluxo Programação não linear Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Algoritmos Paralelos | Fluxo Em Redes | Programacao Nao Linear | Roteamento De Dados | Teoria Dos Grafos

Resumo

O objetivo deste projeto é dar continuidade ao estudo do algoritmo paralelo para o problema de roteamento de dados desenvolvido e implementado pelo grupo Descentralização, Hierarquização e Paralelismo (DHP) do Departamento de Ciências de Computação do ICMC. O algoritmo paralelo, por nós, desenvolvido e implementado em duas versões é um algoritmo do tipo primai, logo para que ele seja executado é necessário que seja fornecida uma solução inicial factível. Desejamos então desenvolver um algoritmo paralelo que seja capaz de fornecer esta solução inicial. Um outro problema que desejamos estudar é o problema de ciclagem que ocorre nos problemas de fluxo em redes com custo não linear devido a soluções degeneradas. Os algoritmos serão implementados no sistema PVM-W95 [Sou-96]. Este sistema, desenvolvido no Departamento de Ciências de Computação do ICMC - USP - São Carlos, permite que se faça uma implementação em paralelo usando vários processadores de maneira eficiente, possibilitando assim uma boa análise de desempenho do algoritmo desenvolvido. O presente plano visa propiciar ao aluno um embasamento técnico na área de paralelismo, teoria dos grafos, fluxos em redes, programação linear e programação não linear. (AU)

Publicações acadêmicas

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

MOREIRA, Luciano Nascimento. Desenvolvimento de um algoritmo paralelo de fase I para o problema de multifluxo: uma aplicação ao problema de roteamento de dados. 2003. Dissertação de Mestrado - Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB) São Carlos.