[gecode-users] Interfacing GeCode to ECLiPSe

[Christian Schulte]

Hi Kish,

As it comes to the search interface: I have been discussing with other
LP-minded people and from these discussions I do recall the following design
outline:

Search:
 (1) Eclipse tells Gecode to create a choicepoint
 (2) Eclipse tells Gecode to backtrack until the next choicepoint (or some
choicepoint if you want it to be
     more powerful than that)

Interfacing:
 (3) Eclipse tells Gecode about variable modifications
 (4) Eclipse tells Gecode to create new variables and propagators
 (5) Eclipse instructs Gecode to do propagation and queries Gecode about
changes to variable domains 

Then, a starting point for implementing backtracking would be to just use
cloning to make it work (that should be really use but inefficient). Then,
in a second step one could use a hybrid of recomputation and cloning (just
replay what has been done by (3) and (4) and redo propagation). For a
realistic interface Gecode must use recomputation.

I think this kind of interface would be quite useful also for other
languages/systems based on backtracking. Provided that:
 - you come up with a naïve implementation that is not Eclipse specific
(say, there will be one part that is Gecode specific and then a separate
part that is Eclipse specific, and the Gecode part can be used without
Eclipse)
 - you put the Gecode-specific part under the MIT license

We could optimize the Gecode-specific part including adding recomputation,
include the Gecode-specific part with Gecode and hence adopt and maintain
it.

What do you think?
Christian
 

--
Christian Schulte, www.it.kth.se/~cschulte/

-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Guido Tack
Sent: Monday, January 26, 2009 7:27 PM
To: Kish Shen
Cc: users at gecode.org
Subject: Re: [gecode-users] Interfacing GeCode to ECLiPSe

Kish Shen wrote:

> I am not sure what are the trade-offs between the two APIs Guido
> outlined -- is it simply that using reflection will be less flexible?

In a way, it's more flexible.  All constraints and variable types  
available in Gecode will be automatically available through the  
interface.  When constraints or variable types are added to Gecode,  
they are available without changing the interface code (and maybe even  
without recompiling the interface).

> I am not very familiar with interface generators like SWIG, although I
> did take a look at it briefly several years ago, and my impression was
> that it mainly serve to map the data structures between C/C++ and the
> target language. In ECLiPSe's interface to MP solvers such as CPLEX,  
> we
> needed to do quite a lot of extra coding in C, in addition to the data
> transformation between C and ECLiPSe, and I suspect we might require
> such extra coding for the interface to GeCode as well. In  
> particular, I
> don't expect a direct mapping from ECLiPSe to the GeCode methods at  
> the
> ECLiPSe level.

Yes, that's how they work.  For our Java interface (which is generated  
by swig), we had to write quite some glue code, too.

> I expect that at the ECLiPSe level, we will use syntax that looks a  
> lot
> like the existing syntacx for the native solvers. I expect that at a
> minimum, we would need to be able to add both constraints and  
> variables
> dynamically.

Sure, that shouldn't be a problem.  Gecode is quite dynamic anyway, it  
would be an artificial restriction to make this static.

> In the backbox search approach, I think we will also need
> to be able to be able to `backtrack' into the search to obtain further
> solutions after the initially one.

The other interfaces usually solve this by providing an object that  
represents the search, and which has a "next" method that you can call  
as often as there are solutions.  I guess you could provide a similar  
interface in Eclipse.

> In the case where the search is done
> by ECLiPSe, my initial thought is that we need to do only the
> propagation in GeCode, but do the search in ECLiPSe. This would mean
> that we need someway of `undoing' the effects of a propagation step,
> without directly using the search/branching facilities of GeCode.

Right.  But Gecode does not provide a mechanism for undoing these  
effects. You can only keep a copy of a space and then redo the effects  
instead.  But this can be hidden behind some layer of abstraction.

> Do you
> expect that I can use Reflection API for both the black-box and the
> ECLiPSe search approach?

Yes.  As reflection will only be used to set up the initial space, it  
should work with both approaches.

Cheers,
	Guido


_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users