The Cell Tower Problem, Part II¶
This Jupyter Notebook can be found at https://github.com/kariheedots/DevJupyter
An integer programming formulation to find the best way to place 6 cell towers. The goal is to provide coverage to 29 or more neighborhoods. The optimal solution covers 31 neighborhoods.
In [1]:
# may need to run this in Julia in a terminal window before things work
#Pkg.add("JuMP")
#Pkg.add("Cbc")
#Pkg.update()
In [2]:
using JuMP
m = Model()
@defVar(m, 0 <= T[1:100] <= 1, Bin)
@defVar(m, 0 <= N[1:41] <= 1, Bin)
# Maximize sum of covered Neighborhoods
@setObjective(m,Max,sum{N[i], i=1:41} )
# Number of Towers
@addConstraint(m, sum{T[i],i=1:100} <= 6)
# Corner Neighborhoods
@addConstraint(m, N[37] <= T[81]+T[82]+T[91]+T[92])
@addConstraint(m, N[41] <= T[89]+T[90]+T[99]+T[100])
# North Edge Neighborhoods
@addConstraint(m, N[1] <= sum{T[i],i=2:4}+sum{T[i],i=12:14})
@addConstraint(m, N[2] <= sum{T[i],i=4:6}+sum{T[i],i=14:16})
@addConstraint(m, N[3] <= sum{T[i],i=5:7}+sum{T[i],i=15:17})
@addConstraint(m, N[4] <= sum{T[i],i=7:9}+sum{T[i],i=17:19})
# West Edge Neighborhoods
@addConstraint(m, N[5] <= sum{T[i],i=1:2}+sum{T[i],i=11:12}+sum{T[i],i=21:22})
@addConstraint(m, N[20] <= sum{T[i],i=41:42}+sum{T[i],i=51:52}+sum{T[i],i=61:62})
@addConstraint(m, N[24] <= sum{T[i],i=51:52}+sum{T[i],i=61:62}+sum{T[i],i=71:72})
@addConstraint(m, N[32] <= sum{T[i],i=71:72}+sum{T[i],i=81:82}+sum{T[i],i=91:92})
# East Edge Neighborhoods
@addConstraint(m, N[11] <= sum{T[i],i=19:20}+sum{T[i],i=29:30}+sum{T[i],i=39:40})
@addConstraint(m, N[29] <= sum{T[i],i=59:60}+sum{T[i],i=69:70}+sum{T[i],i=79:80})
@addConstraint(m, N[36] <= sum{T[i],i=79:80}+sum{T[i],i=89:90}+sum{T[i],i=99:100})
# South Edge Neighborhoods
@addConstraint(m, N[38] <= sum{T[i],i=84:86}+sum{T[i],i=94:96})
@addConstraint(m, N[39] <= sum{T[i],i=85:87}+sum{T[i],i=95:97})
@addConstraint(m, N[40] <= sum{T[i],i=88:90}+sum{T[i],i=98:100})
# Central Neighborhoods
@addConstraint(m, N[6] <= sum{T[i],i=4:6}+sum{T[i],i=14:16}+sum{T[i],i=24:26})
@addConstraint(m, N[7] <= sum{T[i],i=13:15}+sum{T[i],i=23:25}+sum{T[i],i=33:35})
@addConstraint(m, N[8] <= sum{T[i],i=15:17}+sum{T[i],i=25:27}+sum{T[i],i=35:37})
@addConstraint(m, N[9] <= sum{T[i],i=16:18}+sum{T[i],i=26:28}+sum{T[i],i=36:38})
@addConstraint(m, N[10] <= sum{T[i],i=18:20}+sum{T[i],i=28:30}+sum{T[i],i=38:40})
@addConstraint(m, N[12] <= sum{T[i],i=24:26}+sum{T[i],i=34:36}+sum{T[i],i=44:46})
@addConstraint(m, N[13] <= sum{T[i],i=26:28}+sum{T[i],i=36:38}+sum{T[i],i=46:48})
@addConstraint(m, N[14] <= sum{T[i],i=28:30}+sum{T[i],i=38:40}+sum{T[i],i=48:50})
@addConstraint(m, N[15] <= sum{T[i],i=32:34}+sum{T[i],i=42:44}+sum{T[i],i=52:54})
@addConstraint(m, N[16] <= sum{T[i],i=35:37}+sum{T[i],i=45:47}+sum{T[i],i=55:57})
@addConstraint(m, N[17] <= sum{T[i],i=36:38}+sum{T[i],i=46:48}+sum{T[i],i=56:58})
@addConstraint(m, N[18] <= sum{T[i],i=37:39}+sum{T[i],i=47:49}+sum{T[i],i=57:59})
@addConstraint(m, N[19] <= sum{T[i],i=38:40}+sum{T[i],i=48:50}+sum{T[i],i=58:60})
@addConstraint(m, N[21] <= sum{T[i],i=43:45}+sum{T[i],i=53:55}+sum{T[i],i=63:65})
@addConstraint(m, N[22] <= sum{T[i],i=44:46}+sum{T[i],i=54:56}+sum{T[i],i=64:66})
@addConstraint(m, N[23] <= sum{T[i],i=46:48}+sum{T[i],i=56:58}+sum{T[i],i=66:68})
@addConstraint(m, N[25] <= sum{T[i],i=51:53}+sum{T[i],i=61:63}+sum{T[i],i=71:73})
@addConstraint(m, N[26] <= sum{T[i],i=52:54}+sum{T[i],i=62:64}+sum{T[i],i=72:74})
@addConstraint(m, N[27] <= sum{T[i],i=53:55}+sum{T[i],i=63:65}+sum{T[i],i=73:75})
@addConstraint(m, N[28] <= sum{T[i],i=54:56}+sum{T[i],i=64:66}+sum{T[i],i=74:76})
@addConstraint(m, N[30] <= sum{T[i],i=64:66}+sum{T[i],i=74:76}+sum{T[i],i=84:86})
@addConstraint(m, N[31] <= sum{T[i],i=66:68}+sum{T[i],i=76:78}+sum{T[i],i=86:88})
@addConstraint(m, N[33] <= sum{T[i],i=72:74}+sum{T[i],i=82:84}+sum{T[i],i=92:94})
@addConstraint(m, N[34] <= sum{T[i],i=76:78}+sum{T[i],i=86:88}+sum{T[i],i=96:98})
@addConstraint(m, N[35] <= sum{T[i],i=77:79}+sum{T[i],i=87:89}+sum{T[i],i=97:99})
status = solve(m)
#print(m)
println("Objective is: ",m.objVal)
println("Solution is:")
for i = 1:100
println("T", i, " = ", getValue(T[i]))
end
