ConstraintSolver.jl
ConstraintSolver.jl copied to clipboard
Support for obtaining the active domain of an variable
It would be great with a way of obtaining the domain in a variable when writing a Model. It's useful for writing better decompositions than "simply" using the variable's upper/lower domain that JuMP.lower_bound
and JuMP.upper_bound
support.
The syntax could be something like domain = CS.domain(v)
where domain
will be and Array/Vector of the possible values of the variable v
.
(When I'm much more comfortable with Julia as well as the source code in ConstraintSolver.jl, I might be able to write constraints / propagators at the source code level, but for a relatively beginner supports for domains and upper/lower bounds - and in general reflection/introspection - at the model is a great help.)
This was originally discussed at Zulip: https://julialang.zulipchat.com/#narrow/stream/268675-ConstraintSolver/topic/Getting.20.22active.22.20domain.20of.20a.20variable.3F
I currently lack of an example when this will be useful as I'm not really experienced in modelling. Do you mind giving an example model? 😁
Here's a simple (perhaps too simple) example of a modulo
decomposition using - what I now call - fd_dom(v)
which returns the domains of a variable as a list of integers. It might give a little better performance than using the full range range of lower_bound
..upper_bound
via JuMP. The commented lines are which I use now but it blows up for larger values.
function modulo_dom(model, x, y, z)
# lbx = round(Int, JuMP.lower_bound(x))
# ubx = round(Int, JuMP.upper_bound(x))
# lby = round(Int, JuMP.lower_bound(y))
# uby = round(Int, JuMP.upper_bound(y))
x_dom = fd_dom(x)
y_dom = fd_dom(y)
# table = resize_matrix([ [i,j,i % j] for i in lbx:ubx, j in lby:uby if j != 0])
table = resize_matrix([ [i,j,i % j] for i in x_dom, j in y_dom if j != 0])
@constraint(model, [x, y, z] in CS.TableSet(table))
end
Another constraint that might be more efficient using fd_dom
is the assignment
constraint (which holds if X[I] = J <=> Y[J] = I
for all I's and J's).
function assignment_ctr(model, x, y)
n = length(x)
b1 = @variable(model, [1:n,1:n], Bin)
b2 = @variable(model, [1:n,1:n], Bin)
x_dom = [fd_dom(x[i]) for i in 1:n] # <-
y_dom = [fd_dom(x[i]) for i in 1:n] # <-
for i in 1:n, j in 1:n
if !(i in x_dom)
@constraint(model, b1[i] == 0) # <-
end
if !(i in y_dom)
@constraint(model, b2[i] == 0) # <-
end
@constraint(model, b1[i,j] := { x[i] == j})
@constraint(model, b2[j,i] := { y[j] == i})
@constraint(model, b1[i,j] + b2[j,i] != 1 )
end
end
I.e. here we find out that some of the boolean values (e.g. b1[i]
) are not possible since they are not in x_dom
.
Also, been able to print the domains can be a good help in debugging a model since then one see how the constraints behave.
Does this help as inspiration of the use cases?
I realize that the previous version of assignment_ctr
is confusing (or misleading at best), since it use "plain ifs". Here's an adjust version were I use an extended version of the @constraint syntax: !(i in x_dom)
which I'm not sure how to model in the existing ConstraintSolver.jl version.
function assignment_ctr(model, x, y)
n = length(x)
b1 = @variable(model, [1:n,1:n], Bin)
b2 = @variable(model, [1:n,1:n], Bin)
x_dom = [fd_dom(x[i]) for i in 1:n] # <-
y_dom = [fd_dom(x[i]) for i in 1:n] # <-
for i in 1:n, j in 1:n
@constraint(model, !(i in x_dom) := {b1[i] == 0}) # <- Changed version
@constraint(model, !(i in y_dom) := {b2[i] == 0}) # <-
end
@constraint(model, b1[i,j] := { x[i] == j})
@constraint(model, b2[j,i] := { y[j] == i})
@constraint(model, b1[i,j] + b2[j,i] != 1 )
end
end