[gecode-users] semantics for count(Home home, const IntVarArgs &x, IntVar y, IntRelType r, IntVar z)
cschulte at kth.se
Tue Nov 22 20:07:06 CET 2011
Right, it is not domain consistent, it just performs domain propagation. I
will update the docs accordingly.
But still, it does not succeed (it is not logically entailed) but it does
not fail yet (as it is not domain consistent). Try labeling Y and see what
Christian Schulte, KTH, web.it.kth.se/~cschulte/
From: Kish Shen [mailto:kisshen at cisco.com]
Sent: Tuesday, November 22, 2011 6:35 PM
To: cschulte at kth.se
Cc: users at gecode.org
Subject: Re: [gecode-users] semantics for count(Home home, const IntVarArgs
&x, IntVar y, IntRelType r, IntVar z)
I am still not sure I understand the semantics -- the constraint is posted
with domain consistency (the default). My understanding of domain
consistency is that any values remaining in the domain is consistent with
the constraint, i.e. the constraint should not fail if the variable is
instantiated to one of the values, as long as this is the only change made.
Y :: [3,4], count([3,0,3,3,4], Y, =, 2)
Y is the only domain variable with more than one value, so if I understand
domain consistency correctly, then instantiating it to either
3 or 4 should succeed, but doing so fails for both values.
The documentation states that:
Supports domain consistent propagation (icl = ICL_DOM, default) and "almost"
domain consistent propagation (all other values for icl), where y is not
(I assume by other values of icl, you exclude ICL_DEF, which behaves as
ICL_DOM as that is the default)
It seems to me the behaviour is that y is not pruned in the above, even when
the constraint is posted with ICL_DOM and ICL_DEF -- I have explicitly
posted the constraint with ICL_DOM, to check if it makes any difference, and
it does not, i.e. the example with Y::[3,4] succeeds.
On 22/11/2011 08:49, Christian Schulte wrote:
> This is a fundamental missunderstanding of what an integer set and an
> integer variable denotes.
> It might be that the current domain of an integer variable is a set,
> however the variable denotes a single integer (which you do not know
> yet). That's fundamental and very different from a set.
> With that in mind, count behaves exactly like one would expect.
> In your example, the constraint does not succeed (as in being
> entailed). It just does not fail yet. Let's take the more general
> example (2 is replaced by an integer variable Z):
> Y :: [3,4], count([3,0,3,3,4], Y, =, Z)
> Then it will propagate that Z has the domain [0..4] as there are four
> elements in the array that still could be equal to Y with domain 3 or
> 4 and one is already known to be different (the element 0) from 3 or 4.
> Christian Schulte, www.ict.kth.se/~cschulte/
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On
> Behalf Of Kish Shen
> Sent: Tuesday, November 22, 2011 8:09 AM
> To: users at gecode.org
> Subject: [gecode-users] semantics for count(Home home, const
> IntVarArgs&x, IntVar y, IntRelType r, IntVar z)
> I have been looking at the behaviour of
> count(Home home, const IntVarArgs&x, IntVar y, IntRelType r, IntVar z)
> and cannot understand what is happening when IntVar y has more than
> one value in its domain. Until now, I have only tested this constraint
> with y having a singleton value in its domain, and in this case, the
> constraint behaves the same as the case where y is Int, i.e. the
> number of occurrences of the value y in x is counted.
> However, one of my user wanted to use the constraint where y has
> multiple values (i.e. the counts constraint in the global constraint
> catalog). I know this constraint is provided with y being an IntSet,
> but my user did not know about this constraint, so he used the version
where y is a IntVar instead.
> I had expected that mulitple domain values in y would behave like
> multiple values in the IntSet for this constraint, but this does not
> seem to be the case. For example, the constraint succeeds with the
> following (in ECLiPSe syntax, but the argument order of Gecode's
> Y :: [3,4], count([3,0,3,3,4], Y, =, 2)
> where [3,0,3,3,4] is x, IntRelType is IRT_EQ.
> I don't understand why this succeeds -- the count for 3 is 3, and for
> 4 is 1, and for both 3 and 4 is 4, none of which is equal to 2. So
> what is the semantics?
> The equivalent call using y as an IntSet [3,4] fails as expected.
> Also, for the same count constraint, if y has a single domain value
> (e.g. 3 or 4), then the constraint behave as I expected, i.e. z = 3
> for y = 3, and z = 1 for y = 1.
> Thanks and cheers,
> This e-mail may contain confidential and privileged material for the
> sole use of the intended recipient. Any review, use, distribution or
> disclosure by others is strictly prohibited. If you are not the
> intended recipient (or authorized to receive for the recipient),
> please contact the sender by reply e-mail and delete all copies of this
> Cisco Systems Limited (Company Number: 02558939), is registered in
> England and Wales with its registered office at 1 Callaghan Square,
> Cardiff, South Glamorgan CF10 5BT.
> Gecode users mailing list
> users at gecode.org
This e-mail may contain confidential and privileged material for the sole
use of the intended recipient. Any review, use, distribution or disclosure
by others is strictly prohibited. If you are not the intended recipient (or
authorized to receive for the recipient), please contact the sender by reply
e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in England
and Wales with its registered office at 1 Callaghan Square, Cardiff, South
Glamorgan CF10 5BT.
More information about the users