[gecode-users] Symbolic Constraints - fd_relation contraint in Gecode?

[Pedro Salgueiro]

Hi!

On Mon, 2009-05-25 at 16:35 +0200, Christian Schulte wrote:
> Okay, then what one can do is use DFAs (or REGs) for specification, they are
> not as fast but they work perfectly well with spares domains.

That's a great idea, but on this case I don't see a how can I specify
the problem (or the allowable values for the tuples) using DFAs or REGs.

Any way, I have tried the same tests using the Finite Domain Solver of
GNU Prolog with its predicate fd_realtion/2 [1] that is very similar to
Gecode extensional constraint, and the results were much better.

Thank you,
Pedro Salgueiro

[1] http://www.gprolog.org/manual/html_node/gprolog062.html#toc274 

> 
> Christian
> 
> --
> Christian Schulte, www.ict.kth.se/~cschulte/
> 
> 
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Mikael Zayenz Lagerkvist
> Sent: Monday, May 25, 2009 4:30 PM
> To: Denys Duchier
> Cc: users at gecode.org
> Subject: Re: [gecode-users] Symbolic Constraints - fd_relation contraint in
> Gecode?
> 
> Hi,
> 
> On Wed, May 20, 2009 at 8:36 PM, Denys Duchier
> <denys.duchier at univ-orleans.fr> wrote:
> > I could be wrong about this, but I just had a quick glance at the
> > implementation and its seems to allocate datastructures of a size
> > proportial to the width of the domain.  So if you have small values and
> > very large values, the width is going to be very large.
> >
> > If I am right, then you might be better off encoding your N values into
> > the interval [0,N-1] and then possibly using an element constraint to
> > decode them where necessary.
> >
> > Then again, I could be completely off base :-/
> 
> Actually, you are completely right, and it also says so in the
> documentation [1]:
>     Warning:
>         If the domains for the $x_i$ are not dense and have similar
>         bounds, lots of memory will be wasted (memory consumption
>         is in $
> O\left(|x|\cdot|\min_i(\underline{x_i})-\max_i(\overline{x_i})|\right)$
>         for the basic algorithm (epk = EPK_MEMORY) and additionally
>         $
> O\left(|x|^2\cdot|\min_i(\underline{x_i})|\max_i(\overline{x_i})|\right)$
>         for the incremental algorithm (epk = EPK_SPEED).
> 
> The memory-consumption in the size of the domain is inevitable for
> reasonably efficient extensional propagators. The translation into a
> dense domain from a sparse domain needs to happen at one point or
> another anyway for efficient data-structure management, and I choose
> not to do it automagically.
> 
> Cheers,
> Mikael
> 
> [1]
> https://www.gecode.org/doc-latest/reference/group__TaskModelIntExt.html#gf88
> 5611633b7b2bfb4d9512071dee9a3
>