Dear Sandro, It will be equivalent to the decomposition into reified constraints albeit using constructive disjunction for better pruning. Yes, eventually one should go for something based on Beldiceanu & Carlsson.
The real reason to add it for us has been that we needed a variant where the dimensions of the boxes are variables as well (slightly more messy as the box might turn out to have a volume of zero!). If you ever feel like getting busy, please let me know! Best Christian -- Christian Schulte, KTH, web.it.kth.se/~cschulte/ -----Original Message----- From: Sandro Pirkwieser [mailto:[email protected]] Sent: Thursday, May 26, 2011 9:34 PM To: [email protected] Cc: [email protected] Subject: Re: [gecode-users] diffn constraint for Gecode Dear Christian, > Co-incidence: I have been adding a naïve (but better than the > decomposition) version of the constraint to Gecode recently. I will > move that code to the trunk this week (there are still some glitches to fix before that). now that's convenient! On which algorithm is it based? > The plan is to eventually improve to a state-of-the-art implementation. This sounds good. Would you consider the sweep algorithm proposed by Beldiceanu and Carlsson as state-of-the-art, or are there any alternatives? Btw do you know which one is applied in JaCoP? > Taking code directly from Jacop into Gecode will not work due to their > license. The intention was more to get an inspiration. Anyway, both frameworks probably differ too much. > Maybe you would even be interested to contribute? At least you would > have a nice structure to start from. Yes, we can indeed think about this. Though I am not yet in a state where I can "hack" something into Gecode, it would be a good opportunity to start doing so. Best regards, Sandro > We will release soonish a new version that will incorporate that but > there are more things to be done before a release. > > Best > Christian > > -- > Christian Schulte, KTH, web.it.kth.se/~cschulte/ > > > -----Original Message----- > From: [email protected] [mailto:[email protected]] On > Behalf Of Sandro Pirkwieser > Sent: Wednesday, May 25, 2011 9:01 PM > To: [email protected] > Subject: [gecode-users] diffn constraint for Gecode > > Hello, > > I'm using Gecode to tackle a 2D packing subproblem inside an > optimization problem. The subproblem is about packing rectangles (for > the meantime without rotation) into a given larger rectangle and many > instances of moderate size need to be solved. Fortunately I was able > to start with the perfect-square example, where the adapted variant > already performs quite good (using the cumulatives constraint). Also > enabling branching on intervals yielded a speed-up. Now I was > wondering if someone of you already implemented a suitable diffn > constraint (see > http://www.emn.fr/z-info/sdemasse/gccat/Cdiffn.html) in Gecode. In > this way the non-overlapping part would (presumably) be tackled more > efficiently and give an additional performance boost. Do you think > having a look at the > diff/diff2 implementation in JaCoP is useful for implementing it in Gecode? > Thanks! > > Best regards, > Sandro > > _______________________________________________ > 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
