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

[Christian Schulte]

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