[gecode-users] Encoding of tuples as values

[Christian Schulte]

Hi,

As you say, you might have to try ;-) I think I'll make pair available for
the next release (it doesn't really hurt).

Cheers
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 Martin Mann
> Sent: Monday, February 20, 2012 6:03 PM
> To: cschulte at kth.se
> Cc: 'gecode user list'
> Subject: Re: [gecode-users] Encoding of tuples as values
> 
> 
> Hi Christian,
> 
> thanks for the quick response!
> 
> The Pair constraint looks quite useful for me. It can be used to post an
order on
> the tuples, a distinct constraint etc. But so far I am not sure if there
are many
> applications where you can use it on its own.
> Thus, I am not sure if you want/have to make it generally available.
> 
> Concerning my tuple problem and your suggestion to use two variables per
> tuple-variable:
> 
> Maybe a mini description of the problem itself: it is a variant of the
subgraph-
> matching problem where I want to find a very constraint subgraph of k
nodes in
> two graphs (each with n (>>k) nodes) simultatiously, to get a mapping from
one
> graph into the other. This is where the tuples come from, i is from the
first
> graph, j from the second.
> 
> I am unsure if to use the pair of variables or a direct (hard coded)
encoding using
> half the variables.
> 
> The reason is, I can rule out most (many) of the tuples when initializing
the CSP
> domains, ie. many node combinations are not allowed. Thus, I could create
a set
> of all plausible tuples and use it as the initial domains of my variables.
> 
> If I go for the two-variable-model with 2*k variables with domains [1,n],
I would
> have to post additional (cheap) constraints plus 2*n additional helper
variables
> (with small domains) in order to rule out all non-plausible node mappings,
ie.
> tuples.
> Not sure if the additional propagation needed will compensate for the more
low
> level encoding. :/ Furthermore, I am not sure if the two variable encoding
is as
> expressive as a single tuple-encoding variable version, since the latter
allows for
> more specific tuple set encodings. E.g. {(1,2),(2,1)} versus
> {1,2}x{1,2}={(1,1),(1,2),(2,1),(2,2)}.
> 
> Mhh... most likely I have to try both in order to find out.. :(
> 
> If you have further suggestions or comments, please let me know. And
thanks
> for your thoughts!
> 
> So long,
> Martin
> 
> 
> Am 20.02.2012 16:44, schrieb Christian Schulte:
> > Hi Martin,
> >
> > Gecode does not have tuples so you would have to represent this by two
> > variables. However, this representation is rather weak (you might want
> > to read Tip 6.3 in MPG what the issue is) as one can only express
> > information about each component in the tuple individually but not
> > information about tuples (that is, ruling out certain combinations of
values).
> >
> > Then there is even a hand-optimized propagator for the constraint you
> > are talking about (it is used for matrix element constraints) but
> > unfortunately the constraint is not directly available in a Gecode
> > model. If you look at the file gecode/int/element.cpp and search "pair"
you
> will see what I mean.
> > Maybe I should make the constraint available in general. What do you
say?
> >
> > Cheers
> > 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 Martin Mann
> > Sent: Monday, February 20, 2012 4:08 PM
> > To: gecode user list
> > Subject: [gecode-users] Encoding of tuples as values
> >
> >
> > Hi everybody,
> >
> > after years I am back to implement a CSP with Gecode and would like to
> > get your feedback on the best way how to handle the encoding.
> >
> > My problem has integer tuples (i,j) as values for its variables while
> > i and j are bound by an interval [1,n], ie. (i,j) \in (n x n), and n
> > usually< 200.
> >
> > There has been much change in the Gecode library since I used it. Is
> > there already a way to directly use tuples as values or do I have to
> > encode them via integers?
> >
> > If not, do you see a better/faster way of encoding than doing
> >     v = i*(n+1) + j
> > such that I get i=(v/(n+1)) and j=(v%(n+1))?
> >
> > If yes, do you expect a large performance difference between using
> > tuples or encode/decode integers? I will only need a global "distinct"
> > constraint, some binary order constraints and some instances of a
> > selfwritten binary constraint.
> >
> > Thanks for your feedback!
> >
> > Yours,
> > Martin
> >
> >
> > --
> > Dr. Martin Mann, PostDoc assistant
> > Bioinformatics - Inst. of Computer Science Albert-Ludwigs-University
> > Freiburg
> > Fax: ++49-761-203-7462
> > http://www.bioinf.uni-freiburg.de/~mmann/
> >
> >
> > _______________________________________________
> > Gecode users mailing list
> > users at gecode.org
> > https://www.gecode.org/mailman/listinfo/gecode-users
> >
> 
> --
> Dr. Martin Mann, PostDoc assistant
> Bioinformatics - Inst. of Computer Science Albert-Ludwigs-University
Freiburg
> Fax: ++49-761-203-7462
> http://www.bioinf.uni-freiburg.de/~mmann/
> 
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users