Yes, they say “at least 70%” so it has to bi Min with constraint sum(…) >= _TOTAL * 0.7.
Now I can;t quite define constraints for isAntenna → isCovered. Per my logic it should be if there is Antenna it should cover adjusting cells, but still dont know how to write constraints for that.
@constraint(
prmx,
[i in 1:_ROWS, j in 1:_COLUMNS],
isCovered[i, j]
<=
isAntenna[i, j]
+ sum(
isAntenna[r, c]
for r in i - 1:i + 1, c in j - 1:j + 1
if r != i && r >= 1 && r <= _ROWS && c != j && c >= 1 && c <= _COLUMNS
)
)
you can simplify a bit:
@constraint(
prmx,
[i in 1:_ROWS, j in 1:_COLUMNS],
isCovered[i, j]
<=
sum(
isAntenna[r, c]
for r in i - 1:i + 1, c in j - 1:j + 1
if 1 <= r <= _ROWS && 1 <= c <= _COLUMNS
)
)
and the objective should simply be the total amount of antennas:
for @objective I agree and understand, but can’t visualize that isCovered and isAntenna relationship, here it says that isCovered <= sum(isAntenna), hm…, should it be other way around like isCovered >= sum(isAntenna)?
using JuMP, Cbc
function main(; houses::Vector{Tuple{Int,Int}}, ratio::Float64)
M = maximum(h[1] for h in houses)
N = maximum(h[2] for h in houses)
model = Model(Cbc.Optimizer)
@variable(model, cell_tower[1:M, 1:N], Bin)
@variable(model, is_covered[houses], Bin)
@objective(model, Min, sum(cell_tower))
stencil(i, j) = cell_tower[max(i-1,1):min(i+1,M), max(j-1,1):min(j+1,N)]
@constraint(model, [h in houses], is_covered[h] <= sum(stencil(h[1], h[2])))
@constraint(model, sum(is_covered) >= ratio * length(houses))
optimize!(model)
return value.(cell_tower)
end
houses = [(1, 9), (3, 2), (4, 4), (5, 6), (8, 9), (9, 1)]
main(houses, ratio = 0.7)
The most important, what I failed to understand, is that isCovered is in the function of houses. I was thinking about the grid that one antenna can cover, but I should think about which houses antenna(s) can cover instead.
Here is the model:
using JuMP, Cbc, XLSX
mat = XLSX.readdata("data/input.xlsx", "sheet1", "A1:J10")
M = size(mat, 1)
N = size(mat, 2)
ratio = 0.7
houses = []
for i = 1 : M
for j = 1 : N
if mat[i,j] == 1
push!(houses, (i,j))
end
end
end
model = Model(Cbc.Optimizer)
@variable(model,
isCovered[houses],
Bin)
@variable(model,
isAntenna[1:M, 1:N],
Bin)
@objective(
model,
Min,
sum(isAntenna)
)
@constraint(
model,
sum(isCovered) >= length(houses) * ratio
)
@constraint(
model,
[h in houses],
isCovered[h] <=
sum(
isAntenna[r, c]
for r in h[1]-1:h[1]+1, c in h[2]-1:h[2]+1
if 1 <= r <= M && 1 <= c <= N
)
)
optimize!(model)
res = primal_status(model)
if res == MOI.FEASIBLE_POINT
val = value.(isAntenna)
open("out/result.txt","w") do io
for i in 1:M
for j in 1:N
print(io, floor(Int, val[i,j]))
print(io, '\t')
end
print(io, "\n")
end
end
end
Great! But I am still a conventional programmer though and will need some time to understand and start using those operators like . Anyway I am already on another page: puzzlor.com did you solve that too?
I was thinking is it possible to put a @variable in for loop? For example:
Size = 2
@constraint(
model,
[h in houses],
isCovered[h] <=
sum(
isAntenna[r, c]
for r in h[1] - Size:h[1] + Size, c in h[2] - Size:h[2] + Size
if 1 <= r <= M && 1 <= c <= N
)
)
Is it possible to make Size to be Int @variable? ...and if not, why?