[Gecode] Distributors, batch recomputation

[Christian Schulte]

Your scenario is of course a desaster for recomputation. However, it is also
a desaster for non-recomputation: the addition of further constraints can
break it anyway (anyt constraint on either a or b will do). So it's boned
anyway.

But what is clear is that I have to come up with an invariant that describes
hwat are you allowed to do when you want to use recomputation. A simple
restriction (the same as used in Oz) is to restrict us to the case that
there is only one branching to be created at any time. That will do.

Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/ 

-----Original Message-----
From: gecode-bounces at ps.uni-sb.de [mailto:gecode-bounces at ps.uni-sb.de] On
Behalf Of Guido Tack
Sent: Wednesday, July 14, 2004 11:45 AM
To: Technical discussions about Gecode
Subject: Re: [Gecode] Distributors, batch recomputation


Am Mittwoch, 14. Juli 2004 11:18 schrieb Christian Schulte:
> I follow your conclusions but I do not follow your concerns. In which 
> way does branching creation depend on the state of the space? Could 
> you please elaborate.

Maybe I haven't really understood the way distributors are created 
dynamically, but this is what I have in mind:

The Int::Combinators::Select propagator waits for an int variable to be 
assigned and then e.g. creates a new distributor. Assume the following
setup:

intvar a,b
select(create new distributor 1, b)
select(create new distributor 2, a)
distribute naive [a,b]

Now without recomputation, you would probably create the new distributors in

the order 2,1, because a gets determined by distribution before b. In batch 
recomputation, however, you do both distribution steps, determining a and b,

before propagation. Now I guess that the selection propagator waiting for b 
will be invoked first (or at least I don't see why it shouldn't be ;-), so 
the order in which the new distributors are created is 1,2. This will mess
up 
the later steps in batch recomputation, because we will try to commit to 
descriptions in the original order.

Guido

-- 
Guido Tack
Programming Systems Lab
http://www.ps.uni-sb.de/~tack
_______________________________________________
Gecode mailing list
Gecode at ps.uni-sb.de http://www.ps.uni-sb.de/mailman/listinfo/gecode