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: [email protected] [mailto:[email protected]] 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
[email protected]
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
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
