INDR $220$: Introduction to Computing for Operations Research

Homework $3$: The Cell Tower Coverage Problem

In this homework, you will implement a Python script that solves the cell tower coverage

problem using CPLEX. A telecom company needs to build a set of cell towers to provide signal

coverage for the inhabitants of a given city. H$\backslash$times W potential locations where the towers could

be built have been identified. The towers have a fixed range $($it covers its own region and its

neighboring regions, namely, west, north, east, and south$),$ and only a limited number of them

can be built due to budget constraints. 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 H$\backslash$times W 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 to provide coverage to as many people as possible.

The decision variables are

x$\_($ij$)=\{(1$ if tower is built in region $($i$,$j$),)$:$\}$

$0$ otherwise $,$

y$\_($ij$)=\{(1$ if region $($i$,$j$)$ is covered by at least one tower, $)$:$\}$

$0$ otherwise

and the given information includes

H$=$ height of city

W$=$ width of city

T$=$ maximum number of towers

p$\_($ij$)=$ population in region $($i$,$j$)$

The integer linear programming formulation of this problem becomes

ma$\backslash$xi mizez$=\backslash$sum$\_($i$=1)^$H $\backslash$sum$\_($j$=1)^$W p$\_($ij$)$y$\_($ij$)$

subject to: x$\_($ij$)+\backslash$sum$\_(($k$),$l$)$in neighbors $($i$,$j$)$x$\_($kl$)>=$y$\_($ij$),$i$=1,2,$dots,H;$,$j$=1,2,$dots,W

$\backslash$sum$\_($i$=1)^$H $\backslash$sum$\_($j$=1)^$W x$\_($ijT

x$\_($ij$)$in$\{0,1\},$i$=1,2,$dots,H;$,$j$=1,2,$dots,W

y$\_($ij$)$in$\{0,1\},$i$=1,2,$dots,H;$,$j$=1,2,$dots,Wp$\_($ij$)$ H rows and W columns, and it is composed of the following lines for an example problem: import scipy.sparse as sp

import cplex as cp

def mixed$\_($i$)$nteger$\_($l$)$inear$\_($p$)$rogramming$($direction$,$ A$,$ senses$,$ b$,$ c$,$ l$,$ u$,$ types, names$)$:prob $=$ cp$.$Cplex$()$prob$.$variables.add$($obj $=$ c$.$tolist$(),$ lb $=$ l$.$tolist$(),$ ub $=$ u$.$tolist$(),$ types $=$ types.tolist$(),$ names $=$ names.tolist$)$if direction $==$ "maximize":

prob.objective.set$\_($s$)$ense$($prob$.$objective.sense.maximize$)$

else:

prob.objective.set$\_($s$)$ense$($prob$.$objective.sense.minimize$)$prob$.$linear$\_($c$)$onstraints$.$add$($senses $=$ senses$.$tolist$(),$ rhs $=$ b$.$tolist$())$row$\_($i$)$ndices$,$ col$\_($i$)$ndices $=$ A$.$nonzero$()$

prob.linear$\_($c$)$onstraints$.$set$\_($c$)$oefficients$($zip$($row$\_($i$)$ndices$.$tolist$(),$ col$\_($i$)$ndices$.$tolist$(),$ A$.$data.tolist$()))$

print$($prob$.$write$\_($a$)$s$\_($s$)$tring$())$prob$.$solve$()$print$($prob$.$solution.get$\_($s$)$tatus$())$

print$($prob$.$solution.status$[$prob$.$solution.get$\_($s$)$tatus$()])$x$\_($s$)$tar $=$ prob.solution.get$\_($v$)$alues$()$

obj$\_($s$)$tar $=$ prob.solution.get$\_($o$)$bjective$\_($v$)$alue$()$

return$($x$\_($s$)$tar$,$ obj$\_($s$)$tar$)$ def cell$\_($t$)$ower$\_($c$)$overage$\_($p$)$roblem$($populations$\_($f$)$ile$,$ T$)$:your implementation ends above

return$($X$\_($s$)$tar$)$

X$\_($s$)$tar $=$ cell$\_($t$)$ower$\_($c$)$overage$\_($p$)$roblem$("$populations$.$txt$",3)$

print$($X$\_($s$)$tar$)$