[gecode-users] Encoding of tuples as values

[Martin Mann]

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/