cell_tower_coverage/cell_tower.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cell Tower Coverage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Objective and Prerequisites\n",
    "\n",
    "Want to learn how to configure a network of cell towers to provide signal coverage to the largest number of people possible? In this example, you’ll learn how to solve this simple covering problem. We’ll show you how to construct a mixed-integer programming (MIP) model of the problem, implement this model in the Gurobi Python API, and find an optimal solution using the Gurobi Optimizer.\n",
    "\n",
    "This modeling example is at the beginner level, where we assume that you know Python and that you have some knowledge about building mathematical optimization models.\n",
    "\n",
    "**Download the Repository:** <br />\n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Motivation\n",
    "\n",
    "Over the last ten years, smartphones have revolutionized our lives in ways that go well beyond how we communicate. Besides calling, texting, and emailing, more than two billion people around the world now use these devices to navigate to book cab rides, to compare product reviews and prices, to follow the news, to watch movies, to listen to music, to play video games,to take photographs, to participate in social media, and for numerous other applications.\n",
    "\n",
    "A cellular network is a network of handheld smartphones in which each phone communicates with the telephone network by radio waves through a local antenna at a cellular base station (cell tower). One important problem is the placement of cell towers to provide signal coverage to the largest number of people."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Description\n",
    "\n",
    "A telecom company needs to build a set of cell towers to provide signal coverage  for the inhabitants of a given city. A number of potential locations where the towers could be built have been identified. The towers have a fixed range, and -due to budget constraints- only a limited number of them can be built. Given these restrictions, the company wishes to provide coverage to the largest percentage of the population possible. To simplify the problem, the company has split the area it wishes to cover into a set of regions, each of which has a known population. The goal is then to choose  which of the potential locations the company should build cell towers on -in order to provide coverage to as many people as possible.\n",
    "\n",
    "The Cell Tower Coverage Problem is an instance of the Maximal Covering Location Problem [1]. It is also related to the Set Cover Problem. Set covering problems occur in many different fields, and very important applications come from the airlines industry. For example, Crew Scheduling and Tail Assignment Problem [2]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution Approach\n",
    "\n",
    "Mathematical programming is a declarative approach where the modeler formulates a mathematical optimization model that captures the key aspects of a complex decision problem. The Gurobi Optimizer solves such models using state-of-the-art mathematics and computer science.\n",
    "\n",
    "A mathematical optimization model has five components, namely:\n",
    "\n",
    "* Sets and indices.\n",
    "* Parameters.\n",
    "* Decision variables.\n",
    "* Objective function(s).\n",
    "* Constraints.\n",
    "\n",
    "We now present a mixed-integer programming (MIP) formulation for the Cell Tower Coverage Problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Formulation\n",
    "\n",
    "### Sets and Indices\n",
    "\n",
    "$i \\in T$: Index and set of potential sites to build a tower.\n",
    "\n",
    "$j \\in R$: Index and set of regions.\n",
    "\n",
    "$G(T,R,E)$: A bipartite graph defined over the set $T$ of potential sites to build a tower,  the set of regions $R$ that we want to cover, and $E$ is the set of edges, where we have an edge $(i,j) \\in E$ if region $j \\in R$ can be covered by a tower on location $i \\in T$.\n",
    "\n",
    "### Parameters\n",
    "\n",
    "$c_{i} \\in \\mathbb{R}^+$: The cost of setting up a tower at site $i$.\n",
    "\n",
    "$p_{j} \\in \\mathbb{N}$: The population at region $j$.\n",
    "\n",
    "### Decision Variables\n",
    "\n",
    "$covered_{j} \\in \\{0, 1 \\}$: This variable is equal to 1 if region $j$ is covered; and 0 otherwise.\n",
    "\n",
    "$build_{i} \\in \\{0, 1 \\}$: This variable is equal to 1 if tower $i$ is built; and 0 otherwise.\n",
    "\n",
    "### Objective Function(s)\n",
    "\n",
    "- **Population covered**. We seek to maximize the total population covered by the towers.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Max} \\quad Z = \\sum_{j \\in R} p_{j} \\cdot covered_{j}\n",
    "\\tag{0}\n",
    "\\end{equation}\n",
    "\n",
    "### Constraints\n",
    "\n",
    "- **Coverage**. For each region $j \\in R$ ensure that at least one tower that covers a region must be selected.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{(i,j) \\in E} build_{i} \\geq covered_{j} \\quad \\forall j \\in R\n",
    "\\tag{1}\n",
    "\\end{equation}\n",
    "\n",
    "- **Budget**. We need to ensure that the total cost of building towers do not exceed the allocated budget.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{i \\in T} c_{i} \\cdot build_{i} \\leq \\text{budget}\n",
    "\\tag{2}\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Implementation\n",
    "\n",
    "This example considers a bipartite graph for 6 towers and 9 regions. The following table illustrates which regions (columns) are covered by each cell tower site (rows).\n",
    "\n",
    "| <i></i> | Region 0 | Region 1 | Region 2 | Region 3 | Region 4 | Region 5 | Region 6 | Region 7 | Region 8 |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- | --- |  --- |\n",
    "| Tower 0 | 1 | 1 | - | - | - | 1 | - | - |  - |\n",
    "| Tower 1 | 1 | - | - | - | - | - | - | 1 |  1 |\n",
    "| Tower 2 | - | - | 1 | 1 | 1 | - | 1 | - |  - |\n",
    "| Tower 3 | - | - | 1 | - | - | 1 | 1 | - |  - |\n",
    "| Tower 4 | 1 | - | 1 | - | - | - | 1 | 1 |  1 |\n",
    "| Tower 5 | - | - | - | 1 | 1 | - | - | - |  1 |\n",
    "\n",
    "The population at each region is stated in the following table.\n",
    "\n",
    "| <i></i> | Region 0 | Region 1 | Region 2 | Region 3 | Region 4 | Region 5 | Region 6 | Region 7 | Region 8 |\n",
    "| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |\n",
    "| Population | 523 | 690 | 420 | 1010 | 1200 | 850 | 400 | 1008 | 950 |\n",
    "\n",
    "The cost to build a cell tower at each location site is stated inthe following table.\n",
    "\n",
    "| <i></i> | Cost (millions of USD) |\n",
    "| --- | --- |\n",
    "| Tower 0 | 4.2 |\n",
    "| Tower 1 | 6.1 |\n",
    "| Tower 2 | 5.2 |\n",
    "| Tower 3 | 5.5 |\n",
    "| Tower 4 | 4.8 |\n",
    "| Tower 5 | 9.2 | \n",
    "\n",
    "The allocated budget is $\\$20,000,000$.\n",
    "\n",
    "We now import the Gurobi Python Module. Then, we initialize the data structures with the given data.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "\n",
    "# tested with Gurobi v9.0.0 and Python 3.7.0\n",
    "\n",
    "# Parameters\n",
    "budget = 20\n",
    "regions, population = gp.multidict({\n",
    "    0: 523, 1: 690, 2: 420,\n",
    "    3: 1010, 4: 1200, 5: 850,\n",
    "    6: 400, 7: 1008, 8: 950\n",
    "})\n",
    "\n",
    "sites, coverage, cost = gp.multidict({\n",
    "    0: [{0,1,5}, 4.2],\n",
    "    1: [{0,7,8}, 6.1],\n",
    "    2: [{2,3,4,6}, 5.2],\n",
    "    3: [{2,5,6}, 5.5],\n",
    "    4: [{0,2,6,7,8}, 4.8],\n",
    "    5: [{3,4,8}, 9.2]\n",
    "})\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Model Deployment\n",
    "\n",
    "We now determine the model for the Cell Tower Coverage Problem, by defining the decision variables, constraints, and objective function. Next, we start the optimization process and Gurobi finds the plan to build towers that maximizes  the coverage of the population given the budget allocated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using license file c:\\gurobi\\gurobi.lic\n",
      "Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "Optimize a model with 10 rows, 15 columns and 36 nonzeros\n",
      "Model fingerprint: 0xfa0fabb2\n",
      "Variable types: 0 continuous, 15 integer (15 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 9e+00]\n",
      "  Objective range  [4e+02, 1e+03]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [2e+01, 2e+01]\n",
      "Found heuristic solution: objective -0.0000000\n",
      "Presolve removed 4 rows and 5 columns\n",
      "Presolve time: 0.00s\n",
      "Presolved: 6 rows, 10 columns, 21 nonzeros\n",
      "Variable types: 0 continuous, 10 integer (10 binary)\n",
      "\n",
      "Root relaxation: objective 7.051000e+03, 1 iterations, 0.00 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "*    0     0               0    7051.0000000 7051.00000  0.00%     -    0s\n",
      "\n",
      "Explored 0 nodes (1 simplex iterations) in 0.02 seconds\n",
      "Thread count was 8 (of 8 available processors)\n",
      "\n",
      "Solution count 2: 7051 -0 \n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 7.051000000000e+03, best bound 7.051000000000e+03, gap 0.0000%\n"
     ]
    }
   ],
   "source": [
    "# MIP  model formulation\n",
    "m = gp.Model(\"cell_tower\")\n",
    "\n",
    "build = m.addVars(len(sites), vtype=GRB.BINARY, name=\"Build\")\n",
    "is_covered = m.addVars(len(regions), vtype=GRB.BINARY, name=\"Is_covered\")\n",
    "\n",
    "m.addConstrs((gp.quicksum(build[t] for t in sites if r in coverage[t]) >= is_covered[r]\n",
    "                        for r in regions), name=\"Build2cover\")\n",
    "m.addConstr(build.prod(cost) <= budget, name=\"budget\")\n",
    "\n",
    "m.setObjective(is_covered.prod(population), GRB.MAXIMIZE)\n",
    "\n",
    "m.optimize() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Analysis\n",
    "The result of the optimization model shows that the maximum population that can be covered with the $\\$20,000,000$ budget is 7,051 people. Let's see the solution that achieves that optimal result.\n",
    "\n",
    "### Cell Tower Build Plan\n",
    "\n",
    "This plan determines at which site locations to build a cell tower."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " Build a cell tower at location Tower 0.\n",
      "\n",
      " Build a cell tower at location Tower 2.\n",
      "\n",
      " Build a cell tower at location Tower 4.\n"
     ]
    }
   ],
   "source": [
    "# display optimal values of decision variables\n",
    "\n",
    "for tower in build.keys():\n",
    "    if (abs(build[tower].x) > 1e-6):\n",
    "        print(f\"\\n Build a cell tower at location Tower {tower}.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Demand Fulfillment Metrics\n",
    "\n",
    "- **Coverage**: Percentage of the population covered by the cell towers built."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " The population coverage associated to the cell towers build plan is: 100.0 %\n"
     ]
    }
   ],
   "source": [
    "# Percentage of the population covered by the cell towers built is computed as follows.\n",
    "\n",
    "total_population = 0\n",
    "\n",
    "for region in range(len(regions)):\n",
    "    total_population += population[region]\n",
    "\n",
    "coverage = round(100*m.objVal/total_population, 2)\n",
    "\n",
    "print(f\"\\n The population coverage associated to the cell towers build plan is: {coverage} %\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Resources Utilization Metrics\n",
    "\n",
    "- **Budget consumption**: Percentage of the budget allocated to build the cell towers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " The percentage of budget consumed associated to the cell towers build plan is: 71.0 %\n"
     ]
    }
   ],
   "source": [
    "# Percentage of budget consumed to build cell towers\n",
    "\n",
    "total_cost = 0\n",
    "\n",
    "for tower in range(len(sites)):\n",
    "    if (abs(build[tower].x) > 0.5):\n",
    "        total_cost += cost[tower]*int(build[tower].x)\n",
    "\n",
    "budget_consumption = round(100*total_cost/budget, 2)\n",
    "\n",
    "print(f\"\\n The percentage of budget consumed associated to the cell towers build plan is: {budget_consumption} %\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Conclusion\n",
    "\n",
    "In this example, we address the problem of building cell towers to provide signal coverage  to the largest number of people while satisfying a budget constraint. We learned how to formulate the problem as a MIP model. Also, we learned how to implement the MIP model formulation and solve it using the Gurobi Python API."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "[1] Richard Church and Charles R. Velle. \"The Maximal Covering Location Problem\". Papers in Regional Science, 1974, vol. 32, issue 1, 101-118.\n",
    "\n",
    "[2] Tail Assignment Problem. https://www.gurobi.com/case_study/air-france-tail-assignment-optimization/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright © 2020 Gurobi Optimization, LLC"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}