Combining approximation algorithms with metaheuristics for the facility location problem

• Grant number: 19/16276-1
• Support Opportunities: Scholarships abroad - Research Internship - Scientific Initiation
• Start date: November 01, 2019
• End date: January 31, 2020
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Mário César San Felice
• Grantee: Renata Sarmet Smiderle Mendes
• Supervisor: Regina Esther Berretta
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
• Institution abroad: University of Newcastle, Australia
• Associated to the scholarship: 18/13083-5 - Approximation algorithms for the facility location problem, BP.IC

Abstract

In the Facility Location Problem, it is sought to decide how many and which facilities to open in order to serve the connection demands of the clients. It is a very relevant problem both due to its theoretical interest, being an NP-hard problem widely studied and for which numerous approximation algorithms and metaheuristics are known, as well as for being motivated by practical applications, modeling problems such as plant positioning, construction of computer networks and information clustering.This project objective is to study metaheuristics for the Facility Location Problem and to learn how to combine them with approximation algorithms already studied, in order to achieve good solutions. The implementation of these algorithms followed by an empirical analyses of results is also an objective of this project. We believe that the results achieved will be interesting for the scientific community. This BEPE project aims to complement the student's training in Computer Science, deepening her knowledge in combinatorial optimization, metaheuristics, approximation algorithms and techniques for the design and analysis of algorithms. (AU)