Re: Re: Social Golfers

On Wed, Oct 13, 2004 at 01:15:19PM +0100, Mark A. Hennessy wrote:
> Hi Warwick,
> 
>    Once again. Thanks for your help. Yes this works just fine. My 
> attempt at C4 was:
> 
>    % C4: All pairs of golfers must play each other at most once
>    (for(X,1,NumGolfers-1), param(Groups,Weeks,NumGolfers) do
>        (for(Y,X+1,NumGolfers), param(X,Groups,Weeks) do
>        (for(W,1,Weeks),
>         foreach(U,List), param(Y,X,Groups) do
>            (Groups[X,W] == Groups[Y,W] ->
>            U is 1
>            ;
>            U is 0
>            )
>         sum(List) #=< 1
>        )
>        )
>    ).
> 
> I did now know to create this constraint correctly.

Yes, the above only does what you want if the elements of Groups are ground
(never put a constraint in the condition of an if-then-else unless you
*really* know what you're doing :).  If you find you want to do conditional
constraints (such as a constraint form of if-then-else) then typically
reified constraints will allow you to express it.

> Also, I realised that what I really want here is sum(List)  #= 1 since 
> I'm interested in maximum socialization.

In which case you're solving Resolvable Balanced Incomplete Block Designs
(RBIBDs).  (Any "social golfer" instance where every pair of players meets
exactly once (or exactly twice, or ...) is an RBIBD.)  If you want to know
more about these (e.g. tables of which instances are solvable and which
aren't), see The CRC Handbook of Combinatorial Designs, edited by Colbourn
and Dinitz.  Excellent reference, the starting point for anything you want
to know about combinatorial designs.

> I'm not clear on how the sorted constraint you suggested, instead of G 
> occurrence constraints on each Groups column, can enforce
> Group size?

Right, suppose we have 5 groups of 3 players each, and Occur is a list (of
variables) representing which group each player appears in in a given week
(as you had in your original code).  The constraint is then:

    sorted(Occur, [1,1,1,2,2,2,3,3,3,4,4,4,5,5,5])

This says that some permutation of the elements in Occur must be the list
given.  Since there are three occurrences of each group number, each group
number is constrained to appear three times in Occur, hence enforcing the
group size constraint.

Cheers,
Warwick