Re: Social Golfers

Hi Mark,

On Mon, Oct 11, 2004 at 06:13:31PM +0100, Mark A. Hennessy wrote:
> Hi there,
> 
>    I'm using Eclipse 5.7. I've been implementing a number of different 
> models of the social golfer problem in Eclipse. I've run into a problem 
> in trying to
> implement one of the constraints for a particular model I have 
> formulated. The code I have written so far is:
> 
> % Give an account of this model in mathematical notation. C1 and C2
> % are automatically enforced my the setup of the data-structures in
> % this model
> sgp_model2(Weeks,NumberOfGroups,GroupSize,Groups) :-
>    % Calculate the number of golfers
>    NumGolfers is NumberOfGroups*GroupSize,
>   
>    % 2-d Groups Matrix of Variables
>    dim(Groups,[NumGolfers,Weeks]),
>   
>    % The Domain of each Group matrix variable is the range of
>    % 1..NumberOfGroups
>    Groups[1..NumGolfers,1..Weeks] :: 1..NumberOfGroups,
> 
>    % C3: limits the number of times a group identifier appears in a 
> particular
>    % week to GroupSize
>    (for(W,1,Weeks), param(Groups,NumGolfers,GroupSize,NumberOfGroups) do
>        (for(G,1,NumberOfGroups), param(Groups,W,NumGolfers,GroupSize) do
>            Occur is Groups[1..NumGolfers,W],
>            occurrences(G,Occur,GroupSize)           
>        )
>    ),

I'd be interested to know how using G occurrence constraints here compares
with using one sorted constraint (assuming group size of 4 for the example):

    sorted(Occur, [1,1,1,1,2,2,2,2,3,3,3,3,etc.])

Just trying to think outside the box.  Might be a lousy idea - might not
propagate as well.

>    % C4: All pairs of golfers must play each other at most once
>    sigma(W)(Groups[X,W] = Groups[Y,W]) <= 1

What you want is for each (distinct) X and Y, the number of times they
appear in the same group in some week is at most one.  So you do more or
less just that:

    (
	for(X, 1, NumGolfers - 1),
	param(Groups, NumGolfers, Weeks)
    do
	(
	    for(Y, X+1, NumGolfers),
	    param(Groups, Weeks, X)
	do
	    (
		for(W, 1, Weeks),
		foreach(Bool, Meet),
		param(Groups, X, Y)
	    do
		% Bool is 1 iff X and Y are in the same group in this week
		#=(Groups[X, W], Groups[Y, W], Bool)
	    ),
	    sum(Meet) #=< 1
	)
    )

(Usual disclaimer: untested code... ;)

Cheers,
Warwick