[Gecode] Some observations on views depending on more than one variable

[Mikael Lagerkvist]

Hi,

There are some interesting problems associated with views of more than
one variable that I discovered when investigating the possibility of having
a view that represents the sum of two variables.

In the following, assume that we have two identity-views V1 and V2 (on
variables v1 and v2), and the sum-view S representing V1+V2. Let the
initial state be represented by (v1,v2)=({0..2},{0..2}).

The simple definition of the operations min and max for S are:
	max() := V1.max() + V2.max()
	min() := V1.min() + V2.min()
Now we have a problem, because telling something will not necessarily
affect subsequent min- and max-operations on S. For example, telling
"S < 3" does not imply anything for the V1 or V2. Thus we may have
that after telling "S < 3", S.max() may still return 4. This will
break some very basic assumptions made on views, and therefore we need
something stronger if sum-views are going to work.

One possible idea is to add state to the sum-view, recording the
requested minimum and maximum. This will not work either. Consider the
initial state again. Min and max for S will initially return 0 and 4
respectively. Now we tell "S < 4", making the requested upper bound
for S equal to 3. This can not affect V1 or V2, although we 'know'
that (v1,v2)!=({2},{2}). Now let V1 and V2 both be assigned 2. We are
now in an inconsistent state, that in the Gecode framework will not be
detected until we do a tell on S, which may be to late.

To 'fix' this problem, it is necessary to add all the features of a
real variable representing the sum, and then we may as well use the
explicit variable instead.


Regards,
Mikael Lagerkvist

--
Mikael 'Zayenz' Lagerkvist, http://www.imit.kth.se/~zayenz/