[Gecode] gecode/Mercury/HAL interface

[David Overton]

I tried to subscribe to the gecode mailing list, but I'm not sure if
it's worked.

On Mon, Nov 17, 2003 at 06:01:40PM +0100, Christian Schulte wrote:
> before getting to the details I think the best way we can make progress is
> that I take care of the more Gecode related stuff and that you take care of
> the more HAL/Mercury related issues. On top of that I will help you to get
> everything going from the Gecode perspective.
> 
> So, I think one way how we can make progress is that we agree on a couple of
> interfaces capturing what you need and that we implement these interfaces.
> You than do the necessary code for using the interfaces from HAL.

Sounds good.

> If you wish I could try to summarize the interface which I would like to
> implement and where you check whether it is sufficient for your purpose.

Yes, please do that.

> As said, I'd really prefer to not get to that level of detail. But currently
> I don't see how this can be brought together in the easisest way with what I
> have been describing. One option (a rather naïve one) would be that each
> time the current cpi has changed, one will create an entire copy of Gecode's
> current state (or something that allows to get back by recomputation). 

Yes, this is the usual approach for interfacing with the Mercury trail.
The question is whether it is likely to be feasible for gecode, and
whether there is a better way to do it.

> What worries me a little bit is to have to deal with the current cpi. Would
> it be possible for you to do something for HAL which uses what I have been
> describing in my previous Email.

I am a bit unclear exactly what you meant by your previous description.
I.e. who is is responsible for each of the steps you mention (create
choice point and return cpi, check for failure, go back to a cpi)?

> > What we want to be able to do is have a number of "delay 
> > conditions" which can be used to delay a goal until a 
> > condition is satisfied.  For a FD solver, we want (at least) 
> > these conditions:
> > 
> > 	fixed(X):	The value of the variable X becomes fixed.
> > 	ubc(X):		The upper bound of X changes.
> > 	lbc(X):		The lower bound of X changes.
> > 	dc(X):		The domain of X changes.
> > 
> > One way to do this would be to associate 4 lists of goals 
> > with each variable (i.e. one list for each delay condition).  
> > Each operation that constrains the variable would then need 
> > to check these 4 lists and execute the relevant goals.
> 
> Okay, I think I get it. How about the following intermediate interface:
> after Gecode has computed a fixpoint, it returns a list of modifed variables
> together with how they have been modfied. From that list you then choose
> which goals to run. Is that okay? Or do I miss something here?

That is likely to be quite expensive, I think.  It would require
scanning that list of variables to determine which ones have goals
delayed on them.  Peter Stuckey's idea is to add a special kind of
"propagator" which is responsible for calling the goals.  Is that
approach likely to work?


David
-- 
David Overton                  Uni of Melbourne     +61 3 8344 1354
dmo at cs.mu.oz.au                Monash Uni (Clayton) +61 3 9905 9373
http://www.cs.mu.oz.au/~dmo    Mobile Phone         +61 4 0337 4393