Understanding of implies

Specific Domains Optimization (Mathematical)
11

I’ll repeat my answer from: Trying to solve a puzzle - #15 by odow

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)

If the right-hand side of the is_covered[h] <= constraint is 1, then is_covered[h] can be 0 or 1. But the next constraint means that there is a benefit to it taking the value 1. Of course, is the ratio constraint isn’t binding in an optimal solution, then there may be some houses h that are covered by the cell tower, but still have is_covered[h] = 0.

The typical way to fix this is to add a small term to the objective to encourage the “correct” solution

@objective(model, Min, sum(cell_tower) - 0.001 * sum(is_covered))

OR modeling is a large field, and more of an art than a science. There are some good online courses to learn more:

1 Like