Just recently I bumped on this: The PuzzlOR and I want to play a bit with that and solve it using JuMP.

My approach is not yet certain, but something like this:

load data into DICT(string, int) * actually just 0 or 1

total houses * 0.7 will be maximum for the objective function

Now, can I use indicator constraints to set value for my variables?

If cell A2 will hold a value then that value should be equal to sum from all adjusting cells in DICT (including that cell), and then set adjusting cells variables to be = 0.

Is it possible to set variables based with indicator constraints?

amount_covered_houses >= 0.7*total_houses should be a constraint, not an objective, and your objective should be to minimize the amount of antennas

I think I solved it with JuMP, using only Binary variables
I used matrices rather than Dicts to store data and variables

to know if a cell is covered, your constraint can be iscovered <= sum(isantenna.(neighbors))
since these are binary variables and the solver will try to maximize iscovered, itâ€™s equivalent to iscovered == |(isantenna.(neighbors)...)

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)?

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
)

corresponds to

isCovered[i, j] ==
|([
isAntenna[r, c]
for r in i-1:i+1, c in j-1:j+1
if 1 <= r <= _ROWS && 1 <= c <= _COLUMNS
]...)

and for completeness you can add:

isCovered[i, j] .>=
[
isAntenna[r, c]
for r in i-1:i+1, c in j-1:j+1
if 1 <= r <= _ROWS && 1 <= c <= _COLUMNS
]

this works fine for me and I find the right answer (6 antennas for 29 houses covered)
I donâ€™t understand what youâ€™re trying to do in your last post

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: The PuzzlOR did you solve that too?