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

[Pedro Salgueiro]

Hi!

I have been busy on something else, and just now got back to this.

On Tue, 2009-05-26 at 11:42 +0200, Mikael Zayenz Lagerkvist wrote:
> On Tue, May 26, 2009 at 11:36 AM, Pedro Salgueiro <pds at di.uevora.pt> wrote:
> > On Mon, 2009-05-25 at 16:30 +0200, Mikael Zayenz Lagerkvist wrote:
> > Sorry, my bad, didn't noticed that on the documentation... Now I
> > understand why it gets really slow, as the domain gets really big.
> >
> > So, there is no easy way of preventing the translation of this sparse
> > domain to a dense domain, even if it is just to make some tests and see
> > the behavior of Gecode under those circumstances?
> 
> If your domain is big (not just a big width but lots of values) then
> extensional constraints always takes a lot of memory. This is due to
> the nature of extensional constraints.
> 
> If your domain has a large width (difference between minimum and
> maximum element) but few elements (say {-1000, 0, +1000}), then the
> problem can be solved. You just need to translate your large domain
> into a smaller domain (say {0, 1, 2}). The translation can either be
> done by reformulating the problem or by channeling to a new variable
> using an element constraint.
> 

To start, sorry if I am saying something stupid :). 

Translating the large domain to a smaller one is a good idea, the
problem is that besides I need to use the extensional constraint to make
sure that the values belong to some matrix, I also have to apply
constraints to some of the values individual values of the tuple, based
on the values of the large domain. So, if I translate the domain to a
smaller one, then I have no way to apply such constraints.

For instance, let's suppose I have the following matrix:

matrix={{9900, 1234, 2349} 
        {9901, 2345, 5678}}

wich will be translated to:

translated_matrix={{0,1,2,3}
	           {4,5,6,7}}

Then I will apply an extensional constraint to make sure that the
variables C={X1,X2,X3} and C1={Y1,Y2,Y3} belongs to translated_matrix.

Then I need to apply constraints that relate individual values on each
of the tuple, such as

Y1 - X1 < 10

The problem is that this last constraint should be applied over the
initial values, and with the translated domain I can not apply such
constraints because I don't have the original values...


About the element constraint, I didn't got that one. For what I
understood on the documentation, it just constraints one variable to an
element of an array. How do this fit this problem? 

Thank you, 
Pedro Salgueiro


> 
> Cheers,
> Mikael
>