Understanding of implies

Specific Domains Optimization (Mathematical)
1

Can someone explain to me how should I read this and which values can variables have?

model = Model()
@variable(model, x[1:2], Bin)
@constraint(model, x[1] <= x[2])

Should I read it like: this constraint will ensure that:
x1 =1 and x2 = 1
x1 = 0 and x2 = 1
x1 = 0 and x2 = 0

2

Assuming 1 is true and 0 is false, you should read it as “if x[1] then x[2]” or as the contra-positive of this statement “if not x[2] then not x[1].” The converse is not true though because x[1] being false tells us nothing about x[2] and x[2] being true tells us nothing about x[1]. I hope I didn’t add to the confusion!

4 Likes
3

Thanx. So this constraint will make sure that:

If X1 = 1 then X2 will be 1 too and if X1 = 0 we don’t care about X2 is that?

4

Pretty much. But you can also read it starting from x2. If x2 is 0 then x1 is 0, and if x2 is 1 we don’t care about x1.

5

Now, I have an model that I am trying to solve AND understand. The problem here is this constraint:

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
)

Here isCovered can be 0 even if sum(isAntenna) >= 1, but we don’t want that. We want to say if at least one antenna is around us we are covered, and if there is no antenna around us then we are not covered. Above constraint works, don’t get me wrong, I just can’t understand it and that is why I am back with this question again.

6

Are you maximizing coverage in the objective or minimizing the number of antennas?

7

minimizing the number of antennas

8

can you post the full problem?

9

Here:

10

Looking at the model, I am fairly confident that isCovered doesn’t mean what you think it means. If isCovered is 1, then the house is covered. If it is 0, then it may or may not be covered. Consider the case where the minimum coverage is 1 and you have 1 antenna covering 2 houses because it happens to be between them. isCovered can be 1 for either or both houses and that won’t affect the feasibility or optimality of the solution. If you want to find whether a house is truly covered or not as a post-processing, re-compute the sum of antennas in the neighborhood.

If you want to ensure the converse is satisfied, you need new constraints isCovered[(i, j)] >= isAntenna[r, c] for all (r, c) in the neighborhood of (i, j).

2 Likes
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
12

That was my thinking too, but Marc here said otherwise: Trying to solve a puzzle - #11 by MarcMush

Look, I am OK with this, as I see that there is no better way to do it.

13

Thank you again and I may take this course after all.

14

Can that course be done on JuMP? Looks like submissions are on python but it’s possible to call external binaries, does that mean JuliaCall might work?

1 Like
15

It is based on Python, BUT you can call your Julia code and grab console results. I’ve started the course already and modify the submission file (submit.py) like this:

#!/usr/bin/python
# -*- coding: utf-8 -*-

import os
from subprocess import Popen, PIPE

def solve_it(input_data):

    tmp_file_name = 'tmp.data'
    tmp_file = open(tmp_file_name, 'w')
    tmp_file.write(input_data)
    tmp_file.close()

    process = Popen(['julia', 'Solver.jl', tmp_file_name], stdout=PIPE, universal_newlines=True)
    (stdout, stderr) = process.communicate()

    os.remove(tmp_file_name)

    out = stdout.strip()

    arr = out.split("\n")
    while len(arr) > 2:
        arr.pop(0)
    out = "\n".join(arr)

    return out

import sys

if __name__ == '__main__':
    if len(sys.argv) > 1:
        file_location = sys.argv[1].strip()
        with open(file_location, 'r') as input_data_file:
            input_data = input_data_file.read()
        print(solve_it(input_data))
    else:
        print('This test requires an input file.  Please select one from the data directory. (i.e. python solver.py ./data/ks_4_0)')
1 Like