[gecode-users] Two questions about finite set variables
Patrik Haslum
patrik.haslum at anu.edu.au
Mon Jan 26 02:49:58 CET 2009
Hi,
I'm experimenting with different formulations of a problem, using finite
set variables, and have come across two questions.
Q1: Propagation for the weights constraint. I've posted the constraint:
weights(this, elems, costs, deleted, total_cost);
where "deleted" is an otherwise unconstrained SetVar, total_cost an
unconstrained IntVar, and
elems = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
18, 19, 20}
costs = {4, 2, 4, 3, 4, 2, 2, 6, 2, 3, 1, 2, 4, 3, 4, 2, 3, 1,
3, 3, 2}
Next, I post a cardinality constraint on deleted, saying it contains at
least 2 and at most 3 elements. After propagation (call to status()),
the domains of the variables are as follows:
deleted = {}..{0..20}#(2,3)
total_cost = [0..14]
So, it seems that the upper bound on the cardinality of deleted has been
propagated to total_cost (it is at most the sum of the 3 largest costs),
but the lower bound has not (total_cost can not be smaller than the sum
of the 2 smallest costs, which is 2, yet the lower bound remains zero).
This is the case also if I change the upper bound on cardinality (for
example, if I don't put one at all, the upper bound on total_cost
becomes 60, the sum of all the costs, but the lower bound stays zero).
Is there an explanation for this behaviour? And, more importantly, is
there any way to change it? Since I'm trying to solve an optimisation
problem, it is of course the lower bound on cost that is important.
Q2: When branching on in/not-in for a potential element of SetVar, what
is the order in which the alternatives are tried? (i.e., does it explore
the in or out branch first). And how do I change it to do the opposite?
Thanks,
/P at trik
More information about the gecode-users
mailing list