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: [email protected] [mailto:[email protected]] On > Behalf Of Martin Mann > Sent: Monday, February 20, 2012 6:03 PM > To: [email protected] > 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: [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 _______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
