In sci.op-research, bigwind777@aol.com (Bigwind777) writes: > > I have 32 golfers, individual play. > We will golf for 16 weeks. > I want to set up the foursomes so each person only golfs > with the same person once. > How many weeks can we do this before it starts to duplicate ? The structure of the problem is similar to the `progressive party problem' (see Smith et. al in "Constraints" Vol 1.), let's take a similar approach for modeling it. We can specify the problem using a 0-1 integer linear program which uses the 0-1 variables P[i,f,t]=1 iff player i plays in foursome f in week t. Then, we can post constraints on these variables that define the problem. To formulate the meet-only-once restriction, one can use auxiliary variables M[i,j,t]=1 if player i and j meet in week t (i.e. if they play in the same foursome). With these variables, one can state the problem using an algebraic modeling language. For example, an AMPL model of the golf problem looks like # AMPL model of `Maximum socializing on the golf course' # June 8, 1998, J.P. Walser, Programming Systems Lab set Players ordered := { 1..32 } ; set Foursomes ordered := { 1..card(Players)/4 }; set Weeks ordered := { 1..8 } ; ### Variables # variable P[i,j,t] means i plays in foursome j in week t var P { Players, Foursomes, Weeks } binary; # auxiliary variable M[i,j,t] means i meets j in week t (i<j) var M { Players, Players, Weeks } binary; ### Constraints # each player is part of exactly one foursome in each week subject to OF { i in Players, t in Weeks }: sum { f in Foursomes } P[i,f,t] = 1; # each foursome has exactly four players subject to FP { f in Foursomes, t in Weeks }: sum { i in Players } P[i,f,t] = 4; # link the M and P variables subject to LMP { i in Players, j in Players, f in Foursomes, t in Weeks: i<j }: P[i,f,t]+P[j,f,t] - M[i,j,t] <= 1; # each pair of players only meets once subject to MO { i in Players, j in Players: i<j }: sum { t in Weeks } M[i,j,t] <= 1; # fix first round and some symmetry fix { p in Players } P[p,int((p-1)/4)+1,1] := 1; fix { p in Players, t in Weeks: t >= 2 and p <= 4 } P[p,p,t] := 1; Spelled out, the above model has 5152 Boolean variables and 22652 constraints. Having stated the problem, we can try to solve it. From experience, we know that these kind of timetabling problems are typically very difficult for 0-1 integer programming solvers (see e.g. the Progressive Party Problem study). So let's approach the problem using a local search heuristic (called Wsat(PB)) which can interface with AMPL to solve the 0-1 problem. Wsat(PB) is described in a AAAI97 paper "Solving Linear Pseudo-Boolean Constraint Problems with Local Search." An 8 week solution is: foursome 1 foursome 2 foursome 3 foursome 4 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2: 1 23 26 30 2 17 24 31 3 6 15 19 4 12 13 25 3: 1 19 24 27 2 10 14 30 3 23 25 31 4 5 9 22 4: 1 16 22 28 2 8 12 29 3 9 14 27 4 15 23 32 5: 1 9 18 29 2 11 19 23 3 12 20 26 4 8 17 30 6: 1 6 11 25 2 15 20 22 3 10 17 32 4 14 19 29 7: 1 8 13 32 2 7 9 25 3 11 22 30 4 6 16 26 8: 1 5 12 15 2 18 27 32 3 8 16 24 4 7 20 31 foursome 5 foursome 6 foursome 7 foursome 8 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 5 11 28 29 9 16 20 32 7 14 18 22 8 10 21 27 13 20 21 29 6 12 28 32 7 11 16 17 8 15 18 26 7 10 19 26 5 17 21 25 11 13 18 31 6 20 24 30 6 13 22 27 14 24 25 32 7 15 21 28 5 10 16 31 8 9 28 31 7 12 23 27 5 13 24 26 16 18 21 30 15 17 27 29 5 14 20 23 10 18 24 28 12 19 21 31 10 22 25 29 13 19 28 30 6 9 17 23 11 14 21 26 I don't know if there exists a fast combintorial scheme to construct such a plan. I used a method that solves the problem from a delcarative model. It finds 7-week solutions quickly (around 30s), and an 8-week solution after several hours. (Even if there was an efficient scheme, the problem would become a difficult search problem in the presence of additional side constraints, e.g. "never play in a foursome with the two strogenst players in two successive weeks".) Local search can generally not tell us when there isn't a solution (it's an `incomplete' strategy), but often it is efficient in finding solutions when they exist. As an upper bound, we know that there cannot be a timetable with more than 10 weeks. This is because the initial set of possible player- combinations contains (32 choose 2)=496 elements. With each foursome, we remove exactly 6 player-combinations from this set. Since each week has 8 foursomes there are at most 496/(6*8)=10.33 weeks that our reservoir of player-combinations will have enough supply for. (This can also be proved autmatically: If one attempts to solve the LP relaxation of the above integer program for 11 weeks, CPLEX returns `infeasible' after 1000s.) Using this fact, we know that can do almost as well by solving the problem for 16 time periods such that no two players meet more than _twice_. It is interesting that dispite the size of this problem (11K vars, 48K constraints), it is considerably easier to solve than the 8-weeks problem. We can get a solution from integer local search Wsat(PB) in about 40s. Of course, now two players might meet twice in a row. Joachim P. Walser ( http://www.ps.uni-sb.de/~walser )