[gecode-users] diffn constraint for Gecode

[Christian Schulte]

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:pirkwieser at gmail.com] 
Sent: Thursday, May 26, 2011 9:34 PM
To: cschulte at kth.se
Cc: users at gecode.org
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: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On 
> Behalf Of Sandro Pirkwieser
> Sent: Wednesday, May 25, 2011 9:01 PM
> To: users at gecode.org
> 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
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>