[gecode-users] counting/sequence constraints failing when IntVarArray too small

[Kish Shen]

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, cschulte at kth.se
> Expert Researcher, SICS, cschulte at sics.se
>
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Kish Shen
> Sent: Tuesday, June 30, 2015 08:06 PM
> To: users at 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 at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>