[gecode-users] Some distinct

[David Rijsman]

Hi Christian ;),

you are absolutely right we can do this with the global count
constraint and I have actually found a paper which compares the two
approaches (Complete Bound Consistency for the Global Cardinality
Constraint, Irit Katriel, Sven Thiel at
http://citeseer.ist.psu.edu/721003.html ). I will remodel my problem
and see which one performs better,

thanks for the pointer and let me take this moment to let you know I
am very impressed with Gecode in performance, quality and the level of
documentation, I still have to encounter my first bug in using Gecode,

David Rijsman

On Dec 4, 2007 3:37 PM, Christian Schulte <cschulte at kth.se> wrote:
> Hi David,
>
> There is no real plan to implement some-distinct. But we are happy to accept
> contributions (and are willing to give prime support in return for that ;-)
> ). The paper should be accessible through SpringerLink:
>        http://www.springerlink.com/content/n8226635404k1670/
>
> However, I believe that some-different is not what you want to have. To me
> it looks like count (or global cardinality) which is included in Gecode
> (just after a quick look).
>
> 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 David Rijsman
> Sent: Tuesday, December 04, 2007 2:58 PM
> To: users at gecode.org
> Subject: [gecode-users] Some distinct
>
> Are there any plans to introduce the some-distinct constraint
> (Generalizing AllDifferent: the SomeDifferent Constraint,
> Yossi Richter, Ari Freund and Yehuda Naveh) in Gecode? If I had access
> to the paper I could see if I could do an attempt to implement this it
> but if
> there are plans or other ways to get the same semantics that would be
> a waste of time.
>
> My use case is the following:
>
> For d subsequent periods I have 1,..,k(d) activities to assign to n
> resources where k(d) <= n and there are all kinds of constraints
> between activities in different periods assigned to the same resource.
>
> Today I model this by introducing a variable x<i,j> for period i and
> resource j with initial domain [1,..,n] where value v corresponds with
> activity v in period d and all value greater than k(i) to be
> non-activities.
>
> On all the variables of the different resources in the same period I
> post the distinct constraint such that the same activity does not get
> assigned to the same resource.
>
> This works as long as I interpret the values x<i,j> greater or equal
> to k(i) identical in the subsequent constraints in the model also I
> would need a customized branching strategy to only commit to one value
> greater than k
>
> I prefer to do the following:
>
> Introduce a variable x<i,j> for period i and resource j with initial
> domain [1,..,k(i) + 1 ] where value v less or equal to k(i)
> corresponds with activity v in period d and value k(i) corresponds to
> no activity.
>
> On all the variables of the different resources in the same period I
> post the some-distinct constraint such that the same activity does not
> get assigned to the same resource. If value k(i) is selected it does
> not have to be different from the other variables.
>
> David Rijsman
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>