From: <wh_at_icparc.ic.ac.uk>

Date: Wed 13 Oct 2004 04:44:46 PM GMT

Message-ID: <20041013164446.GB14206@tempest.icparc.ic.ac.uk>

Date: Wed 13 Oct 2004 04:44:46 PM GMT

Message-ID: <20041013164446.GB14206@tempest.icparc.ic.ac.uk>

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, WarwickReceived on Wed Oct 13 17:47:01 2004

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:31 PM GMT GMT
*