Hi,
Thanks for the link. I have only read the abstract, as the paper itself
seems to be behind a paywall in that link.
I am not sure if either cases should be considered as being undefined.
For count/atmost, I feel strongly that the number of variables being
less than the limit should be allowed. It so happens that for the >/>=
relations, the constraint will always be satisfied, and for the other
relations, the constraint will always fail.
If an extra condition is added that the number of variables must be at
least the same size as the limit, as in done in GCAT, then having the
small number of variables can be considered as undefined, but I am not
sure there are any logical reason to do so -- there may be
implementation reason to do so, of course. As I said, previously, I had
expected the constraint to succeed in this case, and the atmost
constraint in ECLiPSe's other solvers succeed in such cases as well,
including fd, the original fd solver of ECLiPSe.
For the sequence constraint, it is less clear cut to me if the number of
variables is less than the sequence size. I can see why this should be
considered as undefined. But Joachim's suggestion of dealing with cases
smaller than the sequence size does seem useful, and he does have a use
case for it.
I agree that if the two cases are regarded as undefined, then they
should raise an exception rather than failing. For count, it seems to me
that the behaviour should then be undefined for all relations to be
consistent, even though failing is the correct behaviour if the number
of variables are allowed to be smaller than the limit.
Cheers,
Kish
On 30/06/2015 20:16, Christian Schulte wrote:
Hi,
There is a paper discussing this:
http://link.springer.com/chapter/10.1007%2F978-3-642-04244-7_30
I rather have an exception in most cases. But documenting this in MPG is
really too much effort, that is why it is only in the reference
documentation.
Cheers
Christian
--
Christian Schulte, www.gecode.org/~schulte
Professor of Computer Science, KTH, cschu...@kth.se
Expert Researcher, SICS, cschu...@sics.se
-----Original Message-----
From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf
Of Kish Shen
Sent: Tuesday, June 30, 2015 08:06 PM
To: users@gecode.org
Subject: [gecode-users] counting/sequence constraints failing when
IntVarArray too small
Hi,
My earlier post about min and argmin throwing an exception prompted me to
remember a discussion I had with Joachim Schimpf some time ago about the
semantics of the sequence constraint:
sequence(home, x, s, q, l, u)
if I remember correctly, he thought the constraint should not fail if the
number of variables in x is smaller than q, but larger than l, and the
number of values in x is between l and u. He actually was using the
constraint on some problem instances that had this property.
I did not initially remember that the discussion was about sequence, so I
first looked at the count constraint, and found a similar behaviour with the
IRT_LQ and IRT_LE in
count(home, x, y, IRT_LQ, z)
the constraint fails if the size of x is smaller than than z, even though
the relationship is actually true - the number of times the variables in x
is y is less than z.
I had expected the constraint to succeed in this case, and the atmost
constraint in ic does succeed in such cases (ic restrict z to be an integer
for atmost). I can see that the count fails here because z is constrained to
0..|x|, for all relationships.
Does it make sense for these constraints to succeed in such cases when the
relationship (number of times the value(s) occur) is satisfied, even though
the number of variables is smaller than the limit/sequence length? I am
uncertain for the sequence case, but for count, succeeding makes more sense
to me.
If not succeeding, should an exception be raised instead of failing?
This will alert the user to the fact that there are too few variables for
the constraint, rather than the number of values not satisfying the
requirements.
Should the behaviour be documented in the MPL? I don't think it is mentioned
there at the moment.
Cheers,
Kish
_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
_______________________________________________
Gecode users mailing list
users@gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
