[gecode-users] Symbolic Constraints - fd_relation contraint in Gecode?
Christian Schulte
cschulte at kth.se
Mon May 25 16:35:53 CEST 2009
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.
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
--
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
More information about the gecode-users
mailing list