Combining approximation algorithms with metaheuristics for the facility location problem

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)