[gecode-users] Some distinct

[Christian Schulte]

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