[gecode-users] Two questions about finite set variables

Patrik Haslum patrik.haslum at anu.edu.au
Mon Jan 26 02:49:58 CET 2009

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?

			/P at trik

More information about the gecode-users mailing list