timofeevalex / markovchains_planning5gdeployment

Markov chains and Metropolis-Hastings methods applied to planning a deployment of 5G networks

Deploying a 5G Network in a country

This repository provides the solution of team "X/|Eb" to the project for graduate course "Markov Chains and Algorithmic Applications". (COM-516) at EPFL.

The goal of the project is to plan the deployment of 5G network in a country with given cities (coordinates and populations are known). For this problem, we designed several solutions to how the problem can be seen as a Markov chain. Next, we developed Metropolis-Hastings algorithm to optimize the objective function. Finally, we did a comparative analysis among different proposed chains and suggested a network deployment plan.

A complete description of the project is given in project_description.pdf.

Report of our work is given in paper.pdf.

The notebook main.ipynb contains all visualizations presented in our report. The source code for Metropolis-Hastings algorithm is in ./src as well as auxiliary functions. In our solution, besides the main task we carry out comparative analysis of four base chains. For this purpose, we prepared results of experiments for all chains with different $\lambda$, $\beta$ and its increase factor. This data is contained in ./chains_results as PyTorch tensors.

Authors:

Dubravka Kutlesic (@dkutlesic, [email protected])

Aleksandr Timofeev (@TimofeevAlex, [email protected])

Andrei Afonin (@AfoninAndrey, [email protected])