Algoritmos de aproximação para o problema da localização de instalações

• Processo: 18/13083-5
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de outubro de 2018
• Data de Término da vigência: 30 de junho de 2020
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Mário César San Felice
• Beneficiário: Renata Sarmet Smiderle Mendes
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Bolsa(s) vinculada(s): 19/16276-1 - Combinando algoritmos de aproximação com metaheurísticas para o problema da localização de instalações, BE.EP.IC
• Assunto(s): Programação linear inteira Otimização combinatória Algoritmos de aproximação Análise de algoritmos Problemas de localização de facilidades
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Problema da localização de instalações | programação linear inteira | Otimização Combinatória

Resumo

No problema da Localização de Instalações busca-se decidir quantas e quais instalações abrir de modo a atender as demandas de conexão dos clientes. Ele é bastante relevante tanto do ponto de vista de dificuldade teórica, sendo um problema NP-difícil largamente estudado e para o qual inúmeros algoritmos de aproximação são conhecidos, quanto pela motivação de aplicações práticas, por modelar problemas como posicionamento de fábricas, construção de redes de computadores e clusterização de informação. Este projeto tem como objetivos o estudo de algoritmos de aproximação para o problema da Localização de Instalações, a implementação de alguns destes algoritmos, e a produção de um relatório técnico com os resultados estudados, que sirva de base para outros pesquisadores da área. Esta iniciação científica também visa introduzir a candidata à área de pesquisa científica e objetiva complementar sua formação na área de Ciência da Computação, aprofundando seu conhecimento em otimização combinatória, algoritmos de aproximação e técnicas de projeto e análise de algoritmos.